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

今周的主题继续是性能优化

数据结构与算法

时间复杂度与空间复杂度

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



空间复杂度是算法运行过程中临时占用的存储空间大小的量度



NP问题

• P：能在多项式时间复杂度内解决的问题

• NP：能在多项式时间复杂度内验证答案正确与否的问题（例如数独）

• NP-hard 问题：比 NP 问题更难的问题（NP问题的解法可以规约到 NP-hard 问题的解法）

• NP 完全问题：是一个 NP-hard 问题，也是一个 NP 问题



数组

• 连续的内存空间

• 存放相同类型的数据

• 随机快速读写，根据下标访问，时间复杂度 O(1)



链表

• 可以使用零散的内存空间

• 每个元素包括指向下一个元素的指针

• 不能随机访问，需要顺序访问，时间复杂度 O(N)

• 增删数据比数组更容易，不需要搬动原有数据

• 数组链表结合，实现快速查找和快速增删



Hash 表

• 快速访问

• 快速增删

• key 可能发生冲突



栈

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

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

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



队列

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

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



树

二叉排序树

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

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

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



平衡二叉（排序）树

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

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

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

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



红黑（排序）树

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

• 根节点为黑色

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

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

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

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

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

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

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



跳表

• 降低已排序链表的查找时间复杂度（每次跳过更多的元素）

• 空间复杂度更高（空间换时间）



算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

• 遗传算法



网络通讯协议

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



非阻塞网络 I/O

• I/O 操作立即返回，发起线程不会阻塞等待

• 系统 I/O 复用方式：select, poll, epoll



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

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

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

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

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

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

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

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



总结

性能优化是个很大的话题

• 首先要有判断是否达到优化目标的性能指标

• 围绕性能指标选择技术方案时，需要综合权衡。不同的方案有不同的折中取舍，而这些取舍有时不是技术团队能决定的，技术选型和架构决策需要依赖业务规划甚至企业的战略规划，离开业务发展的支撑和驱动，技术走不远，甚至会迷路

• 前沿技术是由前沿业务催生的

• 新技术的出现又会驱动企业开展新的业务



因此架构师不仅仅要技术全面，还要有业务发展的前瞻性。