架构师训练营 - 第八周 - 总结

一、数据结构与算法

时间复杂度与空间复杂度

• 时间复杂度：算法执行语句的次数

• 空间复杂度：临时占用存储空间的大小

数组

• 特点：

• 必须要内存中一块连续的空间

• 数组中的数据都具有相同的数据类型

• 访问数据时间复杂度 O(1)

链表

• 特点：

• 不需要连续的空间存储

• 查找元素只能遍历链表

• 增删数据快

• 查找数据时间复杂度：O(N)

Hash 表

• 特点：可快速访问数据、快速增删数据

• key 可能发生冲突

栈

• 特点：后进先出

队列

• 特点：先进先出

• 如：生产者消费者

树

• 二叉排序树

• 左子树上所有节点的值均小于或等于它的根节点的值

• 右子树上所有节点的值均大于或等于它的根节点的值

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

• 平衡二叉树

• 从任何一个节点处罚，左右子树深度只差的绝对值不超过 1

• 左右子树也分别为平衡二叉树

• 红黑树

• 每个节点只有 2 种颜色：红、黑

• 根节点是黑色的

• 每个叶子节点都是黑色的空节点

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

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

• 增删节点时，红黑树通过染色和旋转，保持红黑树满足定义

• 红黑树与平衡二叉树的比较

• 红黑树最多只需 3 次就会重新达到红黑平衡，时间复杂度 O(1)

• 在大量增删的情况下，红黑树的效率更高

• 红黑树的平衡性不如平衡二叉树

• 红黑树的查找效率要差一些

跳表

• 链表 + 多级索引

• 空间换时间

• 时间复杂度：O(logn)

• redis 使用跳表

常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

二、网络通信协议

OSI 七层模型

• 应用层

• 表示层

• 会话层

• 传输层

• 网络层

• 物理层

TCP/IP 四层模型

• 应用层

• 传输层

• 网络互联层

• 网络访问（链路）层

非阻塞 IO

• IO 操作立即返回，发起县城不会阻塞等待

三、数据库架构原理与性能优化

数据库架构

• 连接器

• 语法分析器

• 语义分析与优化器

• 执行引擎

索引

• 聚簇索引

• 聚簇索引的数据库记录和索引存储在一起

• MySQL 的主键就是聚簇索引，主键 ID 和所在的记录行存储在一个 B+树中

• 非聚簇索引

• 非聚簇索引在叶子结点记录的就不是数据行记录，而是聚簇索引，也就是主键

• 回表：通过非聚簇索引找到主键索引，再通过主键索引找到行记录

• 注：

• 不要盲目添加索引

• 删除不用的索引，避免不必要的增删开销

• 使用更小的数据类型创建索引

数据库事务

• 事务特性 ACID

• 原子性

• 隔离性

• 持久性

• 一致性