jianshu地址:https://www.jianshu.com/p/99f64509142a

一、数据库基础

1、数据库架构

我们以mysql的架构为例，进行说明。

 

最上层用于连接、线程处理；第二层中包含了大多数 的核心服务，包括了对 SQL 的解析、分析、优化和缓存等功能，存储过程、触发器和视图都是在这里实现的；而第三层就是 真正负责数据的存储和提取的存储引擎，例如：InnoDB、MyISAM等，文中对存储引擎的介绍都是对 InnoDB 实现的分析。

2、数据存储结构

在整个数据库体系结构中，我们可以使用不同的存储引擎来存储数据，而绝大多数存储引擎都以二进制的形式存储数据。

在 InnoDB 存储引擎中，所有的数据都被逻辑地存放在表空间中，表空间（tablespace）是存储引擎中最高的存储逻辑单位，在表空间的下面又包括段（segment）、区（extent）、页（page）：

同一个数据库实例的所有表空间都有相同的页大小；默认情况下，表空间中的页大小都为 16KB，当然也可以通过改变 innodb_page_size 选项对默认大小进行修改，需要注意的是不同的页大小最终也会导致区大小的不同：

从图中可以看出，在 InnoDB 存储引擎中，一个区的大小最小为 1MB，页的数量最少为 64 个。

补充说明：

我们在进行数据插入的时候，数据库会分配新的数据页用于存放数据。MySQL一般都是一个extent为单位进行申请。我们在本地建个MySQL，然后慢慢往里面写数据，你会发现这个表的数据文件大小，是一段段增加的。

二、随机读取和顺序读取

在我们常用的sql理解中，数据是以行的形式读取出来的，其实不然，通过上述的结构，我们可以了解到，单次从磁盘读取单位是页，而不是行，也就是说，你即便只读取一行记录，从磁盘中也是会读取一页的，当然了单页读取代价也是蛮高的，一般都会进行预读。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率，预读的长度一般为页（page）的整倍数。

数据的读取过程：

关系型数据库管理系统最重要的一个目标就是，确保表或者索引中的数据是随时可以用的。那么为了尽可能的实现这个目标，会使用内存中的缓冲池来最小化磁盘活动。

每一个缓冲池都足够大，大到可以存放许多页，可能是成千上万的页。

缓冲池管理器将尽力确保经常使用的数据被保存于池中，以避免一些不必要的磁盘读。如果一个索引或者表页在缓冲池中被找到，那么将会处理很快。

如果在内存缓冲池中，没有找到数据，会从磁盘服务器的缓冲区里面去读取。磁盘服务器的缓冲区，如同数据库的缓冲池读取一样，磁盘服务器试图将频繁使用的数据保留在内存中，以降低高昂的磁盘读取成本。这个读取成本大概会在1ms左右。

如果磁盘服务器的缓冲池中依然没有找到数据，此时就必须要从磁盘读取了，此时读取又分区随机读取和顺序读取。

 

1、随机I/O

随机IO是指读写操作时间连续，但访问地址不连续，随机分布在磁盘的地址空间中

我们必须记住一个页包含了多条记录，我们可能需要该页上的所有行，也可能是其中一部分，或者是一行，但所花费的成本都是相同的，读取一个页（这个地方的前提应该是我们需要将多个页加载到内存中，但是页不连续），一次随机I/O, 大约需要10ms的时间。

 

时间组成：

我们可以看到，一次随机IO需要耗时的时间还是很久的，10ms对计算机来说是一个很长的时间节点了。

2、顺序读取

如果我们需要将多个页读取到缓冲池中，并按顺序处理它们，此时读取的速度回变的很快，具体的原理，在B树索引中也有过介绍，此时读取每个页面（4kb）所花费的时间大概为0.1ms左右，这个时间消耗对随机IO有很大的优势。

以下几种情况，会对数据进行顺序读取。

    全表扫描

    全索引扫描

    索引片扫描

    通过聚蔟索引扫描表行

顺序读取有两个重要的优势：

同时读取多个页意味着平均读取每个页的时间将会减少。在当前磁盘服务器条件下，对于4kb大小的页而言，这一值可能会低于0.1ms（40MB/s）

由于数据库引擎知道需要读取哪些页，所有可以在页被真正请求之前就提前将其读取进来，也就是预读。

对比以上随机和顺序读取，顺序读取的优势是显而易见的。

机械硬盘和固态硬盘在随机IO上性能的影响因素？

对于机械硬盘或是其他类似的机电存储设备，其随机存取IOPS主要和存储设备的寻址时间有关，若是固态硬盘及其他固态电子设备，其随机存取IOPS主要和存储设备的内部控制器及记亿体接口速度有关。这两种设备的顺序访问IOPS（尤其是访问大数据区块）一般与包括存储设备可以持续的最大带宽有关。

SSD作为随机存储设备，其访问任意一块的时间应该是相等的，为什么顺序IO还是快于随机IO?

有多种原因导致了这种情况，一是SSD通常是主控芯片包含若干个通道，每个通道和若干闪存芯片相连，随机IO并不能像顺序IO那样，由多块芯片分担且并行传输以获得更高的性能，二是SSD有擦写/垃圾回收等机制，随机IO明显会提高这些机制的难度和频率，三是预读和缓存等机制对顺序IO会有更好的效果。 不过现在的SSD在多线程下的随机IO吞吐量已经很接近顺序IO了，但还是有一定的差距。

todo：今后还可以进一步分析下ssd中的存取过程和性能瓶颈

三、索引

索引是为了加速对表中数据行的检索而存创建的一种分散存储的数据结构；

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(page)，每页大小4kb或8kb左右，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在B-Tree每次新建一个节点的同时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点node只需一次I/O。 

树的高度决定了I/O的次数，树高度越低，那么I/O性能就越好；

也就是说，因为磁盘的操作费时费资源。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？现在数据库存储的数据结构一般都是树，磁盘查找存取的次数往往由树的高度所决定，所以，我们需要一种高度较低的树结构。

（1）二叉树

二叉树每个节点只能存一个关键字的数据，无法很好的利用操作系统和磁盘的数据交换特性和磁盘预读能力；而且二叉树高度又太高，每查找一次新的节点，就会有一次I/O操作，而且只有两路，所以用来做索引的话，效率比较低；

（2）B树

如下图就是一颗B-tree，是一颗三路树：

 

17、35是第一层的关键字节点，有P 1、P 2、P3三路，小于走左边查找，大于走右边查找，位置之间的走中间查找；

一般路的数=关键字数+1，如果索引关键字节点（每个节点能存储4kb数据）的索引字段名称越短的话，每个节点存储的关键字数越多，路数也会变多，那么就导致了树的层级变低，每次I/O能够查找到数据的机会就越大，这样整体上就减少了I/O的搜寻次数，提高了效率； 

B树的特点

不再是二叉搜索，而是m叉搜索，高度相比二叉树能够大大降低；

叶子节点，非叶子节点，都存储数据，每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO；；

中序遍历，可以获得所有节点；

 （3）B+树

 

B+树，如上图，仍是m叉搜索树，在B树的基础上，做了一些改进：

非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；

叶子之间，增加了链表，获取所有节点，不再需要中序遍历； 

这些改进让B+树比B树有更优的特性：

范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯；画外音：范围查询在SQL中用得很多，这是B+树比B树最大的优势。

叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；

非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；

最后，量化说下，为什么m叉的B+树比二叉搜索树的高度大大大大降低？

大概计算一下：

(1)局部性原理，将一个节点的大小设为一页，一页4K，假设一个KEY有8字节，一个节点可以存储500个KEY，即j=500

(2)m叉树，大概m/2<= j <=m，即可以差不多是1000叉树

(3)那么：

一层树：1个节点，1*500个KEY，大小4K

二层树：1000个节点，1000*500=50W个KEY，大小1000*4K=4M

三层树：1000*1000个节点，1000*1000*500=5亿个KEY，大小1000*1000*4K=4G

画外音：额，帮忙看下有没有算错。

可以看到，存储大量的数据（5亿），并不需要太高树的深度（高度3），索引也不是太占内存（4G）。

参考文章：

https://blog.csdn.net/lejustdoit/java/article/details/95041213

https://juejin.im/post/5cef2c43e51d45572c05ffe3

https://www.jianshu.com/p/7f64caef3b7d

https://blog.csdn.net/lejustdoit/java/article/details/95041213