本周主要介绍了数据结构和算法的相关知识以及网络通信协议、非阻塞网络I/O以及数据库架构原理相关知识。

1       数据结构和算法

1.1     时间复杂度与空间复杂度

-时间复杂度：

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

通常用O(n)来体现算法时间复杂度的记法被称作大O表示法：

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

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

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

       常见时间复杂度的比较：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

常见排序算法的时间复杂度：





-空间复杂度：

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

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

1.2     NP问题

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

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

NP-hard：比NP问题更难的问题( NP问题的解法可以规约到NP-hard问题的解法)。

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

疑问：NP等于P吗？

1.3     线性表

线性表：0个或者多个数据元素的有限序列。

性表的两种存储结构：顺序存储结构和链式存储结构。

顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。

链式存储结构：地址可以连续也可以不连续的存储单元存储数据元素





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

1.4     数组

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组结构有以下约束：

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

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

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



数据的插入和删除很低效：

•如果删除数组末尾的数据，最好情况时间复杂度为 O(1)

•如果删除开头的数据，则最坏情况时间复杂度为 O(n)

•平均情况时间复杂度也为 O(n)。

1.5     链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

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

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

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

链表中增删数据要比数组性能好的多。





可以结合数组和链表各自的有点，实现快速查找和快速增删：





1.6     Hash表

Hash表也叫散列表，是一种线性数据结构。

在一般情况下，可以用o(1)的时间复杂度进行数据的增删改查。

在Java开发语言中，HashMap的底层就是一个散列表。

使用Hash表结构，既快速访问数据，又快速增删数据：





1.7     Hash冲突

对于不同的输入值，Hash函数可能会给出相同的输出，这种情况就叫做Hash冲突。

哈希冲突是不可避免的，我们常用解决哈希冲突的方法有开放地址法和拉链法。

开放地址法：

在开放地址法中，若数据不能直接存放在哈希函数计算出来的数组下标时，就需要寻找其他位置来存放。

在开放地址法中有三种方式来寻找其他的位置，分别是线性探测、二次探测、再哈希法。

拉链法：





1.8     栈

栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。





线程调用栈：

线程调用栈是指某时刻时内存中线程调度的栈信息，当前调用的方法总是位于栈顶。

线程栈的内容是随着程序的运行动态变化的。





1.9     队列

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





典型应用场景：

-生产者消费者；

-阻塞等待的线程被放入队列（重量级锁是一种公平锁，它就是将等待的线程放入队列里的）。

-用队列搜索最短路径：





1.10   树

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。

没有结点的树称为空(null或empty)树。

一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。





树具有的特点：

（1）每个结点有零个或多个子结点

（2）没有父节点的结点称为根节点

（3）每一个非根结点有且只有一个父节点

（4）除了根结点外，每个子结点可以分为多个不相交的子树。

1.10.1    二叉排序树

二叉排序树，又称为二叉查找树。

在二叉查找树中，有以下特点：

（1）若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值。

（2）任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

（3）任意结点的左、右子树也分别为二叉查找树。

（4）没有键值相等的结点。





不平衡二叉树：





平衡二叉树：

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

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





旋转二叉树恢复平衡：

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

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



1.10.2    红黑（排序）树

红黑树是一种自平衡二叉查找树, 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保从根到叶子节点的最长路径不会是最短路径的两倍，用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决。

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

根节点是黑色的。

每个叶子节点(NIL)都是黑色的空节点。

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

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

红黑树多用于搜索,插入,删除操作多的情况下。





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





红黑树VS平衡二叉树：

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

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

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

1.11   跳表

增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。

跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。

跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

我们都知道，在一个有序的链表里面，查询跟插入的算法复杂度都是O(n)：





我们能不能进行优化呢，比如我们一次比较两个呢？那样不就可以把时间缩小一半？





同理，如果我们4个4个比，那不就更快了？





跳表就是这样的一种数据结构，结点是跳过一部分的，从而加快了查询的速度。跳表跟红黑树又有什么差别呢？既然两者的算法复杂度差不多，为什么Redis要使用跳表而不使用红黑树呢？

跳表相对于红黑树，主要有这几个优点：

1.代码相对简单，红黑树写起来很麻烦

2.如果我们要查询一个区间里面的值，用平衡树可能会麻烦。这里的麻烦指的是实现和理解上，平衡二叉树查询一段区间也是可以做到的。

3.删除一段区间，这个如果是平衡二叉树，就会相当困难，毕竟设计到树的平衡问题，而跳表则没有这种烦恼。

跳表的查询：

如下图，假如我们要查询11，那么我们从最上层出发，发现下一个是5，再下一个是13，已经大于11，所以进入下一层，下一层的一个是9，查找下一个，下一个又是13，再次进入下一层。最终找到11。





我们可以把查找的过程总结为一条二元表达式（下一个是否大于结果？下一个：下一层）。

跳表的插入：

插入的时候，首先要进行查询，然后从最底层开始，插入被插入的元素，然后看看从下而上，是否需要逐层插入。

可是到底要不要插入上一层呢？我们都知道，我们想每层的跳跃都非常高效，越是平衡就越好（第一层1级跳，第二层2级跳，第3层4级跳，第4层8级跳）。

但是用算法实现起来，确实非常地复杂的，并且要严格地按照2地指数次幂，我们还要对原有地结构进行调整。所以跳表的思路是抛硬币，听天由命，产生一个随机数，50%概率再向上扩展，否则就结束。这样子，每一个元素能够有X层的概率为0.5^(X-1)次方。

跳表的删除：

同插入一样，删除也是先查找，查找到了之后，再从下往上逐个删除。

跳表的缺点：空间复杂度比较高O(n)

1.12   常用算法

1.12.1    穷举算法

穷举算法是一种最简单的一种算法，其依赖于计算机的强大计算能力来穷尽每一种可能的情况，从而达到求解的目的。穷举算法效率不高，但适用于一些没有明显规律可循的场合。

穷举算法的基本思想就是从所有可能的情况中搜索正确的答案，其执行步骤如下:

(1)对于一种可能的情况，计算其结果。

(2)判断结果是否满足要求，如果不满足则进行执行第(1)步来搜索下一个可能的情况;如果满足要求，则表示寻找到一个正确的答案。

1.12.2    递归算法

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

1.12.3    贪心算法

贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解  。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。

虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。





改进的贪心算法-迪杰斯特拉算法(最快路径)：

是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

迪杰斯特拉算法的核心是找到起点到每个节点的最快路径，其过程如下：

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

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

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

4.计算最终路径。

算法过程示例：







1.12.4    动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

动态规划算法解决背包问题：

通过找到合适的角度，将所求解的目标值在某(几)个维度上展开，将一个大问题拆解

为若干小问题，小问题的最优解，寻找大问题的最优解。

算法过程示例：

问题如下：





每个动态规划算法都从一个网格开始，背包问题的网格如下：







2       网络通信协议

2.1     Web请求的一次网络通信历程





注意:

       上图中有两处负载均衡服务器，第一个是对反向代理服务器集群的负载均衡；另一个是对网关服务器集群的负载均衡。

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





互联网开发主要使用TCP/IP协议：



2.2.1      物理层

物理层负责数据的物理传输，计算机输入输出的只能是0 1这样的二进制数据，但是在

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

2.2.2      链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以

帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被称为最大传输单元。像HTTP要在传输的数据上

添加一个HTTP头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一

个重要信息就是发送者和接受者的MAC地址。MAC地址是网卡的设备标识符，是唯一

的，数据帧通过这个信息确保数据送达到正确的目标机器。

2.2.3      网络层

网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器，请求离开App 后，

到达运营服务商的交换机，交换机会根据这个IP地址进行路由转发，可能中间会经过很

多个转发节点，最后数据到达目标服务器。

网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络

层的IP数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个IP头，

主要包括的就是发送者和接受者的IP 地址。

2.2.4      传输层

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

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

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

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

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

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

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

2.2.5      网络数据包格式





2.3     TCP建立连接的3次握手过程





1.App先发送SYN=1, Seq=X的报文，表示请求建立连接，X是一个随机数;

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

3. App 收到这个报文后，检查ACK的值为自己发送的Seq值+1,确认建立连接，并发送ACK=Y+1的报文给服务器;服务器收到这个报文后检查ACK值为自己发送的Seq值+1,确认建立连接。

至此，App和服务器建立起TCP连接，就可以进行数据传输了。

2.4     TCP关闭连接的4次挥手





1.客户端向服务器端发送一个FIN, 请求关闭数据传输。

2.当服务器接收到客户端的FIN时，向客户端发送一个ACK,其中ACK的值等于FIN + SEQ。

3.然后服务器向客户端发送一个FIN,告诉客户端应用程序关闭。

4.当客户端收到服务器端的FIN是，回复一个ACK给服务器端。其中ACK的值等于FIN +SEQ。

2.5     应用层HTTP协议

而互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，

需要一个统一的应用层协议，这个协议就是HTTP协议。

2.5.1      HTTP请求的7种方法

Get：只读请求，请求处理过程不应该产生副作用，即web应用不应该因为get 请求而发生任何状态改变。

Head：和get方法一样，但是只返回响应头。

Post：提交请求。

Put：上传请求。

Delete：删除URL标识的资源。

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

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

HTTP请求格式：





2.5.2      HTTP响应的5种状态

1xx消息一一请求已被服务器接收，继续处理。

2xx成功一一请求已成功被服务器接收、理解、并接受。

3xx重定向一一需要后续操作才能完成这一请求。

4xx请求错误一一请求含有词法错误或者无法被执行。

5xx服务器错误一一服务器在处理某个正确请求时发生错误。

HTTP响应格式：





2.5.3      HTTP协议版本

1996年发布了HTTP/1.0， 在HTTP/1.0中,客户端和服务器之间交换的每个请求/响应

都会创建一个新的TCP连接,这意味着所有请求之前都需要进行TCP握手连接,因此所

有请求都会产生延迟。





HTTP/1.1试图引入保持连接的概念来解决这些问题,它允许客户端复用TCP连接,

从而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个连接只能

执行一次请求/响应交换。

随着网络的发展,网站所需资源( CSS、JavaScript 和图像等)不断增长，浏览器在获

取和呈现网页时需要越来越多的并发性。但由于HTTP/1.1只允许客户端同时进行一次

HTTP请求/响应交换,因此在网络层上获得并发能力的唯一方法是并行使用多个 TCP

连接。





HTTP/2引入了HTTP"流"的概念,允许将不同的HTTP并发地复用到同一TCP连接

上,使浏览器更高效地复用TCP连接。HTTP/2 解决了单个TCP连接的使用效率低的

问题，现在可以通过同一连接同时传输多个请求/响应。但是, TCP并不理解HTTP流，

当多个HTTP请求复用一个TCP连接,如果前面的请求响应没有处理完,后面的请求/

响应也无法处理,也就是会出现队头堵塞现象。





HTTP/3不是使用TCP作为会话的传输层，而是使用QUIC ( 一种新的互联网传输协

议)。该协议在传输层将流作为一等公民引入。 多个QUIC流共享相同的QUIC连接

因此不需要额外的握手和慢启动来创建新的QUIC流。但QUIC流是独立的,因此在

大多数情况下,只影响一个流的丢包不会影响其他流,这是因为QUIC数据包封装在

UDP数据包。





3       非阻塞网络I/O

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

计算机进程之间是通过Socket进行通信的，先启动的可视为服务器，后启动的可视为客户端：





Socket通信核心代码示例：





以上通信模型会造成多个并发请求时的阻塞，所以可以用多线程来改善：





因为线程总时创建、销毁很消耗资源，所以以上模型可以通过线程池来优化：







注意：

不管怎样，以上每个线程去读写时这个线程还是会阻塞的，所以他们属于阻塞IO。

3.2     阻塞I/O（Blocking I/O）

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





3.3     非阻塞I/O ( Non-Blocking I/O )

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

非阻塞read操作：

Socket接收缓冲区有数据,读n个(不保证数据被读完整,因此有可能需要多次读)。

Socket接收缓冲区没数据,则返回失败(不会等待)。

非阻塞write操作：

Socket发送缓冲区满,返回失败(不会等待)。

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





3.4     Java NIO (New I/O)

Java NIO是一种同步非阻塞的I/O模型，也是I/O多路复用的基础，已经被越来越多地应用到大型应用服务器，成为解决高并发与大量连接、I/O处理问题的有效方式。

NIO是一种基于通道和缓冲区的I/O方式，它可以使用Native函数库直接分配堆外内存（区别于JVM的运行时数据区），然后通过一个存储在java堆里面的DirectByteBuffer对象作为这块内存的直接引用进行操作。这样能在一些场景显著提高性能，因为避免了在Java堆和Native堆中来回复制数据。

NIO主要有三大核心部分：Channel(通道)，Buffer(缓冲区), Selector（选择器）。

传统IO是基于字节流和字符流进行操作（基于流），而NIO基于Channel和Buffer(缓冲区)进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。Selector(选择区)用于监听多个通道的事件（比如：连接打开，数据到达）。因此，单个线程可以监听多个数据通道。

Buffer：

Buffer（缓冲区）是一个用于存储特定基本类型数据的容器。除了boolean外，其余每种基本类型都有一个对应的buffer类。Buffer类的子类有ByteBuffer, CharBuffer, DoubleBuffer, FloatBuffer, IntBuffer, LongBuffer, ShortBuffer 。

Channel：

Channel（通道）表示到实体，如硬件设备、文件、网络套接字或可以执行一个或多个不同 I/O 操作（如读取或写入）的程序组件的开放的连接。Channel接口的常用实现类有FileChannel（对应文件IO）、DatagramChannel（对应UDP）、SocketChannel和ServerSocketChannel（对应TCP的客户端和服务器端）。Channel和IO中的Stream(流)是差不多一个等级的。只不过Stream是单向的，譬如：InputStream, OutputStream.而Channel是双向的，既可以用来进行读操作，又可以用来进行写操作。

Selector：

Selector（选择器）用于监听多个通道的事件（比如：连接打开，数据到达）。因此，单个的线程可以监听多个数据通道。即用选择器，借助单一线程，就可对数量庞大的活动I/O通道实施监控和维护。

在传统的IO处理方式种，一个线程处理一个网络连接；

而NIO处理方式，一个线程可以管理多个网络连接：





NIO服务器端如何实现非阻塞？

服务器上所有Channel需要向Selector注册；

而Selector则负责监视这些Socket的IO状态(观察者)；

当其中任意一个或者多个Channel具有可用的IO操作时，该Selector的select()方法将会返回大于0的整数，该整数值就表示该Selector上有多少个Channel具有可用的IO操作，并提供了selectedKeys（）方法来返回这些Channel对应的SelectionKey集合(一个SelectionKey对应一个就绪的通道)。

正是通过Selector，使得服务器端只需要不断地调用Selector实例的select()方法即可知道当前所有Channel是否有需要处理的IO操作。

（来自https://blog.csdn.net/u013857458/article/details/82424104）





3.5     I/O多路复用(I/O Multiplexing)

这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程。

I/O多路复用方式可分为： select, poll, epoll

3.5.1      select

基本原理：select 函数监视的文件描述符分3类，分别是writefds、readfds、和exceptfds。调用后select函数会阻塞，直到有描述符就绪（有数据 可读、可写、或者有except），或者超时（timeout指定等待时间，如果立即返回设为null即可），函数返回。当select函数返回后，可以通过遍历fdset，来找到就绪的描述符。

缺点:

1、select最大的缺陷就是单个进程所打开的FD是有一定限制的，它由FDSETSIZE设置，32位机默认是1024个，64位机默认是2048。

一般来说这个数目和系统内存关系很大，”具体数目可以cat /proc/sys/fs/file-max察看”。32位机默认是1024个。64位机默认是2048.

2、对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低。

当套接字比较多的时候，每次select()都要通过遍历FDSETSIZE个Socket来完成调度，不管哪个Socket是活跃的，都遍历一遍。这会浪费很多CPU时间。”如果能给套接字注册某个回调函数，当他们活跃时，自动完成相关操作，那就避免了轮询”，这正是epoll与kqueue做的。

3、需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大。





3.5.2      poll

基本原理：poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。

它没有最大连接数的限制，原因是它是基于链表来存储的，但是同样有一个缺点：1、大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。

2 、poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

注意：从上面看，select和poll都需要在返回后，通过遍历文件描述符来获取已经就绪的socket。事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。





3.5.3      epoll

epoll是在2.6内核中提出的，是之前的select和poll的增强版本。相对于select和poll来说，epoll更加灵活，没有描述符限制。epoll使用一个文件描述符管理多个描述符，将用户关系的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。

基本原理：epoll支持水平触发和边缘触发，最大的特点在于边缘触发，它只告诉进程哪些fd刚刚变为就绪态，并且只会通知一次。还有一个特点是，epoll使用“事件”的就绪通知方式，通过epollctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epollwait便可以收到通知。

epoll的优点：1、没有最大并发连接的限制，能打开的FD的上限远大于1024（1G的内存上能监听约10万个端口）。

2、效率提升，不是轮询的方式，不会随着FD数目的增加效率下降。

只有活跃可用的FD才会调用callback函数；即Epoll最大的优点就在于它只管你“活跃”的连接，而跟连接总数无关，因此在实际的网络环境中，Epoll的效率就会远远高于select和poll。

3、内存拷贝，利用mmap()文件映射内存加速与内核空间的消息传递；即epoll使用mmap减少复制开销。

注意：java NIO就是多路复用IO，jdk7之后底层是epoll模型。





4       数据库架构原理

4.1     PrepareStatement预编译

PrepareStatement的好处:

       1. 提高了代码的可读性和可维护性；

       2. 尽最大可能提高性能；

       3. 极大地提高了安全性。

4.2     数据库架构





4.2.1      连接器

连接器会为每个连接请求分配块专 用的内存空间用于 会话上下文管理。 建立连接对数据库而言相对比较重，需要花费一定的时间，因此应用程序启动的时候，通常会

初始化建立-些数 据库连接放在连接池里，这样当处理外部请求执行SQL操作的时候 ，

就不需要花费时间建立连接了。

4.2.2      语法分析器

语法分析器主要用途是解析传入的sql语法（生成语法树）：





4.2.3      语义分析与优化器

语义分析与优化器就是要将各种复杂嵌套的SQL进行语义等价转化,得到有限几种关

系代数计算结构,并利用索引等信息进一步进行优化。

4.2.4      执行引擎

执行引擎又叫存储引擎。

数据库存储引擎是数据库底层软件组织，数据库管理系统（DBMS）使用数据引擎进行创建、查询、更新和删除数据。

不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎，还可以获得特定的功能。

现在许多不同的数据库管理系统都支持多种不同的数据引擎。MySQL的核心就是存储引擎。

如何选择 MySQL 存储引擎？

不同的存储引擎都有各自的特点，以适应不同的需求，如表所示。为了做出选择，首先要考虑每一个存储引擎提供了哪些不同的功能。





InnoDB 事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键。

MySQL 5.5.5 之后，InnoDB 作为默认存储引擎。

4.3     数据库索引

数据库表的索引从数据存储方式上可以分为聚簇索引和非聚簇索引（又叫二级索引）两种。

4.3.1      聚簇索引

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

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





4.3.2      非聚簇索引

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

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





4.3.3      不要滥用索引

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

添加索引的alter操作会消耗较长的时间(分钟级)

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

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

应该使用更小的数据类型(在满足业务的情况下)，理由如下：

1)     更小的数据类型可能占用的磁盘空间更小，相同的内存空间可以缓存更多的记录，减少IO操作，减少磁盘空间占用

2)更小的数据类型意味着CPU可以更快的进行计算。

3)最主要的是，在数据库执行过程中MySQL有时会建立一些临时表进行连接排序或去重操作，在这些临时表中列的长度跟源表中列的长度一致，列的长度越大，性能也就越不好。所以列的类型尽可能的小。

4.4     数据库事务

数据库事务( transaction)是访问并可能操作各种数据项的一个数据库操作序列，这些操作要么全部执行,要么全部不执行，是一个不可分割的工作单位。事务由事务开始与事务结束之间执行的全部数据库操作组成。

事务特性ACID：

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

务之前( 事务回滚)

隔离性(lsolation) : 如果2个事务T1和T2同时运行，事务T1和T2最终的结果是相同

的，不管T1和T2谁先结束，隔离性主要依靠锁实现。

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

据库中。

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

4.5     数据库事务日志

进行事务操作时，事务日志文件会记录更新前的数据记录，然后再更新数据库中的记录。

如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整

个事务全部回滚，已经更新的记录根据事务日志中记录的数据进行恢复，这样全部数据

都恢复到事务提交前的状态，仍然保持数据一致性。





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

TransID: 产生操作的事务ID。

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

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

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

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