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

既然选择的操作系统页作为块大小基本单位，那我们也不引入一个新的概念
块
了，我们也
称块为页
呗。减少大家对新名词的理解成本。
第一个问题，到这儿我们也就解答完了。接下来我们看第二个问题。
块索引存不存？怎么存？
我们的答案是
存
，因为不存的话，当我们的应用重启时，就需要重新建块索引，当存储的数据量很大时，重建块索引是相当耗时的一件事情，在重建索引期间，可能会导致服务对外不可用。
所以我们需要存块索引。
那具体怎么存储呢？
第一种：最简单划分独立的块来保存快索引
该种方式在 MySQL 中也被称为
聚簇索引
,索引和记录数据存储在一起，存储在一个文件中。
第二种：将快索引采用单独的文件来保存
该种方式在 MySQL中也被称为
非聚簇索引
,索引和记录数据分开存储，存储在不同的文件中。
到此，我们的整体推导已经差不多接近尾声了，我们将上述推导做一个汇总，最终得到的结果如下图所示。

本文插图
上图中每个虚线框表示一页，其中每一页都保存数据(数据项或者索引项) ，每一页之间也可以有指针指向确保页之间是逻辑有序的。其次每个页内部都包含多个数据项或者索引项，而且数据是有序存储的。如果我们把其中的黑线去掉后，剩余的这种结构是一种啥结构呢？
答案是:
多叉树，其中每页可以看做一个节点，该节点内部有多项，同时一个节点可以多有个孩子节点
接下来我们再来回想个问题。现在我们可以基于这样的结构进行读写了。那我们来看看，当我们读取的时候，如果读取的数据正好是其中某一页保存的最小记录，那这时候如果我们的最小记录保存了数据的话，就可以直接返回了。而不用再往下遍历了。如果只保存一个最小记录关键字的话，那就还需要一直往下遍历。那我们就来看看
每页中的索引项存或者不存该条记录的原始数据会有哪些差异点呢？
根据上图的分析，我们可以看到，如果对应的页索引项中保存了原始数据，则它对应的就是
b树
的数据结构；如果不存储原始数据，则它对应的就是
B+ 树
的数据结构。分析清楚了存和不存的区别，那我们到底选择存还是不存呢？
答案是:
不存
，因为同样大小的一页，如果页索引项存储了额外的原始数据的话，必然一页中存储的页索引个数就会减少。同时进一步会导致存储同等数据量级的情况下，存储时的树的高度会比不存时高太多。而树的高度在我们这个场景里其实对应的就是磁盘 IO 的次数。显然我们要