架构师训练营——第 8 周学习总结

数据结构与算法

时间复杂度

• O(1)

• O(logn)

• O(n)

• O(n^2)

• O(n^3)

• O(2^n)

• O(n!)

空间复杂度

• 数组长度

• 递归的深度



数组(Array)、链表(LinkedList)、跳表(SkipList)

Array 时间复杂度 查询O(1) 增删O(n)

LinkedList 时间复杂度 查询O(n) 增删O(1)

prepend append lookup insert delete

Array O(1) O(1) O(1) O(n) O(n)

LinkedList O(1) O(1) O(n) O(1) O(1)

跳表特点 只能用于元素有序的情况 对标平衡树（AVL Tree）和二分查找是一种 插入/删除/搜索都是O(logn)数据结构



哈希、映射、集合的实现与特性

• 哈希表Hashtable 也叫散列表 关键码值（key value）存放，映射函数叫做散列函数，存放记录的数组叫做哈希表

• 增删查时间复杂度 O(1)

• Map key-value对 ，key不重复

• Set 不重复元素的集合

• TreeMap和TreeSet 时间复杂度都是logN

栈

• 数组和链表都被称为线性表

• 在线性表的基础加上增删操作的限制条件：后进先出

• 应用场景：函数调用中的参数与局部变量

队列

• 也是操作受限的线性表：先进先出

• 应用场景：生产者、消费者；搜索最短路径

二叉排序树

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

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

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

平衡二叉（排序）树

• 从任何一个节点出发，左右子树高度相差不超过1

• 左右子树也是平衡二叉树

• 插入时，最多只需要两次旋转就会重新恢复平衡

• 删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度 O(logN)

红黑（排序）树

• 每个节点为两种颜色之一：红或黑

• 根节点为黑色

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

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

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

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

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

• 在大量增删的情况下，效率比平衡二叉树高

• 平衡性不如平衡二叉树，查找效率比平衡二叉树低一些



常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

• 遗传算法

网络通信协议

OSI七层模型和TCP/IP四层模型



• 物理层

• 链路层（数据链路层负载均衡）

• 网络层（IP协议，IP负载均衡）

• 传输层（TCP协议：三次握手，四次挥手）

• 应用层（HTTP协议）

非阻塞网络I/O

• 阻塞IO:进行IO操作时用户线程会一直阻塞,直到读操作或者写操作完成.

• 非阻塞IO:IO操作立即返回,发起线程不会阻塞等待。

• IO复用：select, poll, epoll

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

• PrepareStatement 预编译，提前生成执行计划，效率更好，并且可以防止 SQL 注入攻击

• 数据库连接池，减少反复建立连接的开销

• 聚簇索引：记录和索引存储在一起

• 非聚簇索引：叶子节点不记录数据行记录，而是主键。通过非聚簇索引找到主键，再通过主键索引找到行记录，该过程也称作回表。

• 添加必要的索引优化 SQL 查询性能

• 不要盲目添加索引，避免不必要的增删开销

• 事务日志，用于回滚（UNDO Log）或崩溃后恢复（REDO Log）