数据结构与算法

• 时间复杂度与空间复杂度

• 时间复杂度

• 算法执行语句的次数

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

• 多项式时间复杂度

• O(1)、O(log(n))、O(n^a)

• 非多项式时间复杂度

• O(a^n)、O(n!)

• 空间复杂度

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

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

• NP问题

• P问题

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

• NP问题

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

• NP ?= P

• NP-hard问题

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

• NP-hard问题可以解决一系列NP问题

• NP完全问题

• 是一个NP-hard问题，也是一个NP问题

• 基本的数据结构

• 数组

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

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

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

• 线性表、唯一的前区和后继

• 数组查找数据复杂度O(1)比链表查找数据复杂度O(n)好

• 链表

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

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

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

• 线性表、唯一的前区和后继

• 链表增删数据复杂度O(1)比数组增删数据复杂度O(n)好

• 数组链表结合

• 数组构建指针，记录链表头地址，快速定位链表

• 实现快速查找和快速删除

• Hash表（常用）

• 快速访问数据O(1)又快速增删数据O(1)

• Hash表本质就是数组，对key的hashcode对数组长度取模后得到Hash表索引（数组下标），然后取到对应数据

• Kv数据结构

• Hash冲突

• Hash表中实际存放的是数据指针，指针指向数据

• 相同指针需要遍历链表后得到数据

• Hash碰撞

• 栈

• 在线性表的基础上加入操作限制条件：后面添加的数据，在删除的时候必须先删除，即“后进先出”

• 受限的线性表

• 后进先出

• 队列

• 队列也是一种受限的线性表，栈是后进先出，而队列是先进先出

• 受限的线性表

• 先进先出

• 典型应用场景：生产者消费者；阻塞等待的线程被放入队列

• 应用

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

• 用队列搜索最短路径

• 树

• 二叉排序树

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

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

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

• 时间复杂度O(logn)

• 不平衡的二叉排序树

• 退化为链表

• 时间复杂度O(n)

• 平衡二叉（排序）树

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

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

• 时间复杂度O(logN)

• 旋转二叉树恢复平衡

• 插入时最多只需两次旋转就会重新恢复平衡

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

• 红黑（排序）树

• 红黑树为了解决平衡二叉树恢复平衡（删除）所带来的时间复杂度问题

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

• 根节点时黑色的

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

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

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

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

• 红黑树 VS 平衡二叉树

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

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

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

• 跳表

• 缺点空间复杂度高

• 常用算法

• 穷举算法

• 递归算法（快速排序算法）

• 要有退出函数，要不会Stack Overflow

• 死循环不断进栈出栈，不会栈溢出

• 时间复杂度n*log(n)

• 贪心算法

• 背包问题

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

• 迪杰斯特拉算法的核心是找到起点到每个节点的最快路径

• 算法

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

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

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

• 4、计算最终路径

• 动态规划算法

• 通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，从小问题的最优解，寻找大问题的最优解

• 解决背包问题

• 每个动态规划算法都从一个网格开始

• 遗传算法

• 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法

• 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索

• 遗传算法的遗传操作

• 选择

• 交叉

• 变异

• 遗传算法的核心内容（五要素）

• 参数编码

• 初始群体的设定

• 适应度函数的设计

• 遗传操作设计

• 控制参数设定

• 解决背包问题

• 基因编码与染色体

• 物品基因编码

• 基因组合：染色体

• 选择初始染色体：随机产生（也可以认为或者算法选择）

• 适应函数与控制函数

• 选择适应度函数，这里为商品总价值

• 总价值越大越适应

• 选择控制参数，这里为总重量

• 超重淘汰

• 选择算法

• 在剩下的染色体中选择可以被遗传下去的染色体以及繁殖次数

• 选择算法

• 轮盘赌选择

• 是一种回放式随机采样方法。每个染色体进入下一代的概率等于它的适应度值与整体适应度值和的比例

• 随机竞争选择

• 每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，知道选满为止

• 均匀排序

• 对群体中的所有个体按期适应度大小进行怕许，基于这个排序来分配各个个体被选中的概率

• 交叉遗传

• 选择结果

• 生产下一代：染色体交叉遗传

• 循环迭代，如果连续几代遗传都没有出现更强的染色体（价值总和更大），那么算法收敛，当前最大价值的染色体为最终解

• 有时候会在遗传过程中进行基因突变，得到基因突变染色体

• 遗传算法有可能得到的不是最优解

网络通信协议

• Web请求的一次网络通信历程（多次网络通信过程）

• 客户端-->DNS

• DNS（获取IP地址）

• 静态资源解析（图片、静态文本）--> CDN

• 动态资源解析（订单、搜索列表）--> 数据中心负载均衡服务器

• CDN--> 数据中心负载均衡服务器

• 数据中心负载均衡服务器-->反向代理服务器

• 反向代理服务器-->负载均衡服务器

• 负载均衡服务器-->网关服务器

• 网关服务器-->微服务服务器

• 微服务服务器

• -->数据库服务器

• -->缓存服务器

• 数据库服务器

• 缓存服务器

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

• OSI七层模型

• 应层层

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

• 表示层

• 负责转化数据格式，并处理数据加密和数据压缩

• 会话层

• 负责管理网络中计算之间的通信，提供传输层不具备的连接相关功能

• 传输层

• 提供端对端的接口

• 网络层

• 为数据包选择路由

• 数据链路层

• 传输有地址的帧以及错误检测功能

• 物理层

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

• TCP/IP四层模型

• 应用层

• HTTP协议

• HTTP请求的七种方法

• Get

• 只读请求

• Web应用不应因为get请求而发生任何状态改变

• Head

• 和get方法一样，只返回响应头

• Post

• 提交请求

• Put

• 上传请求

• Delete

• 删除URL标识的资源

• Trace

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

• Options

• 请求服务器返回支持的所有HTTP请求方法，测试服务器是否正常

• HTTP响应的五种状态

• 1xx消息

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

• 2xx成功

• 请求已成功被服务器接收、理解、并接受

• 3xx重定向

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

• 4xx请求错误

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

• 5xx服务端错误

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

• HTTP协议版本

• HTTP/1.0

• 1996年发布，客户端和服务端之间交换的每个请求/响应都会创建一个新的TCP连接，这意味着所有请求之前都需要进行TCP握手连接，因此所有请求都会产生延迟

• HTTP/1.1

• 保持、复用TCP连接

• 不能并发，每次只能响应一个请求，网络层上获得并发能力的唯一方法是并行使用多个TCP连接

• HTTP/2

• 引入HTTP“流”的概念，允许将不同的HTTP并发地复用到同一TCP连接上，使浏览器更高效地复用TCP连接

• TCP并不理解HTTP流，当多个HTTP请求复用一个TCP连接，如果前面的请求/响应没有处理完，后面的请求/响应也无法处理，会出现队头堵塞现象

• HTTP/3

• 不使用TCP作为会话的传输层，而是使用QUIC（一种新的互联网传输协议）

• QUIC协议在传输层将流作为一等公民引入

• 多个QUIC流共享相同的QUIC连接，因此不需要额外的握手和慢启动来创建新的QUIC流

• QUIC流是独立的，因此在大多数情况下，只影响一个流的丢包不会影响其他流，这是因为QUIC数据包缝状在UDP数据包

• 传输层

• TCP协议

• 面向连接的、可靠的、基于字节流的传输层协议

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

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

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

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

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

• 建立连接三次握手

• 1、客户端--（SYN=1，Seq=X）-->服务端

• 2、客户端<--（SYN=1，ACK=X+1，Seq=Y）--服务端

• 3、客户端--（ACK=Y+1，Seq=Z）-->服务端

• 关闭连接四次挥手

• 1、主动方--（FIN=1，seq=m）-->被动方

• 2、主动方<--（ACK=1，seq=m+1）--被动方

• 3、主动方<--（FIN=1，seq=n）--被动方

• 4、主动方--（ACK=1，seq=n+1）-->被动方

• UDP协议

• 网络层

• IP协议使得互联网应用根据IP地址就能访问到目标服务器

• 网络层数据交给数据链路层进行处理，数据包必须小于MTU才能进行网络传输

• IP头

• 记录发送者和接收者的IP地址

• IP负载均衡

• 负载均衡服务器转发时修改数据包中的源IP地址为负载均衡IP地址，目标IP地址为目标应用服务器

• 应用服务器回包时数据包中的源IP地址为应用服务器IP地址，目标IP地址为负载均衡服务器IP地址

• IP协议不是一个可靠的通信协议，不会建立稳定的通信链路，不会确保数据一定到达

• 网络访问（链路）层

• 数据链路层

• 将数据封装成数据帧

• 在帧上进行数据校验，进行流量控制

• 定义最大传输单元MTU（帧大小）

• 帧头

• 记录发送者和接收者的MAC地址

• 数据链路层负载均衡

• 负载均衡服务器修改数据帧帧头目的mac地址为某个应用服务器的mac地址

• 集群内应用服务器与负载均衡服务器IP地址一致

• 物理层

• 数据的物理传输

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

非阻塞网络I/O

• 计算机之间如何进行网络请求

• 操作系统Socket编程

• Socket启动监听端口

• Socket数目是Socket连接数目+1

• 端口

• 服务端

• 客户端

• 单线程服务器-客户端

• 两个socket

• 监听端口的socket

• new serverSocket

• 绑定端口

• 建立连接的socket

• Socket socket = serverSocket.accept()

• 多线程服务器-客户端

• 主线程负责连接

• Socket socket = serverSocket.accept()

• 其他线程

• new Thread().start()

• 一个连接一个Socket一个线程

• Socket接收数据，系统内核的处理过程

• 应用只能对Socket中的接收缓冲区和发送缓冲区进行操作

• Socket.getinputStream()

• Socket.getOutputStream()

• 非阻塞I/O（Non-Blocking I/O）

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

• 非阻塞read操作

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

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

• 非阻塞write操作

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

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

• 应用线程是否会被阻塞

• Java NIO（New I/O）

• 是有阻塞的

• 四个关键角色

• Selector

• Buffer

• SelectableChannel

• Channel == Socket

• SelectionKey

• OP_READ

• OP_WRITE

• OP_CONNECT

• OP_ACCEPT

• 过程

• Selector检查每个Channel通道时间（轮询），根据SelectionKey进行相应处理

• 这里面的Buffer是应用管理

• 一个线程解决多个连接请求

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

• Select（poll）管理下的read过程

• epoll管理下的read过程

• 无活动连接时，Selector.select方法被阻塞

数据库架构

• PrepareStatement预编译

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

• 可以防止SQL注入攻击

• 数据库架构

• -（SQL）->连接器->语法分析器->语义分析与优化器->执行引擎

• 连接器

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

• 应用程序启动的时候，通常会初始化一些数据库连接放在连接池里，当处理外部请求执行SQL操作的时候，就不用建立连接了

• 语法分析器

• 语法树

• 语义分析与优化器

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

• 执行计划

• Key：索引类型，NULL无索引

• Rows：需要处理的行数

• Possible_keys：潜在可以利用的索引

• B+树

• 聚簇索引

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

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

• 非聚簇索引

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

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

• 索引

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

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

• 合理使用索引

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

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

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

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

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

• int 4字节

• bigint 8字节

• Timestamp 4字节

• Datetime 8字节

• 数据库事务ACID

• 数据库事务日志

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

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

• TransID：产生操作的事务ID

• PageID：被修改的数据在次盘上的位置

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

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

• REDO：重复本次操作的方法