B-Tree

定义

B树是一个多路的平衡查找树，所谓多路就是多叉，它是一种专门为磁盘等外置存储设备而设计的一种数据结构

一颗m阶的B树（m叉树或者m路树）满足如下性质：

1. 每个节点最多包含m个孩子（m>=2）
2. 除根节点和叶子节点外，其它每个节点至少有ceil(m/2)个孩子
3. 若根节点不是叶子节点，至少有两个孩子
4. 所有叶子节点都出现在同一层
5. 每个非叶子节点包含n个关键字信息（P1,K1,P2,K2...,Kn-1,Pn）,其中K(1 - n-1)为顺序排列的关键字，P(1-n)为指向子节点的指针，并满足P(i-1)子树所有关键字<= Ki <=P(i+1)子树所有关键字

例子

3路B树

image.png

1. 查找
   以查找79关键字为例

• 从磁盘读取磁盘块1，79 > 35 所以，数据在P3指向的子节点里
• 从磁盘读取磁盘块4，65 < 79 < 87，数据在P2指向的子节点里
• 从磁盘读取磁盘块10，遍历即可找到79

可以看到磁盘IO的次数明显降低，我们知道默认InnoDb存储引擎每个页大小为16KB，而一个关键字信息加上指针信息一般为16B，但是每个关键字还包含着对应的记录的信息，这部分大小不定，可知InnoDb一次读取的磁盘块大概包含16KB/（16B+未知大小）,存储的关键字不多，所以也就导致深度会增加，因此InnoDb索引的存储使用的另外一种结构B+Tree

2. 插入
   生成从空树开始，从一个空节点插入m-1个关键字，当关键字数大于m-1时，则进行分裂，分裂方式是将中间节点升级为父节点，左右分别形成单独节点，依次重复上述步骤