数据结构

数组

• 创建数组必须要内存中一块连续的空间，所以可以根据下标直接定位到指定数据

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

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

链表

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

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

• 要想在链表中查找数据只能遍历链表，所以链表查找的时间复杂度是 O(N)

Hash 表

• 数组链表结合，实现快速查找和快速增删

栈

• 线性表：一个元素可以同时拥有一个前驱和一个后继节点，形成连续数据被称为线性表

• 数组和链表都被称为线性表

• 栈就是线性表基础上加了操作限制条件：后面添加的数据，在删除的时候必须先删除，也就是常说的先进后出，例如线程栈的实现

队列

• 队列也是一种操作受限的线性表，需要满足先进先出条件

树

• 二叉排序树

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

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

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

• 平衡二叉树

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

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

• 旋转二叉树恢复平衡

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

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

• 红黑树

• 目的是为了减少插入和删除的时间复杂度

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

• 根节点是黑色的

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

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

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

• 红黑树 vs 二叉平衡树

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

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

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

• 跳表

• 时间复杂度 O(logN)，空间复杂度 O(N)

网络通讯协议

一次 web 请求的通讯历程

• 客户端需要通过域名基于 TCP/IP 协议进行访问

• 通过 DNS 将域名解析为 IP 地址，IP 地址有两种

• 静态资源：图片，js，css，解析出来 CDN 地址

• 动态请求：如下单，搜索，解析出来负载均衡服务器 IP 地址

• 负载均衡服务器将请求分发给反向代理服务器，反向代理服务器将请求分发给网关服务器

• 网关服务器调用微服务，微服务从数据库拉取数据

TCP/IP 协议

• 互联网开发主要使用的是 TCP/IP 协议

• TCP/IP 协议是四层模型

• Http 协议是 TCP 协议的应用层，包含了 OSI 七层协议中的应用层，表示层和会话层

• 会话层：负责管理多次网络间的会话链接

• 表示层：数据都是以二进制比特流的方式传递，如何提取其中有效信息，解析数据格式是由表示层控制的，包括数据加密、压缩也是在表示层完成

• 应用层：访问接口

• 应用层之下依赖的是传输层，常用 Tcp 协议，有时也用 Udp 协议。

• 链路的传输，数据的包装都在传输层，提供端对端的访问，也就是服务器上哪个进程监听请求的端口并进行响应。

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

• Tcp 协议是一种面向连接的、可靠的、基于字节流的传输层协议。Tcp 作为一个比较基础的通讯协议，有很多重要的机制保证了 Tcp 协议的可靠性和强壮型

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

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

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

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

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

• 传输层之下依赖网络层，网络层主要使用 IP 协议，选择网络传输最优路径，IP 地址属于网络层，通过 IP 地址进行网络路由分发，最终到达目标服务器，目标服务器处理完毕后根据原来 IP 地址的路由列表，再将响应结果的数据包返回。

• 网络层之下是链路层，主要用于在物理媒介上（如光纤）传输二进制数据，主要将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧就可以在帧上进行数据校验和流量控制。链路层会定义帧的大小，这个大小也被称为最大传输单元。像 Http 要在传输的数据上添加一个 Http 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受着的 mac 地址。mac 地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

• Tcp 包包含 Http 包主要添加的是端口，IP 层数据包包含 Tcp 包主要增加 IP 地址，链路层包含 IP 数据包主要添加 mac 地址，通过物理层进行数据传递，再逆序根据每一层拆包，最终解析 Http 包，得到需要的数据

• Http 中的 post 请求是根据 body 长度来判断数据是否接受完成，也就是已接受数据长度 = Http 包中的 body-length 就以为着数据接受完成，服务器可以进行处理了

• Http 协议格式

非阻塞网络 IO

BIO

• 服务器会 new 一个 socket，利用这个 socket 监听通讯端口，即 socket.accept();

• 当客户端发起请求后，服务端通过监听端口收到请求，会新创建一个 socket，客户端和服务器使用这个新的 socket 进行通讯

• 服务器接收客户端数据时使用 socket.getInputStream().read(); 此时如果数据没有到达或到达完全，当前线程会被阻塞

• 服务器响应客户端数据时使用 socket.getOutputStream().write(); 此时如果 socket 缓存区写满，当前线程会被阻塞

NIO

• 一个 channel 对应一个 socket

• selector 选择器用于查询所有 channel 上发生的事件

• buffer 数据写入

• selectKey 对应 accept，read，write 操作，也就是每个 socket 上发生的事件

数据库架构原理

• 连接器：数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较重，需要话费几百毫秒时间，因此应用程序启动的时候，通常会初始化一些连接放在数据库连接池里，这样当处理外部请求 SQL 时就无需话费时间建立连接了

• 语法分析器：将需要执行的 SQL 语句解析成一颗语法树，解析时会对 SQL 进行检查

• 语义分析与优化器：将各种复杂嵌套的 SQL 进行语义转化，得到优先级中关系代数计算结构，并利用索引等信息进一步优化

• 执行计划 Explain：Key：类型索引，NULL 无索引，Rows：需要处理行数，Prossible_keys：潜在可以利用的索引

为什么使用 PrepareStatement 更好

• PrepareStatement 会预先提交带占位符的 SQL 到数据库进行预处理，执行多条 SQL 只会编译一次，提前生成执行计划，当给定占位符参数真正执行的时候，执行引擎可以直接执行，速度会更快

• PrepareStatement 可以防止 SQL 注入攻击