B树

B 树 (B - Tree)

B-树，即为 B 树，不要读作 B 减树

B 树与红黑树最大的不同在于，B 树的结点可以有许多子女，从几个到几千个。

定义

B 树的定义有两种，一种以阶数为限制的 B 树(下文所述的)，一种以度数为限制的 B 树(算法导论所描述的)，两者原理类似，这里以阶数来定义

B 树属于平衡多路查找树。一棵 m 阶(m 阶即代表树中任一结点最多含有 m 个孩子)的 B 树的特性如下:

1. 除根节点外所有节点关键字个数范围: [-1, m-1]
2. 若非叶子节点含 n 个关键字，则子树有 n+1 个，由关键字范围可知子树的个数范围: [, m]
3. 根节点至少包含一个关键字，至少有两个孩子(除非 B 树只存在一个节点: 根结点)，即根节点关键字个数范围: [1, m-1]，孩子数范围: [2, m]
4. 所有叶子节点都处在同一层，即高度都一样
5. 每个节点中的关键字从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分

如图是一个典型的 2-3-4 树结构，也是阶为 4 的 B 树。从图中查询元素最多只需要 3 次磁盘 I/O 就可以访问到我们需要的数据节点，将节点数据块读入内存后再查找指定元素会很快。如果同样的数据用红黑树表示，树高会增长很多，造成遍历节点的次数增多，访问磁盘的次数增多，查找性能会下降。
对于一棵包含 n 个元素、高度为 h 、阶数为 m 的 B 树: 影响 B 树高度的是每个结点所包含的子树数，如果尽可能使结点孩子数都等于 ，则层数最多，为最坏情况；如果尽可能使结点孩子数都等于 m，则层数最少，为最好情况。所以有

底数 可以取很大，比如 m 可以达到几千，从而在关键字数一定的情况下，使得最终的 h 值尽量比较小，树的高度比较低。
实际运用中 B 树中的每个结点根据实际情况可以包含大量的关键字信息和分支(但不能超过磁盘块的大小，根据磁盘驱动的不同，一般块的大小在 1k~4k 左右)；这样树的深度降低了，意味着查找一个元素只要很少的结点从外存磁盘中读入内存，就可以很快地访问到要查找的数据

查找

一个节点的结构可以定义为:

type BTNode struct {
  KeyNum   int       // 关键字个数，math.Ceil(m/2)-1 <= KeyNum < 阶数 m
  Parent   *BTNode   // 指向父节点的指针
  IsLeaf   bool      // 是否为叶子，叶子节点 children 为 nil
  Key      []int     // 关键字切片，长度为 KeyNum
  Children []*BTNode // 子节点指针切片，长度为 KeyNum+1
}
复制代码

以上面 2-3-4 树的根节点为例：

所有数据以块的方式存储在外磁盘中，我们通过 B 树来查找数据时，每遍历到一个节点，便将其读入内存，比较其中的关键字，若能匹配到我们要找的元素，便返回；若未能找到，通过比较确定在哪两个关键字的值域区间， 即可确定子树的节点指针，继续往下找，把下一个节点的数据读入内存，重复以上步骤

插入

对于一棵 m 阶的 B 树来说，插入一个元素(或者叫关键字)时，首先判断在 B 树中是否已存在，如果存在则不插入；如果不存在，则在对应叶子结点中插入新的元素，需要判断是否会超出关键字个数限制(m-1)
插入步骤:

1. 根据元素大小查找插入位置，肯定是最底层的叶子节点，将元素插入到该节点中
2. 如果叶子节点的关键字个数小于等于 m-1，说明未超出限制，插入结束；否则进入下一步
3. 如果叶子节点的关键字个数大于 m-1 个，以结点中间的关键字为中心分裂成左右两部分，然后将这个中间的关键字插入到父结点中，这个关键字的左子树指向分裂后的左半部分，这个关键字的右子树指向分裂后的右半部分。
4. 然后将当前结点指向父结点，如果插入刚才的中间关键字后父节点的关键字个数也超出限制，继续进行第 3 步；否则结束插入

还是以上面的 2-3-4 树(阶数 m = 4)为例，我们依次插入元素

• 首先插入 1、2、3，因为关键字个数均未超过 m-1，所以直接插入即可:

• 当插入 4 时，该节点关键字个数达到 m，需要分裂，这里可以选 3 (也可以选 2) 作为中间字，分裂后:

• 继续插入 5、7，对应 4 所在的叶子节点:

• 当插入 8 时，也需要分裂，将中间字 5 上移至父节点，4 成为 5 的左区间子树，7 8 成为 5 的右区间子树:

之后的步骤类似，不再一一叙述

删除

删除操作是指删除 B 树中的某个节点中的指定关键字
删除步骤:

1. 如果当前要删除的关键字位于非叶子结点 N 上，则用后继最小关键字(找前继最大关键字也可以)覆盖要删除的关键字，然后在后继关键字所在的子树中删除该后继关键字。此后继关键字一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个后继关键字后进入第 2 步，如果原本要删除的关键字本身就位于叶子上同样删除关键字后进入第二步
2. 该结点(假设为 M)关键字个数大于等于 math.Ceil(m/2)-1，结束删除操作，否则进入第 3 步
3. 此时结点 M 关键字个数小于 math.Ceil(m/2)-1
   • 如果相邻兄弟结点(左右都可以)关键字个数大于 math.Ceil(m/2)-1，则父结点中取一个临近的关键字下移到 M，兄弟结点中取一个临近关键字上移至父节点，删除操作结束；
   • 如果相邻的兄弟节点关键字个数都不大于 math.Ceil(m/2)-1，将父结点中临近的关键字 key 下移至 M，合并 M 和它的兄弟节点形成一个新的结点。原父结点中的 key 的两个孩子指针就变成一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复第 2 步

以上面的 2-3-4 树为例

阶数为 4，节点关键字个数范围应该是 [1, 3]，即 math.Ceil(m/2)-1 = 1

• 删除关键字 2 或者 8，不影响节点

• 删除关键字 4，该叶子节点 X 关键字个数变为 0 小于范围下界，同时左右两个相邻兄弟的关键字个数都不大于 1，需要合并节点。
  • 第一步，将父节点的 5 下移到 X 上
  • 第二步，合并 X 和右兄弟节点 7 形成一个包含 5、7 的新节点
  • 第三步，父节点中原本 5 的左右两个孩子指针变为一个并指向这个新节点

这里第一步也可以选择下移 3，然后第二步跟左兄弟合并成 1、3 节点

• 继续删除 1，此时与上一个问题不同，该叶子节点的兄弟有富余的关键字，我们只需要把父节点的临近的一个关键字下移到该叶子节点代替删除的元素，然后把兄弟节点的一个临近关键字上移至父节点即可，这个操作有点类似红黑树的左旋操作

• 现在尝试删除非叶子节点 5，用后继最小关键字 7 代替 5，然后删除 7 所在的叶子节点。
  • 此时会引起连锁反应，7 所在的叶子节点现在为空，而兄弟节点关键字又不大于 1，需要合并
  • 将关键字 7 又从父节点移至原来的叶子上，合并成含 3、7 的新节点，假设新节点为 N，父节点的孩子指针变为一个并指向 N
  • 而父节点现在关键字是空的，而且其兄弟(N 的叔叔)关键字也不大于 1，也需要合并
  • 根节点取出关键字 9 下移到 N 的父节点上，合并 N 的父节点和叔叔节点，产生一个包含 9、15 的新节点，根节点的孩子指针减少一个且左子树指向这个新节点

删除操作就演示到这，B 树的内容讲完

B 树动态展示: www.cs.usfca.edu/~galles/vis…

B+ 树 (B+ - Tree)

B+ 树 是基于 B 树的变体，查找性能更好
同为 m 阶的 B+ 树与 B 树的不同点:

1. 所有非叶子节点，每个节点最多有 m 个关键字，最少有 个关键字(比 B 树的限制多一个)，其中每个关键字对应一棵子树
2. 所有的非叶子结点可以看成是索引部分，结点中仅含有其子树根结点中最大(或最小)关键字，不包含关键字数据的指针(B 树是包含这个指针的)
3. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小到大顺序链接.(而 B 树的全部关键字信息分散在各个节点中)

如图所示的是将之前的 2-3-4 树的数据存到 B+ 树结构中的示意图，叶子节点保存了所有关键字信息并且叶子节点之间也用指针连接起来(一个顺序链表)，而所有非叶子节点只包含子树根节点中对应的最大关键字，其作用只是用于索引

B+ 树还可以用另一种形式定义: 中间节点最多有 m-1 个关键字，最少有 个关键字，与 B 树相同； 但是非叶子节点的关键字是左子树的最大关键字(或者右子树的最小关键字)，与刚才的情形不同

比如同样的数据此定义的 B+ 树表现形式如下:

这种形式中间节点占用更少，可能更常见一点，不过下面的讲解是按第一种定义来

优势

B+ 树比 B 树更适合实际应用中操作系统的文件索引和数据库索引

1. B+ 树索引节点可以存储更多的关键字，磁盘 I/O 可以更少

   数据库中关键字可能只是某个数据列的索引信息(比如以 ID 列创建的索引)，而索引指向的数据记录(某个 ID 对应的数据行)我们称作卫星数据，推荐看下博文 数据库的最简单实现 和 MySQL索引背后的数据结构及算法原理 B- 树中间节点和叶子节点都会带有关键字和卫星数据的指针，B+ 树中间节点只带有关键字，而卫星数据的指针均放在叶子节点中

因为没有卫星数据的指针，所以 B+ 树内部结点相对 B 树占用空间更小。如果把所有同一结点的关键字存放在同一盘块中，那么对于 B+ 树来说盘块所能容纳的关键字数量也就更多，一次性读入内存中时能查找的关键字也就更多。相对来说 IO 读写次数也就降低了，性能就提升了。
举个例子，假设磁盘中的一个盘块能容纳 16 bytes，而一个关键字占 2 bytes，一个卫星数据指针占 2bytes。对于一棵 9 阶 B 树来说，一个结点最多含 8 个关键字(8*4 bytes)，即一个内部结点需要 2 个盘块来存储。而对于 B+ 树来说，内部结点不含卫星数据的指针，所以一个内部节点只需要 1 个盘块。当需要把内部结点读入内存中的时候，B 树就比 B+ 树多一次盘块查找时间

1. B+ 树的查询效率更加稳定

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

1. B+ 树对范围查询操作更友好

如果是查找单一元素，B+ 树的查找过程与 B 树类似，只是每次查找都是从根查到叶
而进行范围查询的操作时，B+ 树只要遍历叶子节点就可以实现整棵树的遍历，而 B 树的范围查询要通过中序遍历，效率比较低下

插入

B+ 树的插入与 B 树类似，先寻找关键字对应的位置插入，需要注意的是插入比当前子树的最大关键字还大的数时要修改祖先节点对应的关键字，因为 B+ 树内部结点存的是子树的最大关键字
比如在上面给出的 B+ 树中插入 105 这个元素，因为 105 大于当前子树最大关键字 101，所以需要修改父节点和祖父节点的边界关键字:

• 如果插入元素的节点未超出上界限制，则结束；否则将节点分裂，中间节点上移到父节点中，再判断父节点是否需要调整

比如刚才插入 105 的叶子节点关键字个数达到 4 个，需要分裂，这里分裂与 B 树略有不同。B 树是把节点按中间节点分成三份，再把中间节点上移；而 B+ 树是分成两份，再把左半节点的最大关键字添加进父节点

此时父节点也需要分裂

根节点未超出 4，结束；假如此时根节点也超出上界了，需要把根节点也分裂，生成一个新的根节点，且新的根节点的关键字为左右子树的最大关键字

删除

B+ 树的删除与 B 树也类似，找到要删除的关键字，如果是当前子树的最大关键字，删除该关键字后还要修改祖先节点对应的关键字；如果不是当前子树的最大关键字，直接删除；
在上一张图的基础上删除 8，这是叶子的最大关键字，所以需要修改父节点和祖父节点的边界关键字:

• 如果删除元素的节点未低于下界限制，则结束；否则分两种情况处理:
  • 如果兄弟节点有富余关键字，则从兄弟节点中移动一个关键字到当前节点，修改父节点对应边界关键字即可
  • 如果兄弟节点关键字个数都处于下界值，不能外借元素，则合并当前节点和兄弟节点，修改父节点的孩子指针以及边界关键字，此时父节点关键字个数也少了一个，将当前节点的指针指向父节点继续判断处理

我们继续删除 7，此时该叶子节点关键字个数少于 1 需要调整，而兄弟节点有富余关键字，可以移动 5 到当前节点，修改父节点和祖父节点的边界关键字

继续删除 5，兄弟节点的关键字个数为下界值 1，不能外借，则合并当前节点和兄弟节点，并修改父节点指针及关键字，相应的祖父节点也需要修改边界关键字

B+ 树动态展示: www.cs.usfca.edu/~galles/vis…

B 树 (B - Tree)

B 树是 B+ 树的变体，在 B+ 树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B 树多了两条性质:

• 中间结点也增加了指向兄弟的指针，即每一层节点都可以横向遍历
• B* 树定义了非叶子结点关键字个数至少为 ，即块的最低使用率为 2/3，代替 B+ 树的 1/2

下图的数据与之前 B+ 树的数据一样，但分支结构有所不同(因为中间节点关键字范围变为[3, 4]，不同于之前 B+ 树的 [2, 4])，而且第二层节点之间也用指针连接起来

优势

B+ 树节点满时就会分裂，而 B* 树节点满时会先检查兄弟节点是否满(因为每个节点都有指向兄弟的指针):

• 如果兄弟节点未满则向兄弟节点转移关键字，然后修改原节点和兄弟结点的关键字以及会受最大关键字变动影响的祖先的边界关键字
• 如果兄弟节点已满，则从当前节点和兄弟节点各拿出 1/3 的数据创建一个新的节点出来，然后在父结点增加新结点的指针

B 树存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得 B 树分解次数变得更少，节点空间使用率更高
因为没有找到相关的内容，关于 B* 树的插入删除这里不再讲解