架构师训练营 第 8 周总结

本周学习内容：

• 数据结构、算法

• 网络通信

• I/O

• 数据库架构原理和性能优化



1. 数据结构与算法

智慧老师说到：要做好架构设计，数据结构应该成为一种本能，而算法不必深究，了解大概便可。

常用的数据结构

• 数组，连续的内存空间，且须存相同的数据类型，适用于随机读写的场景，时间复杂度O(1)，但增删需要动态调整保持空间连续，影响性能，所以不适合增删场景；

• 链表，数据存储在零散的内存空间，且可以是不同的数据类型，读写只能通过顺序遍历定位，性能差，但增删是O(1)，所以适用于频繁增删数据的场景；

• Hash表，将key经过hash计算映射到数组索引，实现快速定位读写，且内存空间是固定的，不需要维持连续，除非在空间不够时需要动态扩容之类的，当key冲突时，可以转为链表存储；缺点是hash之后数据一般没办法填满内存空间，会有一定的内存浪费，如果是复杂的hash计算也可能损耗一定的性能；

• 栈，先入后出的结构，利用这种操作受限的特性，满足类似函数嵌套调用时需要保证后声明的函数先返回的要求；

• 队列，也是操作受限的结构，先入先出，典型场景是生产者与消费者模式，还可以利用在广度优先遍历，求最小路径的问题；

• 树，一种二维的结构，典型的有二叉树、二叉排序树、平衡二叉树，其中红黑树实现了近似平衡二叉树，因为维护平衡的代价太高；广泛应用在各种排序场景、数据库存储场景；



常用的算法

• 穷举：暴力求解；

• 递归：深度优先、广度优先，递归代码往往简洁、表现力强；

• 贪心：从局部最优可推导到全局最优；改进版本的贪心：迪杰斯特拉算法；

• 动态规划：动态递推，填表的方式，套路一般是找出存在的状态，定义状态转换方程，然后编码实现；典型问题：背包问题、股票问题、编辑距离等；

• 遗传算法：初始化数据后，通过选择、交叉、变异，不同调整参数，最终达到最优解，但可能不是全局最优；



1. 网络通信

OSI七层网络模型

• 物理层：二进制数据传输，交换机；

• 链路层：数据帧传输，以MAC地址为依据，会对数据进行错误检测，避免数据错漏；

• 网络层：IP包传输，IP协议；

• 传输层：开放端口，进行端对端传输，TCP/UDP协议；

• 会话层：连接功能；

• 表示层：转换数据格式、加密、数据压缩；

• 应用层：为应用服务提供访问网络的支持；



TCP/IP四层模型

• 链路层：对应OSI的物理层与链路层；

• 网络层：对应OSI的网络层；

• 传输层：对应OSI的传输层；

• 应用层：对应OSI的会话层、表示层、应用层；