B树

维基百科，自由的百科全书

B樹是一種樹資料結構，常見於資料庫與檔案系統之中。B樹能夠使資料保持有序，並擁有均勻的對數處理時間的插入和刪除動作。B樹的元素通常會自底向上插入，有別於多數自頂向下插入的二元樹。

B 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

B 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树(常简称为2-3 树)中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。

B 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有在叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音(Boeing)，因为他曾经工作于波音科学研究实验室。

目录 1 节点结构 2 算法 2.1 查找 2.2 插入 2.3 删除 3 注解 4 参见 5 引用 6 外部连接

[编辑] 节点结构

在 B 树中的节点通常被表示为一组有序的元素和子指针。除了根之外的每个节点都包含最少 L 个元素最多 U 个元素，对于任意的 L 和 U 有最多 U+1 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。

每个内部节点的元素充当分开它的子树的分离值。例如，如果内部节点有三个子节点(或子树)则它必须有两个分离值或元素 a₁ 和 a₂。在最左子树中所有的值都小于 a₁，在中间子树中所有的值都在 a₁ 和 a₂ 之间，而在最右子树中所有的值都大于 a₂。

[编辑] 算法

[编辑] 查找

查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用两分查找来确定这个位置。

[编辑] 插入

节点要处于违规状态，它必须包含在可接受范围之外数目的元素。

1. 首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
2. 如果没有节点处于违规状态则处理结束。
3. 如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则建立一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不大于最大数的一半。

[编辑] 删除

1. 首先，查找要删除的值。接着从包含它的节点中删除这个值。
2. 如果没有节点处于违规状态则处理结束。
3. 如果节点处于违规状态则有两种可能情况:
   1. 它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
   2. 它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

[编辑] 注解

假定 L 是节点允许拥有子节点的最小数目，而 U 是最大数目。则每个节点总是有在 L 和 U 之间(包含它们在内)个子节点，除了一个例外: 根节点有从2到U(包含它们在内)个子节点。换句话说，根节点豁免于低边界限制，而拥有它自己的低边界2。这允许树持有小数目的元素。根有一个子节点没有意义，因为附着在这个子节点上的子树可以简单的附着在根节点上。允许根节点没有子节点也是不需要的，因为没有元素的树典型的表示为没有根节点。

Robert Tarjan 证明了均摊的分裂/合并数目是 2。

[编辑] 参见

• B+ tree
• B*-tree
• 二叉樹
• dancing tree
• skip list

[编辑] 引用

最初的论文:

• Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971年, San Diego, California, Session 5B, p. 219-235.
• Rudolf Bayer and McCreight, E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1, 173-189, 1972年.

总结:

• Donald E. Knuth, "The Art of Computer Programming", second edition, volume 3, section 6.2.4, 1997年.
• Douglas Comer, The Ubiquitous B-Tree,ACM Computing Surveys 11(2): 121-137 (1979).

[编辑] 外部连接

• Animation of a 2-3-4 Tree (the simplest form of B-Tree)
• http://www.bluerwhite.org/btree
• B-Tree animation (Java Applet)
• NIST's Dictionary of Algorithms and Data Structures: B-tree
• B-tree algorithms
• B-tree variations
• Source code for a balanced tree (B-tree) (Windows required for test timings)
• B trees by Thomas Niemann
• B 树的注释实现
• (a,b) 树的注释实现