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

数据结构与算法

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

• 空间复杂度：运行中临时占用的空间大小

• NP问题：

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

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

• NP-hard：比NP问题更难的问题

• NP完全问题

• 数组：存储在连续的内存空间，查询快捷，插入较慢。按下标查询时间复杂度O(1)

• 链表：可以使用零散的内存空间，查询较慢，插入较快。查找时间复杂度O(n)

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

• Hash表：数组加链表

• 栈：后进先出

• 线程调用栈

• 队列：先进先出

• 平衡二叉树：通过旋转保持平衡，时间复杂度O(logN)，查找较快

• 红黑树：最多3次旋转就会达成平衡，时间复杂度O(1)，适合增删较多场景，查找效率略差

• 跳表：通过多级索引提高查询效率

• 常用算法：

• 穷举算法

• 递归算法（快速排序）：时间复杂度，n * log(n)，可能导致栈溢出

• 贪心算法（改进-迪杰斯特拉算法-最快路径）

• 动态规划

• 遗传算法

网络通信协议

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

• 物理层：在物理媒介上传输二进制格式数据

• 数据链路层：传输有地址的帧及错误监测功能

• 链路层负载均衡

• 网络层（IP）：为数据包选择路由

• IP负载均衡

• 传输层（TCP）：提供端对端接口

• TCP3次握手，4次挥手

• 会话层：管理网络中计算机之间的通讯，提供传输层不具备的连接相关功能

• 表示层：转化数据格式，并处理数据加密与数据压缩

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

• HTTP协议

非阻塞网络I/O

• BIO 阻塞I/O

• 非阻塞I/O

• Java NIO

• Selector

• SelectableChannel

• SelectionKey

• Buffer

• 系统I/O复用方式：select、poll、epoll（event poll）

数据库原理与性能优化

• 数据库架构：

• 连接器（连接池）

• 语法分析器（校验错误）

• 语义分析与优化器（语句等价转化、利用索引优化）

• 执行引擎（执行计划、分析性能）

• prepareStatement预处理，效率更好

• B-树与B+树

• 聚簇索引：索引和数据存储在一起

• 非聚簇索引：叶子节点存储的是主键，通过主键索引找到记录

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

• 谨慎使用索引

• 数据库事务ACID

• 数据库事务日志