B 树

文章目录

1. 1. 概念
2. 2. 规则
3. 3. 操作
   1. 3.1. 查询流程
      1. 3.1.1. B 树的高度
   2. 3.2. 插入流程
      1. 3.2.1. 实例
   3. 3.3. 删除流程
4. 4.
5. 5. B+ 树
   1. 5.1. 规则
6. 6. 参考

概念

B 树（英语：B-tree）是一种自平衡的树，又名平衡多路（即不止两个子树）查找树。能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B 树，概括来说是一个一般化的二元搜寻树（binary search tree）一个节点可以拥有 2 个以上的子节点。与自平衡二叉查找树不同，B 树适用于读写相对大的数据块的存储系统，例如磁盘。B 树减少定位记录时所经历的中间过程，从而加快存取速度。B 树这种数据结构可以用来描述外部存储。这种资料结构常被应用在数据库和文件系统的实现上。

与平衡二叉树的区别：

1. 平衡二叉树节点最多有两个子树，而 B 树每个节点可以有多个子树，M 阶 B 树表示该树每个节点最多有 M 个子树；
2. 平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而 B 树每个中间节点有 k-1 个关键字（可以理解为数据）和 k 个子树（ **k 介于阶数 M 和 M/2 之间，M/2 向上取整）；
3. B 树的所有叶子节点都在同一层，并且叶子节点只有关键字，指向孩子的指针为 null；

• 关于关键字的概念：

关于二叉树的关键字值

都是翻译惹的祸，key value 翻译成关键值，合适一点的翻译我觉得应该是“键值对”，也就是该二叉树节点的索引（比如编号）和节点存储的值（数字、字符串等等）的合称。

每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个 key 和其对应的 data 称为一个记录。但为了方便描述，除非特别说明，后续文中就用关键字来代替（key, value）键值对这个整体。在数据库中我们将 B 树（和 B+树）作为索引结构，

规则

1. 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；

2. 子节点数：非叶节点的子节点数>1，且<=M ，且 M>=2，空树除外（注：M 阶代表一个树节点最多有多少个查找路径，M=M 路,当 M=2 则是 2 叉树,M=3 则是 3 叉）；

3. 关键字数：枝节点的关键字数量大于等于 ceil(m/2)-1 个且小于等于 M-1 个（注：ceil()表示向上取整，如 ceil(1.1)结果为 2);

4. 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为 null 对应下图最后一层节点的空格子;

操作

查询流程

下面，我们来模拟下查找文件 29 的过程：

1. 根据根结点指针找到文件目录的根磁盘块 1，将其中的信息导入内存。 >>>【磁盘 IO 操作 1 次】
2. 此时内存中有两个文件名 17、35 和三个存储其他磁盘页面地址的数据。根据比较我们知道：17<29<35，因此我们找到指针 p2。
3. 根据 p2 指针，我们定位到磁盘块 3，并将其中的信息导入内存。 >>>【磁盘 IO 操作 2 次】
4. 此时内存中有两个文件名 26，30 和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针 p2。
5. 根据 p2 指针，我们定位到磁盘块 8，并将其中的信息导入内存。 >>>【磁盘 IO 操作 3 次】
6. 此时内存中有两个文件名 28，29。根据算法我们查找到文件名 29，并定位了该文件内存的磁盘地址。
   分析上面的过程，发现需要 3 次磁盘 IO 操作和 3 次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于 IO 操作是影响整个 B 树查找效率的决定因素。

当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘 4 次，最多 5 次，而且文件越多，B 树比平衡二叉树所用的磁盘 IO 操作次数将越少，效率也越高。

B 树的高度

根据上面的例子我们可以看出，对于辅存做 IO 读的次数取决于 B 树的高度。而 B 树的高度又怎么求呢？

对于一棵含有 N 个关键字，m 阶的 B 树来说（据 B 树的定义可知：m 满足：ceil(m/2)<=m<=m，m 阶即代表树中任一结点最多含有 m 个孩子，如 5 阶代表每个结点最多 5 个孩子，或俗称 5 叉树），且从 1 开始计数的话，其高度 h 为：

这个 B 树的高度公式从侧面显示了 B 树的查找效率是相当高的。为什么呢？因为底数 m/2 可以取很大，如 m 可以达到几千，从而在关键字数一定的情况下，使得最终的 h 值尽量比较小，树的高度比较低。树的高度降低了，磁盘存取的次数也随着树高度的降低而减少，从而使得存取性能也相应提升。

插入流程

针对一棵高度为 h 的 m 阶 B 树，插入一个元素时，首先在 B 树中是否存在，如果不存在，一般在叶子结点中插入该新的元素，此时分 3 种情况：

• 如果叶子结点空间足够，即该结点的关键字数小于 m-1，则直接插入在叶子结点的左边或右边；
• 如果空间满了以致没有足够的空间去添加新的元素，即该结点的关键字数已经有了 m 个，则需要将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中，而且当结点中关键元素向右移动了，相关的指针也需要向右移。
• 此外，如果在上述中间关键字上移到父结点的过程中，导致根结点空间满了，那么根结点也要进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。

  实例

  下面我们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的 5 阶 B 树中：C N G A H E K Q M F W L T Z D P R X Y S，而且，因为是 5 阶 B 树，所以必有非根结点关键字数小了（小于 2 个）就合并，大了（超过 4 个）就分裂。

1. 首先，结点空间足够，刚开始的 4 个字母可以直接到插入相同的结点中，如下图：
   
2. 插入 H 结点时，发现结点空间不够，所以将其分裂成 2 个结点，移动中间元素 G 上移到新的根结点中，且把 A 和 C 留在当前结点中，而 H 和 N 放置在新的右邻居结点中。如下图：
   
3. 当插入 E,K,Q 时，不需要任何分裂操作
   
4. 插入 M 需要一次分裂，注意到 M 恰好是中间关键字元素，所以 M 向上移到父节点中
   
5. 插入 F,W,L,T 不需要任何分裂操作
   
6. 插入 Z 时，最右的叶子结点空间满了，需要进行分裂操作，中间元素 T 上移到父节点中
   
7. 插入 D 时，导致最左边的叶子结点被分裂，D 恰好也是中间元素，上移到父节点中，然后字母 P,R,X,Y 直接陆续插入，不需要任何分裂操作
   
8. 最后，当插入 S 时，含有 N,P,Q,R 的结点需要分裂，把中间元素 Q 上移到父节点中，但是问题来了，因为 Q 上移导致父结点 “D G M T” 也满了，所以也要进行分裂，将父结点中的中间元素 M 上移到新形成的根结点中，从而致使树的高度增加一层。
   

   删除流程

   下面介绍删除操作，删除操作相对于插入操作要考虑的情况更多点。

• 首先查找 B 树中需删除的元素,如果该元素在 B 树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点
• 如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；
• 如果没有，直接删除后，移动之后的情况。

删除元素，移动相应元素之后，如果某结点中元素数目（即关键字数）小于 ceil(m/2)-1，则需要看其某相邻兄弟结点是否丰满（结点中元素个数大于 ceil(m/2)-1）

• 如果丰满，则向父节点借一个元素来满足条件；
• 如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于 ceil(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。

下面我们还是以上述插入操作构造的一棵 5 阶 B 树（树中除根结点和叶子结点外的任意结点的孩子数 m 满足 3<=m<=5，除根结点外的任意结点的关键字数 n 满足：2<=n<=4，所以关键字数小于 2 个就合并，超过 4 个就分裂）为例，依次删除 H,T,R,E。

1. 首先删除元素 H，当然首先查找 H，H 在一个叶子结点中，且该叶子结点元素数目 3 大于最小元素数目 ceil(m/2)-1=2，则操作很简单，我们只需要移动 K 至原来 H 的位置，移动 L 至 K 的位置（也就是结点中删除元素后面的元素向前移动）
   

2. 下一步，删除 T,因为 T 没有在叶子结点中，而是在中间结点中找到，我们发现他的继承者 W(字母升序的下个元素)，将 W 上移到 T 的位置，然后将原包含 W 的孩子结点中的 W 进行删除，这里恰好删除 W 后，该孩子结点中元素个数大于 2，无需进行合并操作。
   

3. 下一步删除 R，R 在叶子结点中,但是该结点中元素数目为 2，删除导致只有 1 个元素，已经小于最小元素数目 ceil(5/2)-1=2,而由前面我们已经知道：如果其某个相邻兄弟结点中比较丰满（元素个数大于 ceil(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中（有没有看到红黑树中左旋操作的影子?）。 故在这个实例中，由于右相邻兄弟结点“X Y Z”比较丰满，而删除元素 R 后，导致“S”结点稀缺

   • 所以原来的的“R S”结点先向父节点借一个元素 W 下移到该叶子结点中，代替原来 S 的位置，S 前移；
   • 然后相邻右兄弟结点中的 X 上移到父结点中；

   • 最后相邻右兄弟结点中元素 Y 和 Z 前移。

     

4. 最后一步删除 E， 删除后会导致很多问题，因为 E 所在的结点数目刚好达标，刚好满足最小元素个数（ceil(5/2)-1=2）,而相邻的兄弟结点也是同样的情况，删除一个元素都不能满足条件，所以该节点需要与某相邻兄弟结点进行合并操作；

   • 首先移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中
   • 然后将这两个结点进行合并成一个结点。所以在该实例中，我们首先将父节点中的元素 D 下移到已经删除 E 而只有 F 的结点中，然后将含有 D 和 F 的结点和含有 A,C 的相邻兄弟结点进行合并成一个结点。
     

也许你认为这样删除操作已经结束了，其实不然，再看看上图，对于这种特殊情况，你立即会发现父节点只包含一个元素 G，没达标（因为非根节点包括叶子结点的关键字数 n 必须满足于 2=<n<=4，而此处的 n=1），这是不能够接受的。如果这个问题结点的相邻兄弟比较丰满，则可以向父结点借一个元素。假设这时右兄弟结点（含有 Q,X）有一个以上的元素（Q 右边还有元素），然后我们将 M 下移到元素很少的子结点中，将 Q 上移到 M 的位置，这时，Q 的左子树将变成 M 的右子树，也就是含有 N，P 结点被依附在 M 的右指针上。

在这个实例中，我们没有办法去借一个元素，只能与兄弟结点进行合并成一个结点，而根结点中的唯一元素 M 下移到子结点，这样，树的高度减少一层。

为了进一步详细讨论删除的情况，再举另外一个实例：
这里是一棵不同的 5 序 B 树，那我们试着删除 C

于是将删除元素 C 的右子结点中的 D 元素上移到 C 的位置，但是出现上移元素后，只有一个元素的结点的情况。
又因为含有 E 的结点，其相邻兄弟结点才刚脱贫（最少元素个数为 2），不可能向父节点借元素，所以只能进行合并操作，于是这里将含有 A,B 的左兄弟结点和含有 E 的结点进行合并成一个结点。

这样又出现只含有一个元素 F 结点的情况，这时，其相邻的兄弟结点是丰满的（元素个数为 3>最小元素个数 2），这样就可以想父结点借元素了，把父结点中的 J 下移到该结点中，相应的如果结点中 J 后有元素则前移，然后相邻兄弟结点中的第一个元素（或者最后一个元素）上移到父节点中，后面的元素（或者前面的元素）前移（或者后移）；注意含有 K，L 的结点以前依附在 M 的左边，现在变为依附在 J 的右边。这样每个结点都满足 B 树结构性质。

从以上操作可看出：除根结点之外的结点（包括叶子结点）的关键字的个数 n 满足：（ceil(m / 2)-1）<= n <= m-1，即 2<=n<=4。这也佐证了我们之前的观点。删除操作完。

B+ 树

规则

1. B+跟 B 树不同，B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得 B+树每个非叶子节点所能保存的关键字大大增加；

2. B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

3. B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

4. 非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料，这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的，Mysql 的 B+树是用第一种方式实现）;
   参见
   维基百科
   从 MySQL Bug#67718 浅谈 B+树索引的分裂优化

Q: 为什么说 B+树 比 B 树更适合实际应用中操作系统的文件索引和数据库索引？

• B+树的磁盘读写代价更低
  B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。
  举个例子，假设磁盘中的一个盘块容纳 16bytes，而一个关键字 2bytes，一个关键字具体信息指针 2bytes。一棵 9 阶 B 树(一个结点最多 8 个关键字)的内部结点需要 2 个盘块。而 B+ 树内部结点只需要 1 个盘快。当需要把内部结点读入内存中的时候，B 树就比 B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

• B+树的查询效率更加稳定
  由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

总而言之，B 树在提高了磁盘 IO 性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历，支持基于范围的查询，而 B 树不支持 range-query 这样的操作（或者说效率太低）。

参考

B 树
B 树和 B+树的插入、删除操作图文详解