数据结构

时间复杂度与空间复杂度

时间复杂度：并不是计算程序具体运行的时间，而是算法执行语句的次数

O(2^n)：表示对n数据处理需要进行2^n次计算

O(1),O(log(n)),O(n^a)：多项式时间复杂度

O(a^n)和O(n!)：非多项式时间复杂度



空间复杂度：一个算法在运行过程中占用存储空间大小的度量

O(n)：表示需要临时存储n个数据



数组

• 内存中一块连续的空间，存放相同类型的数据，通过数组下标访问数据，支持随机快速读写，时间复杂度O(1)。

链表

• 可以使用零散的内存空间来存储数据，链表中每个数据元素都包含指向下个数据元素的内存地址指针，查找时需要遍历链表，所以查询复杂度为O(n)。

数组VS链表、hash表

• 数组查找性能优于链表

• 链表增删数据性能优于数组

• 实现快速查找和快速增删，时间复杂度O(1)



• hash表



栈

• 在线性表（数据和链表）的基础上加上操作限制条件，后进先出。



队列

• 操作受限的线性表，先进先出

• 典型应用场景：生产者消费者



二叉排序树

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

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

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

平衡二叉（排序）树

• 从任何一个节点出发，左右子树深度之差的绝对值不超过1

• 左右子树仍然为平衡二叉排序树

• 旋转二叉树恢复平衡

• 插入时需要最多2次旋转，时间复杂度O(1)

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

红黑（排序）树

• 每个节点只有两种颜色：红色和黑色

• 根节点是黑色

• 每个叶子结点nil，都是黑色空节点

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

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

• 增删节点时，通过染色和旋转来保持红黑树定义，时间复杂度O(1)



红黑树VS平衡二叉树

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

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

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

常用算法

穷举算法

递归算法（快速排序）

时间复杂度O(nlogn)

贪心算法（迪杰斯特拉算法，最快路径）

动态规划算法（背包问题）







遗传算法

得到的不是最优解，时间复杂度O（1）

网络通讯协议

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

四层模型：应用层/传输层/网络层/链路层

网络数据包格式

链路层负载均衡

IP负载均衡

TPC建立连接的3次握手过程

非阻塞网络IO

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

数据库架构

PreparedStatement

• 提交带占位符的SQL到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行SQL的时候，执行引擎可以直接执行，性能更好一点。

• 防止SQL注入攻击

B+树

概念

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；

规则

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

（4）非叶子节点的子节点数=关键字数



聚簇索引

聚簇索引的数据库记录和索引存储在一起

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

非聚簇索引

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

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