理解 B+ 树算法

作者：毛见峰

导语： 最近有接触到b 树，花了点时间，顺便总结梳理下方便后续翻阅；时间仓促，且文中多是个人的理解，仅供参考。

定义

参考百度百科及wiki百科定义：B 树是一个N叉排序树，每个节点通常有多个孩子，一棵B 树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。

B 树主要价值在于存储用于在面向块的存储环境中高效检索的数据，通常用于数据库和操作系统的文件系统中。B 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B 树元素自底向上插入。

结构类似如下：

B 树的特点剖析

1. 只有叶子节点才记录数据，非叶子节点只包含索引；换句话说，所有叶子节点中包含了全部关键字的信息，及指向这些关键字记录的指针，所有的非终端节点（内部节点）并不存储数据信息，而是保存其叶子节点的最小值作为索引。 此点设计初衷，主要作用体现在降低磁盘IO方面。
2. 能够提供稳定高效的范围扫描（range-query）功能；这也是为什么数据库和操作系统中的文件系统通常会采用b 树作为元数据索引的原因，这个特点主要得益于所有叶子节点相互连接，并且叶子节点本身依关键字的大小自小而大顺序链接。这种设计在扫描时可以避免的耗时的遍历树操作。所以，b 树通常可以提供两种查找方式，一，从根节点起随机查找（起点是指向根节点的root）； 二，顺序查找（起点是指向最小关键字的sqt）。
3. 所有叶子节点均出现在同一层；因为在实现上B 树元素插入采用的是自底向上分裂算法（删除元素类似同理），具体实现可参看下节图示。另外说明的一点，B 中的B并不是代表二叉(Binary),而是代表平衡(Balance)。
4. 对于m阶B 树，m的值越大，固定高度的B 树存放的值就越多。实验数据表明当m处于50~400之间，性能最好[待验证]；在wiki百科里的b 树的介绍里提到的m值也通常是100甚至更多：B trees have very high fanout (number of pointers to child nodes in a node,[1] typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree。
5. 在B 树的索引中，用户可以得到页表（或者叫块）级别的位置信息；但如果要进行一次比如key1到key3的范围查询，则可能需要读取两个在磁盘上不连续甚至可能相隔很远的叶子节点页表；这种情况，通常在B 树的设计中会含有一组被称为OPTIMIZE TABLE（优化表）命令，TA的作用是把表重写，从而使表的范围查询变成磁盘的多段连续读取，提高范围查询的执行效率。

B 树插入删除操作图示

插入基本算法（参考wiki定义）：

执行搜索以确定新记录应该进入哪个节点。

• 如果节点不满，添加记录。
• 否则，拆分节点。
  1. 分配新的叶子节点，并将一半的原节点元素移动到新的叶子节点。
  2. 将新叶子节点的最小键和地址插入父节点。
  3. 如果父节点满了，分拆。
  4. 将中间键添加到父节点。
  5. 重复一遍，直到找到不需要拆分的父节点。
• 如果根分裂，创建一个新的根，分别取自叶子的最小键。
• B树在根部生长，而不是在叶子上生长。

举个栗子：往下图的3阶B 树中依次插入关键字：10、21、68、65、85

首先查找10应插入的叶节点(最左下角的那一个),插入发现没有破坏B 树的性质,完毕。插完如下图所示:

继续查找21应插入的叶节点(还是最左下角的那一个),插入，发现该叶子节点已经破坏了B 树的性质，则分解成[8 10], [15 21]两个,并把15往父节点移；

这时可以发现父节点也破坏了B 树的性质,则把之再分解成[8 15], [34 93]两个,并把8和34（由于此时是根节点）向上产生一个新根节点；

如下图：

接着查找68应插入的叶节点(第三个叶子节点),插入发现没有破坏B 树的性质,完毕。插完如下图所示:

接着查找65应插入的叶节点(第三个叶子节点),插入，发现该叶子节点已经破坏了B 树的性质，则分解成[34 65], [68 78]两个,并把68往父节点移；如下图所示:

最后查找85应插入的叶节点(第四个叶子节点),插入发现没有破坏B 树的性质,完毕。插完如下图所示:

至此完毕！

删除算法类似，但更为复杂些，插入算法节点之间只与父节点产生关系，而删除算法则需要考虑兄弟节点和父子节点的关系；在此不赘述了。

总而言之 B 树多用于文件系统索引（比如NTFS, ReiserFS, NSS, XFS等）和数据库索引（比如innodbinnodb存储引擎等）方面，其优势主要体现在（针对B树）：

1. 降低磁盘IO方面做的更好 B 树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存 中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。 举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B 树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B 树多一次盘块查找时间(在磁盘中就是盘片旋转寻道的时间)。
2. 查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

但是如果对写数据敏感度比较高，则更倾向于使用LSM树，LSM树能够保证更稳定的数据插入速率；后续有时间整理介绍。