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

重复本次操作的方法