B 树

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

鲁道夫·拜尔（Rudolf Bayer）和 艾华·M·麦克雷（Ed M. McCreight）于1972年在波音研究实验室（Boeing Research Labs）工作时发明了 B 树，但是他们没有解释B代表什么意义。

变体

狭义上，一个Ｂ树在它内部节点中存储键值，但不需在叶子节点上存储这些键值的记录。大体上的一类包含一些变体，B+树 和 B*树

在B+树，这些键值的拷贝被存储在内部节点；键值和记录存储在叶子节点；另外，一个叶子节点可以包含一个指针，指向另一个叶子节点以加速顺序存取。

B*树分支出更多的内部邻居节点以保持内部节点更密集地填充。此变体要求非根节点至少2/3填充，而不是1/2。为了维持这样的结构，当一个节点填满之后将不会再立即分割节点，而是将它的键值与下一个节点共享。当两个节点都填满之后，分割成3个节点。

术语与定义

在一些设计中，叶子可能保存了完整的数据记录；在另一些设计中，叶子可能只保存了指向数据记录的指针。

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个键
• 所有的叶子节点都在同一层

算法

搜索

B树的搜索和二叉搜索树类似。从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。子树值的范围被它的父节点的键确定。

插入

所有的插入都从根节点开始。要插入一个新的元素，首先搜索这棵树找到新元素应该被添加到的对应节点。将新元素插入到这一节点中的步骤如下：

• 如果节点拥有的元素数量小于最大值，那么有空间容纳新的元素。将新元素插入到这一节点，且保持节点中元素有序。
• 否则的话这一节点已经满了，将它平均地分裂成两个节点：
  • 从该节点的原有元素和新的元素中选择出中位数
  • 小于这一中位数的元素放入左边节点，大于这一中位数的元素放入右边节点，中位数作为分隔值。
  • 分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。

如果分裂一直上升到根节点，那么一个新的根节点会被创建，它有一个分隔值和两个子节点。这就是根节点并不像内部节点一样有最少子节点数量限制的原因。每个节点中元素的最大数量是 U-1。当一个节点分裂时，一个元素被移动到它的父节点，但是一个新的元素增加了进来。所以最大的元素数量 U-1 必须能够被分成两个合法的节点。如果 U-1 是奇数，那么 U=2L ，总共有 2L-1 个元素，一个新的节点有 L-1 个元素，另外一个有 L 个元素，都是合法的节点。如果 U-1 是偶数，那么 U=2L-1,总共有 2L-2 个元素。 一半是 L-1，正好是节点允许的最小元素数量。

删除

有两种常用的删除策略

• 定位并删除元素，然后调整树使它满足约束条件； 或者
• 从上到下处理这棵树，在进入一个节点之前，调整树使得之后一旦遇到了要删除的键，它可以被直接删除而不需要再进行调整

删除叶子节点中的元素:

• 搜索要删除的元素
• 如果它在叶子节点，将它从中删除
• 如果发生了下溢出，按照后面 “删除后重新平衡”部分的描述重新调整树

删除内部节点中的元素:

内部节点中的每一个元素都作为分隔两颗子树的分隔值，因此我们需要重新划分。值得注意的是左子树中最大的元素仍然小于分隔值。同样的，右子树中最小的元素仍然大于分隔值。这两个元素都在叶子节点中，并且任何一个都可以作为两颗子树的新分隔值。算法的描述如下：

• 选择一个新的分隔符（左子树中最大的元素或右子树中最小的元素），将它从叶子节点中移除，替换掉被删除的元素作为新的分隔值。
• 前一步删除了一个叶子节点中的元素。如果这个叶子节点拥有的元素数量小于最低要求，那么从这一叶子节点开始重新进行平衡。

删除后的重新平衡:

重新平衡从叶子节点开始向根节点进行，直到树重新平衡。如果删除节点中的一个元素使该节点的元素数量低于最小值，那么一些元素必须被重新分配。通常，移动一个元素数量大于最小值的兄弟节点中的元素。如果兄弟节点都没有多余的元素，那么缺少元素的节点就必须要和他的兄弟节点 合并。合并可能导致父节点失去了分隔值，所以父节点可能缺少元素并需要重新平衡。合并和重新平衡可能一直进行到根节点，根节点变成惟一缺少元素的节点。重新平衡树的算法如:

• 如果缺少元素节点的右兄弟存在且拥有多余的元素，那么向左旋转
  1. 将父节点的分隔值复制到缺少元素节点的最后（分隔值被移下来；缺少元素的节点现在有最小数量的元素）
  2. 将父节点的分隔值替换为右兄弟的第一个元素（右兄弟失去了一个节点但仍然拥有最小数量的元素）
  3. 树又重新平衡
• 否则，如果缺少元素节点的左兄弟存在且拥有多余的元素，那么向右旋转
  1. 将父节点的分隔值复制到缺少元素节点的第一个节点（分隔值被移下来；缺少元素的节点现在有最小数量的元素）
  2. 将父节点的分隔值替换为左兄弟的最后一个元素（左兄弟失去了一个节点但仍然拥有最小数量的元素）
  3. 树又重新平衡
• 否则，如果它的两个直接兄弟节点都只有最小数量的元素，那么将它与一个直接兄弟节点以及父节点中它们的分隔值合并
  1. 将分隔值复制到左边的节点（左边的节点可以是缺少元素的节点或者拥有最小数量元素的兄弟节点）
  2. 将右边节点中所有的元素移动到左边节点（左边节点现在拥有最大数量的元素，右边节点为空）
  3. 将父节点中的分隔值和空的右子树移除（父节点失去了一个元素）
     • 如果父节点是根节点并且没有元素了，那么释放它并且让合并之后的节点成为新的根节点（树的深度减小）
     • 否则，如果父节点的元素数量小于最小值，重新平衡父节点

附录

• https://www.cs.usfca.edu/~galles/visualization/Algorithms.html