第 8 周总结: 数据结构与算法，网络与数据库

数据结构与算法

时间复杂度

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

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

多项式的时间复杂度 数据n在表达式的下方 O(1) O(log(n)) O(n^a)

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

空间复杂度

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

O（n）表示需要临时存储n个数据



NP问题

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

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

NP-hard：比NP问题更难的问题（NP问题的解法可以规约到NP-hard问题的解法）

NP完全问题：是一个NP-hard问题，也是一个NP问题



数组

数组的特性

• 创建数组必须要内存中一块连续的空间

• 数组中必须存放相同的数据类型

因为数组的这两个特性，所以数组支持随机快速读写。数组可以根据第一个数据的内存地址和数据类型，推导出任意下标的内存地址。根据下标访问数据，时间复杂度为O(1)。

在数组中删除数据（不是数组末尾的数据）到导致数据迁移，时间复杂度为O(n)。



链表

链表的特性

• 链表可以用零散的内存空间存储数据

• 链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针

要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(N)。

总体来说，在链表中增删数据要比数组性能好很多。



Hash表

hash表本质是一个数组。

数据存入hash表的过程：数据以key value的方式存储在hash表中。先计算key的hash值，然后用hash值和hash表的长度取模,余数就是hash表的下标。如果这个下标地址已经存入了数据，那么新数据会放在老数据后面，形成一个链表。

哈希碰撞攻击就是，针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表，哈希表的各种操作的时间复杂度提升一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（Dos）的目的。



栈

栈的特性

操作受限的线性表

“先进后出”

典型应用场景，线程调用栈



队列

操作受限的线性表

“先进先出”

典型应用场景，生产消费者队列

例子 用队列搜索好友关系最近的有钱人，用队列搜索最短路径



树

二叉排序树

左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它根结点的值。

不平衡的二叉排序树

平衡二叉排序树

旋转二叉树恢复平衡



红黑树（排序树）



红黑树vs平衡二叉树

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

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

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



跳表



常用算法

穷举算法

递归算法

贪心算法

动态规划



递归算法用于实现快速排序，时间复杂度为n*logn



迪杰斯特拉算法（最快路径）是改进的贪心算法。



动态规划解决背包问题。



遗传算法解决背包问题。



网络通信协议

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



物理层

在真正的通信线路里有光纤，电缆，无线各种设备。光信号和电信号以及无线电磁信号在物理上是完全不同的，如何让这些不同的设备能够理解，处理相同的二进制数据，这是物理层要解决的问题。

电信号用高电压和低电压表示0 和 1 。



链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被称为最大传输单元。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。



链路层可以使用数据链路层负载均衡。



网络层（IP协议）

网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的IP数据包必须要小于最大传输单元才能进行网络传输。

网络的数据包会定义一个IP头，这个IP头里包含了网络层的元信息，包括发送者和接受者的IP地址。



网络层可以使用IP负载均衡。



传输层（TCP协议）

IP协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议TCP。



TCP协议是一种面向连接的，可靠的，基于字节流的传输层协议。

有很多重要的机制保证了TCP协议的可靠性和强壮性：

• 使用序号，对收到的TCP报文进行排序和检测重复的数据

• 无错传输，使用校验和检测报文段的错误

• 使用确认和计数器来检测和纠正丢包或者延时

• 流量控制，避免主机分组发送的过快而使接收方来不及完全收下

• 拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃丢失包的重传



TCP建立连接的三次握手，关闭连接的四次挥手。



应用层Http协议

Http请求的7种方法：get,post,put,delete,head,trace,options

Http响应的5种状态

1XX: 消息 请求已被接收，继续处理

2XX: 成功

3XX：重定向

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

5XX：服务器错误



Http协议回复的格式



Http协议的版本，1.0，1.1, 2 ,3。各个版本的区别，解决了什么问题。



非阻塞I/O

BIO：进行I/O操作时，用户线程会一直阻塞，直到读操作或写操作完成



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



非阻塞read操作:

• Socket接收缓冲区有数据，读n个（不保证数据被读完整，因此有可能需要多次读）。

• Socket接收缓冲区没数据，则返回失败（不会等待）。

非阻塞write:

• Socket发送缓冲区满，返回失败（不会等待）。

• Socket发送缓冲区不满，写n个数据（不保证一次性全部写入,因此可能需要多次写）。



Java NIO（New IO）的核心类：Selector,SelectableChannel,Buffer,SelectionKey



系统I/O复用的方式：select,poll,epoll



数据库架构原理与性能分析



数据块架构：连接器，语法分析器，语义分析与优化器，执行引擎。

这四个部分是解耦的，每个部分可以重新开发，用其他独立开发的一样功能的模块替换。比如开源社区就为mysql开发了很多执行引擎，innodb引擎就是其他公司开发的，后来被mysql放进了发行包中，作为默认引擎。



连接器

数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连

接对数据库而言相对比较重，需要花费一定的时间/因此应用程序启动的时候，通常会 初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行SQL操作的时候' 就不需要花费时间建立连接了。



语义分析与优化器

语义分析与优化器就是要将各种复杂嵌套的SQL进行语义等价转化，得到有限几种关系 代数计算结构，并利用索引等信息进一步进行优化。



为什么 PrepareStatement 更好

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

• PrepareStatement可以防止SQL注入攻击



聚簇索引

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

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



非聚簇索引

非聚簇索引在叶子节点记录的就不是数据行记录，而是聚簇索引，也就是主键。 通过非聚簇索引找到主键索引/再通过主键索引找到行记录的过程也被称作回表。



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

在几百万行的数据库中查找一个条记录/如果没有索引,就需要全表扫描，检索所有的 行记录，才能找到需要的记录。



谨慎使用索引

不要盲目添加索引，尤其在生产环境中

•添加索引的alter操作会消耗较长的时间（分钟级）

• Alter操作期间，所有数据库的增删改操作全部阻塞，对应用而言，因为连接不能释放，事实 上，查询也被阻塞。

删除不用的索引,避免不必要的增删开销

使用更小的数据类型创建索引



数据库事务

事务特性ACID

•原子性(Atomicity): 事务要么全部完成，要么全部取消。如果事务崩溃，状态回到事 务之前(事务回滚)。

•隔离性(Isolation): 如果2个事务T1和T2同时运行，事务T1和T2最终的结果是相同 的，不管T1和T2谁先结束，隔离性主要依靠锁实现。

•持久性(Durability): 一旦事务提交，不管发生什么(崩溃或者出错)，数据要保存在数 据库中。

• 一致性(Consistency): 只有合法的数据(依照关系约束和函数约束)才能写入数据库。



数据库事务日志

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



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

TransID:产生操作的事务ID。

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

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

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

REDO:重复本次操作的方法。