动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度 O(log2N) 与树的深度相关，那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，因此我们该想办法降低树的深度，从而减少磁盘查找存取的次数。一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

这样我们就提出了一个新的查找树结构——平衡多路查找树，即B-tree（B-tree树即B树，B即Balanced，平衡的意思），这棵神奇的树是在Rudolf Bayer, Edward M. McCreight(1970)写的一篇论文《Organization and Maintenance of Large Ordered Indices》中首次提出的。

B树的各种操作能使B树保持较低的高度，从而有效避免磁盘过于频繁的查找存取操作，达到有效提高查找效率的目的。

B树

定义

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母 m 表示阶数。当 m 取 2 时，就是我们常见的二叉搜索树。

一颗 m 阶的B树定义如下：

  • 每个结点最多有 m-1 个关键字。
  • 根结点最少可以只有 1 个关键字。
  • 非根结点至少有 Math.ceil(m/2)-1 个关键字(向上取整)。
  • 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
  • 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

b树

上图是一颗阶数为 4 的B树。在实际应用中的B树的阶数 m 都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

插入操作

插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

  1. 根据要插入的key的值，找到叶子结点并插入。
  2. 判断当前结点key的个数是否小于等于 m-1 ，若满足则结束，否则进行第 3 步。
  3. 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第 3 步。

下面以 5 阶B树为例，介绍B树的插入操作，在 5 阶B树中，结点最多有 4 个key,最少有 2 个key

a）在空树中插入 39

a

此时根结点就一个key，此时根结点也是叶子结点

b）继续插入 22，97 和 41

b

根结点此时有 4 个key

c）继续插入 53

c1

插入后超过了最大允许的关键字个数 4，所以以key值为 41 为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。当阶数 m 为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

c2

d）依次插入 13，21，40，同样会造成分裂，结果如下图所示。

d

e）依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。

e

f）插入key值为 26 的记录，插入后的结果如下图所示。

f1

当前结点需要以 27 为中心分裂，并向父结点进位 27，然后当前结点指向父结点，结果如下图所示。

f2

进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

f

分裂后当前结点指向新的根，此时无需调整。

g）最后再依次插入key为 17,28,29,31,32 的记录，结果如下图所示。

g

在实现B树的代码中，为了使代码编写更加容易，我们可以将结点中存储记录的数组长度定义为 m 而非 m-1，这样方便底层的结点由于分裂向上层插入一个记录时，上层有多余的位置存储这个记录。同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

一般来说，对于确定的 m 和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况， 比如key为 28,29 所在的结点，还有 2 个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是 27 ,后继key是 30 ,所有整数值都用完了。 所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。这里的浪费问题可以进行优化，具体讨论见 从MySQL Bug#67718浅谈B+树索引的分裂优化

删除操作

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

  1. 如果当前需要删除的 key 位于非叶子结点上，则用后继 key （这里的后继 key 均指后继记录的意思）覆盖要删除的 key，然后在后继 key 所在的子支中删除该后继 key 。此时后继 key 一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第 2 步

  2. 该结点key个数大于等于 Math.ceil(m/2)-1，结束删除操作，否则执行第 3 步。

  3. 如果兄弟结点 key 个数大于 Math.ceil(m/2)-1，则父结点中的 key 下移到该结点，兄弟结点中的一个 key 上移，删除操作结束。

否则，将父结点中的 key 下移与当前结点及它的兄弟结点中的 key 合并，形成一个新的结点。原父结点中的 key 的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第 2 步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以 5 阶B树为例，介绍B树的删除操作，5 阶B树中，结点最多有 4 个key,最少有 2 个key

a）原始状态

a

b）在上面的B树中删除 21 ，删除后结点中的关键字个数仍然大于等 2，所以删除结束。

b

c）在上述情况下接着删除 27。从上图可知 27 位于非叶子结点中，所以用 27 的后继替换它。从图中可以看出，27 的后继为 28，我们用 28 替换 27，然后在 28（原 27 ）的右孩子结点中删除28。删除后的结果如下图所示。

c1

删除后发现，当前叶子结点的记录的个数小于 2 ，而它的兄弟结点中有 3 个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的 28 下移，兄弟结点中的 26 上移,删除结束。结果如下图所示。

c2

d）在上述情况下接着删除 32 ，结果如下图。

d1

当删除后，当前结点中只有 1 个 key，而兄弟结点中也仅有 2 个 key。所以只能让父结点中的 30 下移和这个两个孩子结点中的 key 合并成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

d2

当前结点 key 的个数满足条件，故删除结束。

e）上述情况下，我们接着删除 key 为 40 的记录，删除后结果如下图所示。

e1

同理，当前结点的记录数小于 2 ，兄弟结点中没有多余 key，所以父结点中的 key 下移和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

e2

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

e3

合并后结点当前结点满足条件，删除结束。

B+树

B+树的定义

b+

各种资料上 B+ 树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小 1，这种方式是和B树基本等价的。上图就是一颗阶数为 4 的B+树。

除此之外B+树还有以下的要求:

  • B+ 树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。
  • B+ 树与B 树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
  • m 阶 B+ 树表示了内部结点最多有 m-1 个关键字（或者说内部结点最多有m个子树），阶数 m 同时限制了叶子结点最多存储 m-1 个记录。
  • 内部结点中的 key 都按照从小到大的顺序排列，对于内部结点中的一个 key，左树中的所有 key 都小于它，右子树中的 key 都大于等于它。叶子结点中的记录也按照 key 的大小排列。
  • 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

插入操作

  1. 若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。

  2. 针对叶子类型结点：根据 key 值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于 m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的 key 进位到父结点中（父结点一定是索引类型结点），进位到父结点的 key 左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第 3 步。

  3. 针对索引类型结点：若当前结点 key 的个数小于等于 m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前 (m-1)/2 个 key，右结点包含 m-(m-1)/2 个key，将第 m/2 个 key 进位到父结点中，进位到父结点的 key 左孩子指向左结点, 进位到父结点的 key 右孩子指向右结点。将当前结点的指针指向父结点，然后重复第 3 步。

下面是一颗 5 阶B树的插入过程，5阶B数的结点最少 2 个key，最多 4 个key。

a）空树中插入 5

a

b）依次插入 8，10，15

b

c）插入 16

c1

插入 16 后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点 2 个记录，右边 3 个记录，中间 key 成为索引结点中的 key，分裂后当前结点指向了父结点（根结点）。结果如下图所示。

c2

当然我们还有另一种分裂方式，给左结点 3 个记录，右结点 2 个记录，此时索引结点中的key就变为 15。

d）插入 17

d

e）插入 18，插入后如下图所示

e

当前结点的关键字个数大于 5，进行分裂。分裂成两个结点，左结点 2 个记录，右结点 3 个记录，关键字 16 进位到父结点（索引类型）中，将当前结点的指针指向父结点。

e2

当前结点的关键字个数满足条件，插入结束。

f）插入若干数据后

f

g）在上图中插入 7，结果如下图所示

g1

当前结点的关键字个数超过 4，需要分裂。左结点 2 个记录，右结点 3 个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

g2

当前结点的关键字个数超过 4 ，需要继续分裂。左结点 2 个关键字，右结点 2 个关键字，关键字 16 进入到父结点中，将当前结点指向父结点，结果如下图所示。

g3

当前结点的关键字个数满足条件，插入结束。

删除操作

如果叶子结点中没有相应的 key，则删除失败。否则执行下面的步骤:

  1. 删除叶子结点中对应的 key。删除后若结点的 key 的个数大于等于 Math.ceil(m-1)/2 – 1 ，删除操作结束,否则执行第 2 步。

  2. 若兄弟结点 key 有富余（> Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的 key 替换父结（指当前结点和兄弟结点共同的父结点）点中的 key，删除结束。否则执行第 3 步。

  3. 若兄弟结点中没有富余的 key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的 key（父结点中的这个 key 两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第 4 步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。

  4. 若索引结点的 key 的个数大于等于 Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第 5 步

  5. 若兄弟结点有富余，父结点 key 下移，兄弟结点 key 上移，删除结束。否则执行第 6 步

  6. 当前结点和兄弟结点及父结点下移 key 合并成一个新的结点。将当前结点指向父结点，重复第 4 步。

注意，通过 B+ 树的删除操作后，索引结点中存在的 key，不一定在叶子结点中存在对应的记录。

下面是一颗 5 阶 B 树的删除过程，5 阶B数的结点最少 2 个key，最多 4 个key。

a）初始状态

a

b）删除 22 ,删除后结果如下图

b

删除后叶子结点中 key 的个数大于等于 2 ，删除结束

c）删除 15 ，删除后的结果如下图所示

c1

删除后当前结点只有一个 key,不满足条件，而兄弟结点有三个 key，可以从兄弟结点借一个关键字为 9 的记录,同时更新将父结点中的关键字由 10 也变为 9 ，删除结束。

c2

d）删除 7 ，删除后的结果如下图所示

d

当前结点关键字个数小于 2 ，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。

d2

此时当前结点的关键字个数小于 2 ，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。

d3

B*树

B* 树是 B+ 树的变种，相对于 B+ 树他们的不同之处如下：

  • 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是 cei(m/2)，B* 树的初始化个数为 cei(2/3*m)

  • B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出 1/3 的数据创建一个新的节点出来；

特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

比较

  • B+树的层级更少：相较于B树B+每个非叶子节点中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”，树的层级更少所以查询数据更快, IO 少；

举个例子，假设磁盘中的一个盘块容纳 16 bytes，而一个关键字 2 bytes ，一个关键字具体信息指针 2 bytes。一棵 9 阶B-tree(一个结点最多 8 个关键字)的内部结点需要 2 个盘块。而B+树内部结点只需要 1 个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

  • B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的路径长度都相同所以查询速度要比B树更稳定;

  • B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历

  • B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是: 如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

应用

文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

Windows：HPFS 文件系统

Mac：HFS，HFS+ 文件系统

Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统

数据库：ORACLE，MYSQL，SQLSERVER 等中

数据库：ORACLE，MYSQL，SQLSERVER 等中

参考文献