1. 数据结构与算法

2. 网络通信协议

3. 非阻塞网络 IO

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

数据结构与算法

数据结构

常见的数据结构有数组、链表、树

算法是在这些数据结构上对数据进行操作的一系列动作

评判算法好坏有两个维度，时间复杂度和空间复杂度

时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数和数据量的关系

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

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

空间复杂度

• 一个算法在运行过程中临时占用存储空间的大小的标尺

• O(n)表示要处理的数据量为 n，需要另外 n 个单位的存储空间

常见的时间空间复杂度有 O(1),O(log(n)),O(n),O(nlog(n)),O(n^2),O(n^3),O(2^n),O(n!)

NP 问题

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

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

NP 问题范围包含 P 问题

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

NPC：可以规约到 NP-hard 问题的 NP 问题就是 NPC 问题。

数组

数组的存储需要一块连续的空间，存储的内容是相同的数据类型。

数组的一个重要特性是随机快速读写，根据数组下标访问数组数据，时间复杂度为 O(1)

链表

链表使用非连续内存空间。

链表中的节点都包含指向下一个节点的地址，最后一个节点指向 null

查找链表中的元素，只能遍历链表，所以链表的查询时间复杂度为 O(1)

链表中替换删除等操作很简单，找到元素后，时间复杂度为 O(1)

Hash 表

hash 表结合了数组和链表

hash 表中，key 和 value 组成一个 Map.Entry

hash 表根据 key 计算 hash 值，然后与数组长度做余数 hash，hash 值为 Entry 需要放入的位置

若计算出的数组位置有值，即存在冲突的情况下，则把 Entry.next->原 Entry，array[hash]=Entry

栈

数组和链表是线性表

栈也是一种线性表

栈被规定只能在栈顶做操作：入栈和出栈

栈具有的特点被称为后进先出

线程调用使用的数据结构是栈，存储的元素是栈帧

队列

队列也是线性结构

队列有队头和队尾，操作有：入队和出队，从队尾入队，队头出队

队列的特点是先进先出

典型的应用场景是生产者消费者模型

使用队列搜索出好友中关系最近的有钱人

使用队列搜索最短路径

树

树的节点类型有：根节点，叶子节点，普通节点

节点间的关系有：父节点、子节点、兄弟节点、祖先节点、子孙节点

二叉排序树

树上的一个节点最多有两个子节点

左子树的值小于或等于根节点

右子树的值大于根节点

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

二叉排序树在不平衡的情况下，退化为链表

平衡二叉（排序）树

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

左右子树仍然为平衡二叉树

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

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

红黑（排序）树

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

根节点都是黑色

每个叶子节点（NIL）都是黑色的空节点

从根节点到叶子节点，所有路径上，不会出现两个红色节点相连的路径

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

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

红黑树 VS 平衡二叉树

• 红黑树最多通过三次旋转就可达到红黑树再次平衡，时间复杂度为 O(1)，平衡二叉树最多是 lO(og(n))

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

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

跳表

对于一个有序链表，不断加大 step，生成一个长度变小的链表

通过查找小的链表，提高查找数据的效率

常用算法

1. 穷举算法

2. 递归算法

3. 贪心算法

4. 动态规划

穷举算法

使用列举出所有情形的方法，找出最优解

递归算法

在快速排序中，使用了递归算法

递归算法要有退出条件，以及递推工时

算法的时间复杂度为 O(n*log(n))

贪心算法

通过获得每一步的最优解来获取整体最优解

贪心算法获得的整体最优解不是数学上的最优解

迪杰斯特拉算法

改进的贪心算法，在最短路径中的使用

1. 找出“最便宜”的节点，即可在最短时间内到达的节点

2. 更新该节点邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销

3. 重复该过程，直到对图中的每个节点都这样做了

4. 计算最终路径

动态规划

动态规划解决背包问题

使用网格，横轴是限制条件，单位按实际刻度来

纵轴是可选物品，可按照价值高低升序排序

从上往下开始填表格，填写在当前限制和物品下的最佳组合

最后在右下角得出最佳组合

遗传算法

遗传算法的遗传操作

• 选择

• 交叉

• 变异

遗传算法的核心内容

• 参数编码

• 初始群体的设定

• 适应度函数的设计

• 遗传操作设计

• 控制参数设定

遗传算法的特点：得到的解不是最整体最优解，是局部最优解

网络通信协议

网络协议在设计时，分层

有两种分层方式

OSI 的标准七层，TCP/IP 的实用四层

OSI 七层

1. 物理层（Physical Layer）

2. 数据链路层（Data Link Layer）

3. 网络层（Network Layer）

4. 传输层（Transport Layer）

5. 会话层（Session Layer）

6. 表示层（Presentation layer）

7. 应用层（Application Layer）

TCP/IP 四层

1. 网络访问（链路）层（Network Access（Link）Layer）

2. 网络互联层（Intennet Layer）

3. 传输层（Transport Layer）

4. 应用层（Application Layer）

OSI 与 TCP 对应关系

1. 1,2 == 1

2. 3 == 2

3. 4 == 3

4. 5,6,7 == 4

网络数据包格式

1. 链路层协议头

2. IP 协议头

3. TCP 协议头

4. HTTP 协议头

以上协议头从外到内

TCP 三次握手

1. 客户端先发送 SYN=1，Seq=X 的报文，请求建立连接，X 是一个随机数

2. 服务端收到这个报文后，应答 SYN=1，Seq=Y，ACk=X+1，表示同意建立连接

3. 客户端收到报文后，检查 ACK 的值是否为 X+1，确认连接，并发送 ACK=Y+1 的报文给服务器；服务器收到报文后，确认 ACK 值为自己发送的 Seq+1，确认建立连接

通过以上散步，TCP 连接建立

TCP 四次挥手

1. 主动方发送一个 FIN，seq=m，请求关闭连接

2. 被动方收到主动方的 FIN，回应主动方发送一个 ACK，其中 ack=m+1

3. 被动方向主动方发送 FIN 码，seq=n

4. 主动方收到被东方的 FIN，回应主动方一个 ACK 码，ack=n+1

HTTP 请求的七种方法

1. GET

只读请求，不产生副作用，服务端无状态变更

1. POST

提交请求，一般用于创建

1. PUT

上传请求，一般用于变更

1. DELETE

删除 URL 标识的资源

1. OPTIONS

请求服务器所支持的方法，测试服务器是否正常

1. TRACE

回显服务器收到的请求，用于测试或者诊断

1. HEAD

和 GET 类同，但是只返回响应头

HTTP 响应的五种状态

1. 1XX

请求已被服务器接收，继续处理

1. 2XX

请求已成功被服务器接收，理解，处理

1. 3XX

需要后续操作才能完成这一请求

1. 4XX

请求含有词法错误或者无法被执行

1. 5XX

服务器在处理某个正确请求时，发生错误

HTTP 协议版本

1. HTTP/1.0

客户端请求到资源后，关闭连接。并发量大的时候，会频繁的创建、关闭 TCP 连接，而 TCP 三次握手，四次挥手会消耗一定的时间

1. HTTP/1.1

默认启用长连接，客户端可以用一个 TCP 连接默认发送多个请求，引入了管道机制，客户端不用等上个请求得到响应就可以发送下个请求，但服务端是按照请求的顺序进行响应，半双工模式

1. HTTP/2

复用 TCP 连接的方式不同，依然遵循请求响应模式，但客户端发送多个请求和服务端给出多个响应的顺序不受限制，既避免“队头阻塞”，又能更快获取响应，全双工模式

非阻塞网络 IO

BIO

BlockingIO，阻塞 IO，一个线程服务一个 Socket 连接，处理读写关闭时间

read、write 时，请求被阻塞，等待数据到达内核并从内核态复制到用户态

NIO

Non-Blocking I/O

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

系统 I/O 复用方式

1. select

2. poll

3. epoll

说下对非阻塞的理解，BIO 时代，之所以阻塞，是 I/O 时间内核没有通知用户线程。当内核有了通知用户线程的机制，只需用户注册感兴趣的 I/O 事件到内核，内核感知连接上是否可读、可写。可读时，把数据放入读取缓冲区，可写时，通知用户继续写（写有带宽以及 TCP 连接上拥堵限制等）。请求连接时，通知用户常见一个连接 Socket，处理读、写、关闭等操作。

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

数据库组成

1. 连接器

为每个连接分配一块内存空间，用于连接回话上下文管理。连接对数据库来说是一个重操作，消耗高，一般会在应用服务启动后，就会创建几个连接缓存着供后续传输 SQL 使用

1. 语法分析器

分析 SQL 语句，生成 SQL 语法树，可检查 SQL 是否正确

1. 语义分析与优化器

将各种复杂嵌套的 SQL 进行语义等价转化，得到有限集中关系代数计算结构，利用表索引信息进一步优化

1. 执行引擎

根据执行引擎的不同，生成执行计划，执行

PrepareStatement

PrepareStatement 会预先提交带占位符的 SQL 到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行 SQL，执行引擎直接执行，效率更高，因为提前做了语法分析、语义分析与优化

B-树和 B+树

相比于 B-树，B+树非叶子节点不存储数据，所有的数据都存储在叶子节点，且叶子节点之间有链接

索引

聚簇索引

聚簇索引的数据库记录和索引在一起。典型的，像 MySQL 的主键索引就是聚簇索引

非聚簇索引

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

通过非聚簇索引找到聚簇索引，再通过聚簇索引找到行记录的过程，被称为回表

创建索引

优点

查找行记录表较慢，通过添加索引，提高查找效率

缺点

• 索引创建消耗时间长

• 创建索引时，所有数据库增删改操作全部阻塞，对应用来说，查询也表现为阻塞

• 索引占用存储空间

• 增删改数据时，要联动修改索引，维护不易

数据库事务

事务特性 ACID

1. 原子性（Atomicity）

事务要么全部完成，要么全部取消。如果事务崩溃，状态回到事务之前

1. 一致性（Consistency）

只有合法的数据（遵守关系约束和函数约束）才能写入数据库

1. 隔离性（Isolation）

两个事务 T1 和 T2 运行，事务 T1 和 T2 最终的结果是相同的，不管 T1 和 T2 谁先结束，隔离性主要依靠锁实现

1. 持久性（Durability）

一旦事务提交，不管发生什么（崩溃或者出错），数据要保存在数据库中

数据库事务日志

进行数据库事务日志操作时，事务日志文件会记录更新前的数据记录，然后再更新数据库中的记录。如果全部记录更新成功，那么事务正常结束；如果过程中某条记录更新失败，那么整个事务全部回滚，已经更新的记录根据事务日志中记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，仍然保持数据一致性。

事务日志组成

• LSN

一个按时间顺序分配的唯一事务记录日志序列号

• TransID

产生操作的事务 ID

• PageId

被修改的数据在磁盘上的位置

• PrevLSN

同一个事务产生的上一条日志记录的指针

• UNDO

取消本次操作的方法，按照此方法回滚

• REDO

重复本次操作的方法