数据库必知词汇：平衡多路查找树B-Tree

B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。B-Tree中的B代表平衡（balance），而不是二叉（binary），因为B-Tree树是从最早的平衡二叉树演化而来的。这个数据结构一般用于数据库的索引，综合效率较高。

B-tree中，每个结点包含：

1. 本结点所含关键字的个数；
2. 指向父结点的指针；
3. 关键字；
4. 指向子结点的指针。

对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。

一棵m阶的B-Tree有如下特性：

1. 每个节点最多有m个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。

8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

   B-tree有以下特性：

9. 关键字集合分布在整棵树中；
10. 任何一个关键字出现且只出现在一个结点中；
11. 搜索有可能在非叶子结点结束；
12. 其搜索性能等价于在关键字全集内做一次二分查找；
13. 自动层次控制。

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：O（log2N）（N为关键字总数）。

所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如：

1. B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。
2. 硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。

资料来源：

B-Tree详解

https://www.cnblogs.com/qixinbo/p/11048269.html

深入理解索引的底层实现原理之BTree索引和B+Tree索引解析及区别

https://baijiahao.baidu.com/s?id=1635778645917488178&wfr=spider&for=pc

MySQL索引原理及BTree（B-/+Tree）结构详解

https://blog.csdn.net/u013967628/article/details/84305511