65.9K
CodeProject 正在变化。 阅读更多。
Home

B-Tree：Java 的另一个实现

Tung.Nguyen.2k
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.28/5 (13投票s)

2016年11月30日

Apache

17分钟阅读

viewsIcon

78494

downloadIcon

2809

如何在Java中实现B-Tree的查找、插入和删除

引言

对于像我一样学习计算机科学专业的大学生来说，B-Tree 应该很熟悉。它的最初目的是通过尽可能减少存储 I/O 操作来缩短计算机硬盘的访问时间。这项技术在数据库和文件系统等计算机领域得到了很好的应用。随着大数据和 NoSQL 分布式数据库系统的发展（得益于廉价的硬件和互联网的增长），B-Tree 及其变种在数据存储方面发挥着比以往更重要的作用。

在本文中，我将不讨论 B-Tree 操作的性能和时间度量。这些细节可以在 [1] 和 [2] 中找到。相反，我将花费大部分时间来讨论和解释如何使用 Java 来实现 B-Tree 数据结构和实现，尽我最大的努力。

要求

  • 构建核心 B-Tree 及其所有测试用例需要 JDK 6+
  • 如果您想构建使用 JGraphX 的 B-Tree 渲染工具，则需要 JDK 8

什么是 B-Tree？

B-Tree 是一种自平衡树（即所有叶子节点具有相同的高度级别）数据结构。但是，与二叉树、红黑树和 AVL 树等只有 2 个子节点（左子节点和右子节点）的树不同，B-Tree 的节点可以有 2 个以上的子节点。因此，有时也称为 M 路分支树，因为一个 B-Tree 节点可以有 M 个子节点（M >= 2）。

图 1：  B-Tree 示例

根节点、内部节点和叶子节点

内部节点是有子节点的节点。内部节点位于树的上方。在图 1 中，节点 [3 | 6]、节点 [12 | 15 | 19| 26] 和节点 [33 | 36] 是内部节点。

叶子节点是没有子节点的节点。它们是树底部的节点。在图 1 中，节点 [1 | 2]、节点 [4 | 5]、节点 [20 | 22 | 25] 和节点 [31 | 32] 是一些叶子节点。

B-Tree 的根节点是一个特殊的节点。B-Tree 只有一个根节点，它位于树的顶部。根据 B-Tree 中项目的数量，根节点可以是内部节点或叶子节点。节点 [9 | 30] 是图 1 中 B-Tree 的根节点。

B-Tree 节点属性

每个节点可以包含一组键和一组子节点（子节点），其中子节点的数量可以是 0，也可以是其键的总数加 1。考虑节点 [x]。如果节点 [x] 是叶子节点，则它没有子节点。如果它是内部节点，则其子节点总数为 n[x] + 1，其中 n[x] 是其键的总数。

B-Tree 的约束

令 t 为 B-Tree 的最小度数，其中 t >= 2

约束 #1：除根节点外，每个节点必须至少有 (t – 1) 个键。这是 B-Tree 节点中键的总数的下限。

约束 #2：包括根节点在内的每个节点最多必须有 (2t – 1) 个键。因此，如果一个节点有 (2t – 1) 个键，我们就说它是满的。这是 B-Tree 节点中键的总数的上限。

约束 #3：除根节点外，每个内部节点必须至少有 t 个子节点。每个内部节点（包括根节点）最多必须有 2t 个子节点。

约束 #4：节点中的键必须按升序存储。例如，在图 1 中，节点 [12 | 15 | 19 | 26] 的键为 12 < 15 < 19 < 26

约束 #5：位于键左侧的所有子节点的键都必须小于该键。在图 1 中，位于键 30 左侧的子节点，其节点 [12 | 15 | 19 | 26]、节点 [10 | 11]、节点 [13 | 14]、节点 [16 | 18]、节点 [20 | 22 | 25] 和节点 [28 | 29] 的键都小于 30。

约束 #6：位于键右侧的所有子节点的键都必须大于该键。例如，在图 1 中，位于键 9 右侧的子节点，其节点 [12 | 15 | 19 | 26]、节点 [10 | 11]、节点 [13 | 14]、节点 [16 | 18]、节点 [20 | 22 | 25] 和节点 [28 | 29] 的键都大于 9。

根据约束 #4 和约束 #5，通常位于键左侧的所有节点中的键都必须小于该键。

根据约束 #4 和约束 #6，通常位于键右侧的所有节点中的键都必须大于该键。

在图 1 中，B-Tree 的最小度数为 3。因此，其下限为 2，上限为 5。

如果您仔细观察图 1 中的 B-Tree 示例，您会注意到任何节点中的一个键实际上是该键两侧较低层级节点中所有键的范围分隔符。

我们来看节点 [9 | 30]，位于键 9 左侧的较低层级节点（由蓝色箭头连接的节点）的键都小于 9。位于键 9 右侧的较低层级节点（由绿色箭头连接的节点）的键都大于 9。位于键 30 左侧的较低层级节点（由绿色箭头连接的节点）的键都小于 30。位于键 30 右侧的较低层级节点（由红色箭头连接的节点）的键都大于 30。B-Tree 的这种模式使得键查找类似于二叉树的键查找。

只要 B-Tree 操作不违反上述约束，它就会自动自平衡。换句话说，这些约束的设计是为了保持其平衡性。

最小度数 (t) 与 B-Tree 高度 (h) 成反比。增加 t 会减小 h。然而，较大的 t 意味着在节点中花费更多时间来查找键和遍历子节点。

B-Tree 操作的概念和伪代码

为了理解键查找、插入和删除等基本 B-Tree 操作是如何实现的，在深入了解完整实现细节之前，我想介绍一些关键概念。

左右兄弟节点

节点的左右兄弟节点是同一层级上位于其右侧和左侧的节点。

图 2：  节点兄弟

在图 2 中，节点 [18 | 22] 的左兄弟节点是 [3 | 12]，右兄弟节点是 [33 | 36]。节点 [3 | 2] 没有左兄弟节点，它的右兄弟节点是 [18 | 22]。节点 [33 | 36] 的左兄弟节点是 [18 | 22]，它没有右兄弟节点。

(内部)节点键的前驱和后继

在本篇内容中，这里提到的特定节点中的键的前驱和后继仅适用于内部节点。

前驱是位于键左侧子树内的叶子节点，它包含该子树中最大的键。

对称地，后继是位于键右侧子树内的叶子节点，它包含该子树中最小的键。

图 3：键的前驱和后继

在图 3 中，键 17 的前驱是节点 [13 | 14 | 16]，因为键 16 是其左侧的最大键。键 17 的后继是节点 [19 | 20 | 21]，因为键 19 是其右侧的最小键。

类似地，键 12 的前驱是节点 [4 | 7 | 6 | 10]，因为键 10 是其左侧的最大键；其后继是节点 [13 | 14 | 16]，因为键 13 是其右侧的最小键。

分裂节点

对于插入操作，如果我们即将插入的节点已满（有时也称为溢出），我们需要分裂一个节点，以避免违反约束 #2。

图 4-a：B-Tree 中的分裂

图 4-a：B-Tree 中的另一个分裂

左旋和右旋

对于删除操作，从节点中删除一个键可能会违反约束 #1（有时也称为欠载）。如果其左兄弟或右兄弟节点拥有的键数大于下限，我们可以将该节点的一个键“借”给它。

图 5-a：左旋

图 5-b：右旋

与左兄弟节点或右兄弟节点合并

对于删除操作，如果不能进行左旋/右旋（即左兄弟或右兄弟节点的键总数正好等于下限，它们没有多余的键可以移到其他节点），那么就必须发生该节点与其一个兄弟节点的合并。

图 6：与左兄弟节点合并

实现 B-Tree 操作的通用概念

B-Tree 的键查找简单明了。如果您熟悉二叉树查找，那么您可以毫不费力地实现它。尽管如此，与二叉树不同，在 B-Tree 中，您需要遍历节点中的键数组来验证搜索的键是否在该节点中。如果不在，我们需要决定选择哪个子节点进一步查找。键插入使用更复杂的逻辑，而键删除则最复杂。然而，在高层次上，B-Tree 的插入和删除很容易理解：键插入涉及分裂节点，键删除涉及旋转和合并。就是这么简单。为了使键插入和删除成为可能，我们需要注意的一个重要事项是：在对特定键执行这些操作之前，它必须位于叶子节点中。如果键位于内部节点中，我们需要将其与叶子节点中的适当键进行交换。有了这种策略，我们就无需担心添加或删除键后的节点子节点。

键查找

Key-Search (searched-key)

    Current-Processed-Node = Root-Node

    While (Current-Processed-Node is not NULL)
        Current-Index = 0

        While ((Current-Index < key number of Current-Processed-Node) AND
                (searched-key > Current-Processed-Node.Keys[Current-Index]))
            Current-Index++
        End While


        If ((Current-Index < key number of Current-Processed-Node) AND
             (searched-key == Current-Processed-Node.Keys[Current-Index]))
            searched-key is found
            Return it (We are done)

        End If

        Current-Processed-Node = Left/Right Child of Current-Processed-Node
    End While

    Return NULL

键插入

图 7：键插入示例

Split-Node(parent-node, splitted-node)

    Create new-node
    Leaf[new-node] = Leaf[splitted-node]  (The new node must have the same leaf info)

    Copy right half of the keys from splitted-node to the new node

    If (Leaf[splitted-node] is FALSE) Then
        Copy right half of the child pointers from spitted-node to the new node
    End If

    Move some of parent children to the right accordingly

    parent-node.children[relevant index] = new-node

    Move some of parent keys to the right accordingly as well

    Parent-node.keys[relevant index] = splitted-node.keys[the right-most index]
Insert-Key-To-Node(current-node, inserted-key)

    If (Leaf[current-node] == TRUE) Then
        Put inserted-key in the node in ascending order
        Return (We are done)
    End If

    Find the child-node where inserted-key belong

    If (total number of keys in child-node == UPPER BOUND) Then
        Split-Node(current-node, child-node)
        Return Insert-Key-To-Node(current-node, inserted-key)
    End If

    Insert-Key-To-Node(child-node, inserted-key)
Insert-Key(inserted-key)

    If (root-node is NULL) Then
        Allocate for root-node
        Leaf[root-node] = TRUE
    End If


    If (total number of keys in root-node == UPPER BOUND) Then
        Create a new-node
        Assign root-node to be the child pointer of the new-node
        Assign new-node to be the root-node
        Split-Node(new-node, new-node.children[0])
    End If

    Insert-Key-To-Node(new-node, inserted-key)

正如您所见，Split-Node() 和 Insert-Key-To-Node() 是最终由 Insert-Key() 调用的辅助函数。根节点的更新由 Insert-Key() 处理，其余由 Split-Node() 和 Insert-Key-To-Node() 处理。可以看出，键插入始终发生在叶子节点。在插入路径中，如果任何节点已满，我们需要执行分裂并在该点重新启动插入过程。通过这样做，我们可以确保 B-Tree 在键插入时不会出现溢出问题。

键删除

图 8：键删除示例

Delete-Key-From-Node(parent-node, current-node, deleted-key)

    If (Leaf[current-node] == TRUE) Then
        Search for deleted-key in current-node

        If (deleted-key not found) Then
            Return (We are done)
        End If

        If (total number of keys in current-node > LOWER BOUND) Then
            Remove the key in current-node
            Return (We are done)
        End If

        Get left-sibling-node and right-sibling-node of current-node

        If (left-sibling-node is found AND total number of keys in left-sibling-node > LOWER BOUND) Then
            Remove deleted-key from current-node
            Perform right rotation
            Return (We are done)
        End If

        If (right-sibling-node is found AND total number of keys in right-sibling-node > LOWER BOUND) Then
            Remove deleted-key from current-node
            Perform left rotation
            Return (We are done)
        End If

        If (left-sibling-node is not NULL) Then
            Merge current-node with left-sibling-node
        Else
            Merge current-node with right-sibling-node
        End If

        Return Rebalance-BTree-Upward(current-node)
    End If

    Find predecessor-node of current-node

    Swap the right-most key of predecessor-node and deleted-key of current-node

    Delete-Key-From-Node(predecessor-parent-node, predecessor-node, deleted-key)
Rebalance-BTree-Upward(current-node)

    Create Stack

    For each step of the path from root-node to current-node Then
        Stack.push(step-node)
    End For

    While (Stack is not empty) Then
        step-node = Stack.pop()
        If (total number of keys in step-node < LOWER BOUND) Then
            Rebalance-BTree-At-Node(step-node)
        Else
            Return (We are done)
        End If
    End While
Rebalance-BTree-At-Node(step-node)

    If (step-node is NULL OR step-node is root-node) Then
        Return (We are done)
    End If

    Get left-sibling-node and right-sibling-node of step-node

    If (left-sibling-node is found AND total number of keys in left-sibling-node > LOWER BOUND) Then
        Remove deleted-key from step-node
        Perform right rotation
        Return (We are done)
    End If

    If (right-sibling-node is found AND total number of keys in right-sibling-node > LOWER BOUND) Then
        Remove deleted-key from step-node
        Perform left rotation
        Return (We are done)
    End If

    If (left-sibling-node is not NULL) Then
        Merge step-node with left-sibling-node
    Else
        Merge step-node with right-sibling-node
    End If
Delete-Key(deleted-key)

    Delete-Key-From-Node(NULL, root-node, deleted-key)

根据 [2]，B-Tree 中的键删除有两种流行的方法：

  1. 单次遍历树：我们需要在进入节点之前重构树，这样当我们实际从 B-Tree 中删除键时，其结构不会违反任何约束。其删除伪代码可以在 [3] 和 [4] 中找到。
  2. 查找并删除键。但是，我们需要向上重新平衡，因为键删除可能导致 B-Tree 的约束违反。我的键移除实现基于此策略。删除键的主要入口点是 Delete-Key()。稍后，如果需要，将调用 Rebalance-BTree-Upward() 来重构树。重新平衡 B-Tree 主要涉及左旋/右旋以及左/右兄弟节点合并。

B-Tree 的 Java 实现

实现 B-Tree 的源代码附在本文章中。我使用 NetBeans IDE 8 创建了 B-Tree 项目。但是，如果您使用 Eclipse 或其他 Java IDE，将其导入到您的项目中应该很直接。主要的 Java 文件是 BTIteratorIF.java、BTKeyValue.java、BTNode.java 和 BTree.java。泛型类型用于 B-Tree 的键值对，因此任何继承 Comparable 的键都可以使用。

除了 B-Tree 的标准操作外，通过实现其回调接口，还可以有序地迭代所有 B-Tree 条目。暂时就这些。未来的版本可能会实现 Java Collection Iterator 接口，并且可能还会提供仅在指定范围内迭代的功能。

B-Tree 节点不包含有关其父节点的信息。但是，在某些情况下（例如查找其左/右兄弟节点）我们需要节点的父节点。这可能会使实际实现变得有些复杂。

使用代码

使用 B-Tree 简单明了，如下所示：

BTree<Long, String> btree = new BTree<>();
btree.insert(35, "value-35")
     .insert(25, "value-25")
     .insert(12, "value-12")
     .insert(40, "value-40")
     .insert(9, "value-9")
     .insert(4, "value-4")
     .insert(100, "value-100")
     .insert(45, "value-45")
     .insert(80, "value-80")
     .insert(81, "value-81");

String value = btree.search(12);
value = btree.delete(100);

B-Tree 的最小度数可以在 BTNode.java 中找到。它可以修改为任何大于 1 (t >= 2) 的值，并且应该可以正常工作。

B-Tree 的测试用例

对我来说，测试的重要性总是与软件本身同等重要，特别是当我们处理组件内的复杂逻辑时。强调测试的重要性永远不会过多。

我创建了 7 个测试用例来验证我的 B-Tree 实现。它们都在 BTreeTest.java 中。我的测试使用 Java TreeMap 进行键比较和数据验证。

  • 测试用例 0：手动随机设置、查找和删除键。验证键顺序、大小和值的所有项目。
  • 测试用例 1：添加键 1 到 19，并删除其中一些。验证键顺序、大小和值的所有项目。
  • 测试用例 2：添加键 1 到 32，并删除其中一些。验证键顺序、大小和值的所有项目。
  • 测试用例 3：添加键 1 到 50，并删除其中一些。验证键顺序、大小和值的所有项目。
  • 测试用例 4：添加键 1 到 80，并删除 10 到 30。验证键顺序、大小和值的所有项目。
  • 测试用例 5：添加键 0 到 40000，搜索键 -10 到 100，并删除 40000 到 0。验证键顺序、大小和值的所有项目。
  • 测试用例 6：添加键 40000 到 0，搜索键 -10 到 200，并删除 1 到 40000。验证键顺序、大小和值的所有项目。

如果测试因任何原因失败，它将在失败点停止，打印相关信息并退出测试程序。这样我们就可以准确地找出失败的位置。

渲染 B-Tree 的工具

我绝对可以说，当我花时间创建这个工具来以框图形式显示 B-Tree 时，我做出了正确的决定。起初，我以为我只会写一个简单的程序，在控制台以文本格式打印键。后来，当我发现一个名为 JGraphX [6] 的 Java 图形图库时，我改变了主意（顺便说一句，库的 jar 文件包含在 zip 文件中）。这个工具非常值得我花费的时间，甚至更多。它不仅为我节省了大量的纸张，还帮助我在短时间内直观地找出错误的根本原因。

图 9：B-Tree 渲染工具

您可以尝试使用它，通过添加或删除指定的键来玩转 B-Tree。如果您在使用此工具时发现任何错误，只需单击“保存”按钮保存您的步骤，然后将保存的文件发送给我。我将用它来重现错误，并在下次修复它。

我认为这个工具本身值得一篇单独的文章。但是，目前我只是把它放在了这篇文章里。

观察和一些笔记

  • KISS (保持简单，姐妹！)：不必过度设计。那么问题来了，何时需要，何时不需要。
  • 我总是尽可能使用早期返回。它确实使代码逻辑整洁干净。
  • JVM 垃圾收集器是 Java 平台的一项伟大功能。但请不要认为它是防止内存泄漏的万灵药。尽管 B-Tree 实现中没有需要担心的资源连接，但如果我们不仔细处理节点分裂和删除，它仍然可能比实际需要消耗更多的内存。对于具有大量最小度数和数百万个键的 B-Tree，如果我们不正确地丢弃节点，许多节点最终将不会被释放给 JVM GC 进行回收。
  • 可以使用链表替换节点结构中的数组。这可以使代码更紧凑（无需处理数组索引）并且内存使用更有效（内存空间仅在需要时创建）。但是，搜索（以及整体性能）会变慢。
  • 对于使用数组实现的节点，如果用二分查找等更好的搜索技术替换键节点数组中的线性搜索，可以提高整体性能，特别是对于具有大最小度数的 B-Tree。
  • 一个项目的成功，除了知识，正确的設計和完整的测试，利用/创造正确的工具也很重要。

相关的未来工作（如果时间允许）

  • 如果您查看源代码，您会发现某些方法中的某些逻辑部分非常相似。这些是代码重构的良好候选。
  • 如上所述，实现 Java 标准迭代器接口比回调迭代器接口要好。
  • 使用 B-Tree 实现的简单文件系统
  • 分布式 B-Tree 如何？除了 B-Tree 中键的升序排列方式，它还可以很好地适合一致性哈希技术。

最后的想法

我希望此时您已经掌握了 B-Tree 的全部细节以及如何实现它。如果您没有，至少您已经掌握了它的通用概念和思想。一旦您消化了它们，细节就可以稍后跟进。

我知道处理像 B-Tree 这样的数据结构可能会枯燥乏味。但我猜美在于观者的眼中。个人而言，B-Tree 自我还在上大学的时候，就因其概念和实现而成为一个有趣且具有挑战性的数据结构。直到最近，我需要为我目前的项目找到一个更好的数据搜索和组织解决方案时，B-Tree 才进入我的视野。只有在我们彻底理解了其所有重要术语和概念之后，才能成功地实现它。我们必须预料到实现细节可能会让人不知所措。因此，我们应该准备一个不错的调试器、创意的测试用例以及某种可视化工具，以使我们的故障排除更容易。但是，嘿，如果我能做到，我敢肯定你也能做到。下次再见，编码愉快！

参考文献

[1] 算法导论，第三版
第 19 章：B-Tree
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap19.htm

[2] B-Tree 维基百科
https://en.wikipedia.org/wiki/B-tree

[3] B-Trees
http://www.di.ufpb.br/lucidio/Btrees.pdf

[4] B-Tree 中的删除
http://scanftree.com/Data_Structure/deletion-in-b-tree

[5] B-Tree 的笔记
http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T15.BTrees.pdf

[6] JGraphX 3.6.0.0 release
https://github.com/jgraph/jgraphx

历史

首次发布于 2016 年 11 月 30 日

2016 年 11 月 30 日修复了一些小的拼写错误和错误的标签

2016 年 12 月 1 日增加了最小度数与树高度的关系，并修复了一些小的拼写错误

© . All rights reserved.