为什么 MySQL 选择 B＋树作为存储引擎索引结构( 八 )

我们如果将磁盘划分成一段一段的固定大小的连续块，
对于每一块的话，我们记录一个块编号no来区分不同的块
，假设我们的块大小是 100 个字节，那么第 0 块对应的范围是 0~99 ，第 1块对应的是 100~199 ，依次类推。做了这样的改变后会发生什么呢？我们详细分析一下。
将磁盘划分成一个一个的固定大小连续块后，每个块内仍然保留原先过程中的两大特性：
数据有序并且顺序写
。大致的结果如下图所以：

本文插图
这样改造以后，关键我们看看怎么保证读写呢？
我们先假设我们的块空间足够大，这样的话就能避免出现一个块存不下一条记录的问题。
正常情况下，我们的一个块会保存多条记录，并且块内的记录是有序存储的。我们在读取一条记录的时候，一条记录肯定是位于其中一块上，首先我们得解决这个定位问题。当定位到具体的块后，将当前块的数据从磁盘加载到内存中，块内部的数据是有序存储的，那自然就可以通过二分的方式来找到我们的具体数据对应的索引项了。最后再根据索引项来读取数据即可。同理写的过程虽然对外来看是对单条记录进行写，但内部是按照块作为单位来写磁盘。
那问题就转化成了
如何确定一条记录保存在哪一块上了？
针对这个问题，我们就需要
确定一块上具体存储的多条记录的具体范围
。例如第 0 块保存的是id 从 0~10 的记录；第 1 块保存的是 id 从 11~23 的记录。等等
这样的话，当查询 id 为7 的记录时，我们就很快可以知道该条记录存储在第 0 块上，然后再从第 0 块内部查找具体 id 为7 的记录的索引项，最后再读取数据。
怎么确定呢？
自然就需要在原先只保存一个块编号 no 的基础上，再多保存两个信息：该块保存的记录最小值 min、该块保存的记录的最大值 max
。
每一块都对应这样一个三元组 block->(no,min,max) 。
这个三元组表达的含义是：第 no 块保存的记录范围是 min~max
我们仔细再回想一下，其实这个三元组还是有改进空间的。因为我们写入的时候，每个块都是顺序写的并且块内数据是有序的，块间也是有序的。那也就是说：
对于第 i 块而言，第 i 块存储的记录范围就是第 i 块的最小值拼接上第 i+1 块的最小值。其根本原因也就是存储的时候块间是有序的。那进一步我们就可以将上述三元组简化成一个二元组了 block->(no,min)
。同时附加保证每块之间保存的数据是逻辑有序的。
前面啰里啰嗦说了一大堆，我们最后总结一下：