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

快速、高效
，那就要尽可能减少不必要的磁盘 IO 次数。所以不存。近而，
我们也就确定了我们选择的数据结构就是 B+ 树了
。
到此，我们就从最初的直观思路出发，找到了在磁盘上容易维护的数据结构：
B+ 树
。
在我们的抽象和改进中，引入了页的概念，磁盘中按照页的单位来组织数据，页内部保存的数据有序存储，页间数据也是有序存储。同时在磁盘上的 B+ 树中，非叶子节点保存页索引信息。其中包括(页编号 no、该页保存的数据最小记录 min)；叶子节点保存具体的记录数据。
既然磁盘上选择了 B+ 树存储，那自然内存中也就选择 B+ 树实现咯。我们来看看二者之间如何相互转化。
内存中b+树的节点对应磁盘上的一页。内存中一个节点内部的多项对应磁盘上每一页中保存每一个元素(每条记录数据or每个页索引项) 。
这儿再强调下：我们选择用 B+ 树作为索引而不是 B 树作为索引的核心点在于，在存储同等数据量级的情况下，选择用 B+ 树做索引时，要比用 B 树做索引。平均的磁盘 IO 次数要少。同时对B+ 树而言，不同请求的时间复杂度都比较平均。因为每条记录的数据都保存在叶子节点上。
到此我们尝试回答
为什么选择 B+ 树作为存储引擎索引结构
这个问题就回答完毕了。我们用一张图来总结下：

本文插图
最后我们看一下数据结构的 B+ 树长啥样，我们磁盘+内存中的 B+ 树又长啥样。
下图是数据结构中的 B+ 树，此处我们就不再过多解释其 B+ 树的特性了。

本文插图
下图是磁盘+内存中最后对应的 B+ 树示意图。

本文插图
最后，我们在接下来的一节内容中尝试通过回答第三个问题来我们来佐证一下我们选择的这个方案。
4.反向论证
既然选择了用 B+ 树来存储千万级数据量级的索引结构，那对于一个指定页大小的存储引擎， 3 层或者 4 层的 B+ 树能存储多少条数据呢？通过这个问题，我们再来证明下，我们选择的方案是否能解决我们当初提到的
存储千万级数据量级的数据
这个问题。
4.1 3层、4层 B+ 树(InnoDB 为例)各能存储多少数据?

本文插图
针对这个问题，我们如何做一个粗略的估算呢？
我们都知道 InnoDB 中，默认的一页大小是 16k ，此处我们也就以 16k 来做近似的估算。