主题
Search

B 树


B-树由 Bayer (1972) 和 McCreight 引入。它们是一种特殊的 m 阶平衡树,因其结构允许记录的插入、删除和检索,并保证最坏情况下的性能,而被广泛应用于数据库中。一个有 n 个节点的 B-树的高度为 O(lgn),其中 lg 是以 2 为底的 对数。Apple® Macintosh® (Apple, Inc., Cupertino, CA) HFS 文件系统使用 B-树来存储磁盘目录 (Benedict 1995)。一个 B-树满足以下属性:

1. 节点要么是一个叶节点,要么至少有两个子节点

2. 每个节点(除了节点和叶节点)拥有介于 [m/2]m 之间的子节点,其中 [x]向上取整函数

3. 从节点到叶节点的每条路径长度相同。

每个 2-3 都是一个 3 阶 B-树。具有 B-树的 3 阶,叶节点数为 n=1, 2, ... 的 B 树的数量分别是 1, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43, 63, ... (Ruskey, OEIS A014535)。叶节点数为 n=1, 2, ... 的 4 阶 B-树的数量分别是 1, 1, 1, 2, 2, 4, 5, 9, 15, 28, 45, ... (OEIS A037026)。


参见

红黑树,

使用 探索

参考文献

Aho, A. V.; Hopcroft, J. E.; 和 Ullmann, J. D. 数据结构与算法。 Reading, MA: Addison-Wesley, pp. 369-374, 1987.Bayer, R. 和 McCreight, E. "大型有序索引的组织与维护。" Acta Informatica 1, 173-189, 1972.Benedict, B. Macintosh 版 Norton Utilities 使用指南。 Indianapolis, IN: Que, pp. B-17-B-33, 1995.Beyer, R. "对称二叉 B-树:数据结构与维护算法。" Acta Informat. 1, 290-306, 1972.Knuth, D. E. "B 树。" 计算机程序设计艺术,第 3 卷:排序与查找,第 2 版。 Reading, MA: Addison-Wesley, pp. 482-485 和 490-491, 1998.Ruskey, F. "关于 B 树的信息。" http://www.theory.csc.uvic.ca/~cos/inf/tree/BTrees.html.Skiena, S. S. 算法设计手册。 New York: Springer-Verlag, p. 178, 1997.Sloane, N. J. A. 序列 A014535A037026 在 "整数序列在线百科全书" 中。

在 中引用

B 树

请引用本文献为

Weisstein, Eric W. "B 树。" 来自 Web 资源。 https://mathworld.net.cn/B-Tree.html

主题分类