第八周总结

用户头像
Linuxer
关注
发布于: 2020 年 07 月 29 日

数据结构

时间复杂度与空间复杂度

NP问题:能在多项式时间复杂度内验证答案正确与否的问题。



数组:连续空间、数据类型相同,随机快速读写

链表:每个数据元素必须包含一个指向下一个数据元素的内存地址指针

链表增删数据比数组性能好

数组随机访问元素比链表好



Hash表,快速访问,增删除数据

栈 先进后出

队列 先进先出 典型场景 生产消费



二叉排序树

左子树上所有结点的值小于或等于根结点的值

右子树上所有结点的值大于或等于根结点的值

左、右子树也分别为二叉排序树



平衡二叉排序树

左右子树深度之差的绝对值不超过1



红黑树

根节点是黑色的

从根节点到叶子节点,不会出现两个连续的红色节点

从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点



跳表

空间复杂度较高,以空间换时间



常用算法



网络

网络分层



网络数据包格式

TCP三次握手、四次挥手

HTTP1.0 客户端与服务器之间交换的每个请求/响应都会创建一个新的TCP连接

HTTP2 引入HTTP流

复用同一个TCP连接,队头堵塞

HTTP3 QUIC 自定义的传输协议,多个QUIC流共享相同的QUIC连接

基于UDP包



非阻塞I/O:I/O操作立即返回,发起线程不会阻塞等待

非阻塞read操作:

Socket接收缓冲区有数据,读n个

Socket接收缓冲区没数据,则返回失败(不会等待)

非阻塞write

Socket发送缓冲区满,返回失败

Socket发送缓冲区不满,写n个数据

通过I/O多路复用,避免业务线程阻塞



数据库

 preparestatement 减少硬解析的代价, 可以防止SQL注入

连接器 -》 语法分析器 -》语义分析与优化器 -》执行计划 -》引擎

存储结构:

B+树、LSM树、

事务:ACID

用户头像

Linuxer

关注

还未添加个人签名 2018.06.12 加入

还未添加个人简介

评论

发布
暂无评论
第八周总结