B 树、B+树、二叉搜索树与红黑树

发表于 更新于 分类于 Disqus： 本文字数： 4k

前言

B 树是一种用于索引外部存储数据的数据结构。许多数据库系统与文件系统都有它或者它的变体的应用。我们在这里讨论 B 树，B+ 树以及其他的树，为理解基于 B+ 树的 iDistance 算法打下基础。

为什么需要 B 树（和其他平衡树）

我们早就知道可以构造这样的树：比根小的扔左边，比根大的扔右边，这样就可以轻松构建一个有序的结构了。但是如果根的左右两边不平衡，显然就会导致找其中一边化的时间比较变长。因此我们就需要一些把树变平衡的方法。由是得到平衡查找树。

平衡的方法各有不同，对于本文介绍的树们，它们的逻辑关系是这样的：

  • 由于二叉查找树的不平衡性，人们设计 AVL 树。它通过左右旋保证左右子树高度差不超过 1；
  • AVL 树严格的平衡反而导致开销过大，于是设计了不那么严格的红黑树。红黑树通过两种颜色的区别，保证左右高度差不超过一倍；
  • B 树从另一个角度入手，一个结点上存多个值叉分出多个子树，通过“限定结点上值的数量”和“叶子结点都在同一层”，保证平衡。由于一个结点上有多个值，树比二叉树浅，适合磁盘上存储大量数据的数据库采用。
  • B+ 树把值全存在叶子结点上，相比 B 树检索速度更稳定。此外遍历和排序也都更方便了。
  • B* 树在 B+ 树的基础上提高了结点拆分合并的时间，因为一个结点被从兄弟中创建出来的时候拥有了上限的 2/3 而不是 1/2 的结点，需要拆分的次数降低了。

AVL 树

AVL 树是最先发明的自平衡二叉查找树。 在AVL树中任何节点的两个子树的高度最大差别为 1 。

AVL树增删操作后需要把失去平衡的结点重新变平衡。为此，引入左旋和右旋操作：

左旋

上图将 A 为根结点在树进行左旋，得到 B （原右孩子）为根结点的树。这个过程可以如下描述：

  1. B 的左子树成为 A 的右子树；
  2. A 成为 B 的新左子树；
  3. B 成为新的根结点；

类似地，右旋就有：（假设 A 是根结点，C 是 A 左结点）

  1. C 的右子树成为 A 的左子树；
  2. A 成为 C 的新左子树；
  3. C 成为新的根结点；

我们现在可以讨论 AVL 树的再平衡了。

我们规定一个结点左右子树高度差绝对值是平衡因子，那么 AVL 数平衡因子只能是 0 或 1。

显然一个结点（下的子树）失衡，说明之前其平衡因子是 1，现在变成了 2。这也说明，新结点插入的那个子树原先较长而且插入一个结点使其变得更长了。于是最靠近插入结点的失衡结点的一个子树现在的平衡因子必然为 1。

不平衡树

假设是插入在左子树。对于结点插入在左子树的左边的情况（左），我们可以把不平衡节点的子树右旋，使得插入了结点的左子树成为新根结点，则树恢复平衡。插入右边的情况，则先对左子树进行左旋，再对根结点右旋。插入在右子树的情况是类似的。总结如下：

对于最靠近插入结点的失衡结点 A：

  • 插入结点在 A 的左结点 B 的左子树上：A 右旋
  • 插入结点在 A 的左结点 B 的右子树上：B 左旋，再 A 右旋
  • 插入结点在 A 的右结点 C 的右子树上：A 左旋
  • 插入结点在 A 的右结点 C 的左子树上：C 右旋，再 A 左旋

红黑树

AVL 树对平衡要求很高，左右旋又是较为耗时的操作，增删比较频繁时，付出的代价甚至可能比获得的效率收益还多，故而它只适合用于插入删除次数比较少的情况，实际应用不多。

红黑树是对 AVL 树的一种改进，它只保证最长路径不超过最短路径的两倍，是一种弱平衡二叉树。因为平衡要求没那么严格，所以增删花费时间少，查询时间则有所增多。

红黑树每个结点非红即黑，而且有：

  1. 根节点、叶节点（请注意，叶子结点是 NULL 结点）都是黑的；
  2. 红结点的两儿子都是黑的；
  3. 对于任意节点而言，到其下叶子结点路径都包含相同数目的黑结点；
  4. 高度始终保持在h = logn

红黑树的插入

记新结点为 N，其父结点为 P，父结点的兄弟结点（叔父结点）为 U，父结点的父结点为祖父结点 G。首先，我们将结点 N 插入到树中，并标记它的颜色为红色。检查此时的情况：

  1. P 不存在，N 是根结点：把 N 染黑。
  2. P 是黑结点：什么都不用干。因为 N 取代了一个黑空节点，到达 N 下空结点经过的黑色结点数没有变。
  3. P 是红结点，此时 G 结点必存在为黑节点。
    1. P、U 都是红结点：P、U 染黑。
      1. G 是根结点：不动。
      2. G 不是根结点：染红。
      • 如果不动 PU，把 N 染黑，那么 G 到达 N 下结点经过的黑结点数就会比去 N 兄弟的路径多一个。
      • 如果不染 G，那么 G 的父亲到达 G 下结点经过的黑结点数就会比去 G 兄弟经过的多一个。
    2. P 左红 U 右黑，N 是右节点(记为 LR )：对 P 左旋，然后对 G 右旋，P 染黑，G 染红。

      左旋一次以后，变为下面的 LL 情况。

    3. P 左红 U 右黑，N 是左节点：对 G 右旋，P 染黑，G 染红。

      N 的插入不会导致经过的黑色结点数发生改变，但是 P 子树深了一层，所以不管改 P 还是 N 都会导致经过黑点增加，除非同时通过 G 把增加黑点数减掉，但是这同时会导致 U 子树方向少掉一个黑点， P 子树还是多一个，因此通过单纯的染色是无法解决问题的。
      通过旋转操作，相当于把 P、N 两个都在 P 子树的红点移了一个到 U 子树。由于 G、U 都是黑结点，因此在里面插一个红点不会有影响。这样就两边都没有红点相连的情况了。

    4. P 右红 U 左黑：对照上面对称处理。

      注意这些情况和 AVL 树的再平衡的相似。

红黑树的删除

假设删除的结点是 D

  1. 如果左右子树均不为空：将左子树中的最大值或右子树中的最小值挪过来覆盖，然后删除原来其在的结点。这个结点是最值，那么显然不可能有两个有值的孩子，于是转化为下面的情况。
  2. 左右子树至少有一个为空：
    1. D 是红结点：那么父结点和子结点都是黑色结点，直接接一起就完了。（当然优先的不空的子树）
    2. D 是黑结点，且非空孩子是红结点：删除 D，把非空孩子移上来并染黑。
    3. D 是黑结点：可知两个孩子都为黑空，将 D 变成黑空，可知此时 D 子树少了一个黑色结点，然后有下面若干种情况。

假设删除的结点是 D，D 的父亲 P，兄弟 U，U 的左右孩子 NL，NR：

  1. 情况1：P 为空， D 是根结点：什么都不用干；
  2. P 为黑
    1. 情况2： U 为黑，NL，NR也为黑：U 变红，U 子树减一个黑色接结点；然后 P 子树减少了一个黑结点，对 P 思考该问题；
    2. 情况3： U 为红：对 P 左旋；然后 P 变红， U 变黑。然后情况 4, 5, 6：

      相当于将兄弟子树的一个红节点拿了过来。

    3. 情况5： NL 为红，NR 为黑：U 右旋，NL 变红 ，U 变黑，变成情况 6；
    4. 情况6： NL 为黑，NR 为红：P 左旋，U 变 P 的颜色(黑)，P 变黑，U 的颜色，NR 变黑。

      根结点的颜色不变，根的左子树补了一个黑结点（U）。

  3. P 为红，U 为黑：
    1. 情况4： U 的孩子都为黑：对换 P、U 的颜色；
    2. 情况5： NL 为红，NR 为黑：U 右旋，NL 变红 ，U 变黑，变成情况 6；
    3. 情况6： NL 为黑，NR 为红：P 左旋，U 变 P 的颜色(红)，P 变黑，U 的颜色，NR 变黑。

      根结点的颜色不变，根的左子树补了一个黑结点（P）。

B树

B 树（B-Tree）， B 普遍来说被认为是 Balanced 的意思，因为这是一种自平衡树。

有的地方翻译为 B-树，容易给人一种是 B “减”树的错觉，事实上 B-Tree 就是 B 树。

如果数据太大，我们就无法在内存中放下整个树，同时我们知道磁盘读取速度远慢于内存。因此这种情况下我们对“读取”操作非常敏感。如果是不够平衡的树，或者深度太深，检索速度就会很慢。在数据库应用中，B树的每个节点存储的数据量大约为4K, 这是因为磁盘数据存储每个块的大小为通常为 4K，这样每次磁盘 IO 可以读写刚好一个数据库结点。

B 树是多叉树，而且每个结点能存储多个值。它定义如下：

  1. 一个结点能存储多个值，这些值称之为键。
  2. 度：定义一颗树的度为 t(t≥2t\geq 2)。度能决定树内的结点有多少键：
    1. 空树：0个；
    2. 根结点:[1,2t−1][1,2t-1] 个；
    3. 普通结点：[t−1,2t−1][t-1,2t-1]个。
  3. 子结点数：自己的键数 +1 个。一个键把数轴划为两个区间， n 个键自然就是 n+1 个区间。
  4. 叶子结点都在同一层。

例如：t = 2。此时的 B 树内部节点可以有 2、3 或 4 个孩子，称之为 2-3-4 树。

B 树的检索

在树 T 中检索关键字 k 的逻辑如下：

  1. 首先，查找 k 和 T 根结点的区间关系。
    1. 如果落在一个键上，那么就搜索到了 k 是 T.root 的第 i 关键字。
    2. 否则，继续第二步
  2. 在 k 落在区间的对应孩子上继续搜索。
  3. 当前结点没有孩子，说明没找到。

B 树的插入

逻辑：

  • 如果结点的键槽没有满：结点添加一个新键。
  • 如果结点满了（2t-1个键）：那把此结点的键分为三份，最中间的键插入到父结点，左右分裂为两个有 t-1 个键的结点。其孩子也对应分配给新分裂出来的结点。
    • 如果父节点也满了：递归重复上面过程。
    • 如果根结点都满了：创建一个空结点为新的根结点，然后分裂根结点

实际我们在确定新键位置的过程中，就沿途分裂了所有遇到的满结点。因此实际上这不是一个递归过程。

B 树的删除

假设问题是删除结点 x 中的键 k：

  1. 不少于 t-1 个键的叶子结点删除：直接删除；
  2. 内部结点：
    1. 找到 k 前面的区间对应的子结点 y，看是否有至少 t 个键：
      1. 如果 y 至少有 t 个键：找到结点 y 中最后一个键 k’（即 k 的前驱）。执行“删除结点 y 中 k’ 键”的操作。x 中用 k’ 替换 k。
    2. 否则：找到 k 后面的区间对应的子结点 z，看是否有至少 t 个键：
      1. 如果有：找到结点 z 中最后一个键 k’（即 k 的后继）。执行“删除结点 z 中 k’ 键”的操作。x 中用 k’ 替换 k。
    3. 否则：此时 y 和 z 加起来就只有 2t-2 个键。把键 k 和结点 z 都合并进 y。然后再在 y 中删除 k；
  3. 由上向下找 k 时如果确定 k 在一颗以 x 为根的子树中，并且 x 只有 t-1 个键，设 x 的父结点为 p：
    1. x 的一个相邻兄弟（y/z）结点有至少 t 个键：删除此键。根据是 y 或者 z，从 p 中对应给一个键给 x。从 y/z 中对应给一个键给 p；
    2. 相邻兄弟也只有 t-1 个键：合并 x 和 y/z、p 中由两个子结点夹着的键。如果p 是根结点而且本来就只有一个键，那么树的高度就缩减了。

B+ 树

B+ 树的特点是在 B 树上做了如下改动：

  • 非叶子结点不存值，只有子结点的头元素的索引。即一个键（子结点头元素值）对应一个指向子结点的指针。
  • 相邻叶子结点之间用指针直接串连。
  • 根结点至少一个元素，非根结点有 [m/2, m-1] 个元素。其中 m 是 B+ 树的阶。

这样一来 B+ 树的查询速度基本恒定。

此外 B+ 树还有以下好处

  • 遍历快：因为块与块之间有指针
  • 天然排序：例如我我们想取一个区间内的数据，取出来就是有序的。

B+ 树的插入

当节点元素数量大于 m-1 ：按中间元素分裂成左右两部分，中间元素是右半部分的头结点。同时父节点添加中间元素当做索引。

B+ 树的删除

因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可。

  • 删除元素后依然满足要求：直接删除

  • 删除后元素个数不够

    • 兄弟结点有多余元素：向兄弟要一个元素，修改父结点的索引值；
    • 兄弟结点无多余元素：和兄弟合并。递归删除父结点的索引。

  • 删除元素后

B* 树

很显然，B* 树又是对B+数的再一次改进，在 B+ 树的构建过程中，为了保持树的平衡，节点的合并拆分是比较耗费时间的，所以 B* 树就是在如何减少构建中节点合并和拆分的次数，从而提升树的数据插入、删除性能。

  • 一个结点创建的时候有 upper(2/3)mupper(2/3)m 的键，而不是 upper(m/2)upper(m/2)；
  • 如果结点存满了，检查兄弟结点是否是满的：
    • 不是满的：向兄弟节点转移关键字；
    • 也是满的：和兄弟结点各拿 1/3 创建一个新结点；

参考

  1. 面试官问你B树和B+树，就把这篇文章丢给他 - 好好学java - SegmentFault 思否
  2. 二叉搜索树(BST)与平衡二叉树(AVL) - 知乎
  3. 万字大总结，一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树 - 知乎
  4. 红黑树 - 维基百科，自由的百科全书
  5. 《算法导论》