架构第八周总结

数据结构与算法

• 时间复杂度

算法执行语句的次数。

• 空间复杂度

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



NP 问题

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

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

• NP-hard：NP 问题的解法可以规约到 NP-hard 问题的解法

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



数组

• 内存中一块连续的空间

• 相同的数据类型

• 随机快速读写，时间复杂度 O(1)



链表

• 零散的内存空间存储数据

• 每个数据元素包含一个指向下一个数据元素的内存地址指针

• 查找需要遍历链表，O(N)



链表中增删数据要比数组性能好的多

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



Hash 表

• Hash 表 key 冲突



栈

• 后进先出

• 线程栈



队列

• 先进先出

• 生产者消费者



树

• 二叉排序树

• 平衡二叉排序树

• 选择二叉树恢复平衡

• 红黑（排序）树



红黑树 VS 平衡二叉树

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

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

• 红黑树的平衡性不如平衡二叉树，查找效率要差一些



跳表



常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划



遗传算法



网络通信协议



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

• 物理层

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

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

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

• 应用层（HTTP 协议）



网络数据包格式



非阻塞网络 I/O

• 线程池服务器

• BIO

• 非阻塞 I/O

• Java NIO(NEW I/O)

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



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

• PrepareStatement 预编译

• 数据库架构（连接器，语法分析器，语义分析与优化器，执行引擎）



为什么预编译更好

• 效率高

• 防止 SQL 注入攻击



B-树和 B+树



聚簇索引

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

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



非聚簇索引

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

• 通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程也被称作回表



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



谨慎使用索引

• 不要盲目添加索引，尤其在生产环境中

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

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



数据库事务

• ACID

• 数据库事务日志