我知道性能永远不是黑白的，通常一种实现在 X 情况下更快，在 Y 情况下更慢，等等，但总的来说 - B-trees 是否比 AVL 或 RedBlack-Trees 更快？它们的实现比 AVL 树（甚至可能是红黑树？）要复杂得多，但是它们更快吗（它们的复杂性是否得到回报）？
编辑：我还想补充一点，如果它们比等效的 AVL/RedBlack 树（就节点/内容而言）更快 -为什么它们更快？
fredrikholmstrom
问问题
36506 次
9 回答
135
肖恩的帖子（目前被接受的）包含几个不正确的声明。对不起，肖恩，我不是故意粗鲁的。我希望我能说服你，我的陈述是有根据的。
它们的用例完全不同，因此无法进行比较。
它们都用于维护一组具有快速查找、插入和删除功能的完全有序的项目。它们具有相同的界面和相同的意图。
RB 树通常是用于提供对数据的快速访问（理想情况下为 O(logN)）的内存结构。[...]
总是O(log n)
B 树通常是基于磁盘的结构，因此本质上比内存数据慢。
废话。在磁盘上存储搜索树时，通常使用 B 树。这是真的。当您将数据存储在磁盘上时，访问速度比访问内存中的数据要慢。但是存储在磁盘上的红黑树也比存储在内存中的红黑树慢。
你在这里比较苹果和橘子。真正有趣的是内存 B 树和内存红黑树的比较。
[顺便说一句：与红黑树相反，B 树在 I/O 模型中理论上是有效的。我已经通过实验测试（并验证了）用于排序的 I/O 模型；我希望它也适用于 B 树。]
B树很少是二叉树，一个节点可以拥有的孩子的数量通常很大。
需要明确的是，B-tree 节点的大小范围是树的一个参数（在 C++ 中，您可能希望使用整数值作为模板参数）。
当数据发生变化时，B-tree 结构的管理会相当复杂。
我记得它们比红黑树更容易理解（和实现）。
B-tree 尽量减少磁盘访问的次数，以便数据检索具有合理的确定性。
这是真的。
在非常数据库中查找一些数据所必需的 4 B 树访问这样的情况并不少见。
有数据吗？
在大多数情况下，我会说内存中的 RB 树更快。
有数据吗？
因为查找是二进制的，所以很容易找到一些东西。B-tree 每个节点可以有多个子节点，因此您必须在每个节点上扫描节点以查找合适的子节点。这是一个 O(N) 操作。
每个节点的大小是一个固定参数，所以即使你进行线性扫描，也是 O(1)。如果我们超过每个节点的大小，请注意您通常保持数组排序，因此它是 O(log n)。
在 RB 树上，它会是 O(logN)，因为你正在做一个比较然后分支。
你在比较苹果和橘子。O(log n) 是因为树的高度最多为 O(log n)，就像 B 树一样。
此外，除非你对红黑树玩讨厌的分配技巧，否则推测 B 树具有更好的缓存行为似乎是合理的（它访问一个数组，而不是散布在各处的指针，并且分配开销更少，增加内存地方性甚至更多），这可能有助于它在速度竞赛中。
我可以指出实验证据表明，B 树（特别是大小参数为 32 和 64）在小尺寸方面与红黑树非常有竞争力，并且在 n 值适中的情况下也优于它。见http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
B树更快。为什么？我推测这是由于内存局部性、更好的缓存行为和更少的指针追逐（如果不是相同的东西，在某种程度上重叠）。
于 2009-03-18T09:57:47.897 回答
105
实际上 Wikipedia 有一篇很棒的文章显示每个 RB-Tree 都可以很容易地表示为 B-Tree。以以下树为例：
现在只需将其转换为 B-Tree（为了使这一点更明显，节点仍为 R/B 色，这是 B-Tree 中通常没有的）：
.svg){kind=link}
（由于某些奇怪的原因无法在此处添加图像）
任何其他 RB-Tree 也是如此。它取自这篇文章：
http://en.wikipedia.org/wiki/Red-black_tree
引用这篇文章：
然后，红黑树在结构上等效于 4 阶 B 树，每个簇的最小填充因子为 33% 的值，最大容量为 3 个值。
我没有发现任何数据表明两者中的一个明显优于另一个。我想如果是这样的话，两者中的一个已经死了。它们在必须在内存中存储多少数据以及从树中添加/删除节点的复杂程度方面有所不同。
更新：
我的个人测试表明，B-Tree 在搜索数据时更好，因为它们具有更好的数据局部性，因此 CPU 缓存可以更快地进行比较。B-Tree 的阶数越高（阶数是一个笔记可以拥有的子节点数），查找的速度就越快。另一方面，它们的添加和删除新条目的性能越差，它们的顺序越高。这是因为在节点内添加值具有线性复杂性。由于每个节点都是一个排序数组，因此在将元素添加到中间时，您必须在该数组内移动大量元素：新元素左侧的所有元素必须向左移动一个位置，或者将所有元素向右移动一个位置新元素必须向右移动一位。如果一个值在插入过程中向上移动一个节点（这在 B 树中经常发生），它会留下一个空洞，也必须通过将所有元素从左侧移动一个位置或将所有元素移动到右侧来填充该空洞。右边一个位置到左边。这些操作（在 C 中通常由 memmove 执行）实际上是 O(n)。所以B-Tree的阶数越高，查找越快但修改越慢。另一方面，如果您选择的顺序太低（例如 3），B-Tree 在实践中与其他树结构相比几乎没有优势或劣势（在这种情况下，您也可以使用其他东西）。因此，我总是会创建具有高阶的 B 树（至少 4、8 及以上就可以了）。它会留下一个空洞，也必须通过将所有元素从左侧移动一个位置或将所有元素向右移动一个位置来填充该空洞。这些操作（在 C 中通常由 memmove 执行）实际上是 O(n)。所以B-Tree的阶数越高，查找越快但修改越慢。另一方面，如果您选择的顺序太低（例如 3），B-Tree 在实践中与其他树结构相比几乎没有优势或劣势（在这种情况下，您也可以使用其他东西）。因此，我总是会创建具有高阶的 B 树（至少 4、8 及以上就可以了）。它会留下一个空洞，也必须通过将所有元素从左侧移动一个位置或将所有元素向右移动一个位置来填充该空洞。这些操作（在 C 中通常由 memmove 执行）实际上是 O(n)。所以B-Tree的阶数越高，查找越快但修改越慢。另一方面，如果您选择的顺序太低（例如 3），B-Tree 在实践中与其他树结构相比几乎没有优势或劣势（在这种情况下，您也可以使用其他东西）。因此，我总是会创建具有高阶的 B 树（至少 4、8 及以上就可以了）。另一方面，如果您选择的顺序太低（例如 3），B-Tree 在实践中与其他树结构相比几乎没有优势或劣势（在这种情况下，您也可以使用其他东西）。因此，我总是会创建具有高阶的 B 树（至少 4、8 及以上就可以了）。另一方面，如果您选择的顺序太低（例如 3），B-Tree 在实践中与其他树结构相比几乎没有优势或劣势（在这种情况下，您也可以使用其他东西）。因此，我总是会创建具有高阶的 B 树（至少 4、8 及以上就可以了）。
通常基于 B 树的文件系统使用更高的阶数（阶数 200 甚至更多） - 这是因为它们通常选择足够高的阶数，以便注释（当包含最大允许元素数时）等于硬盘驱动器上的扇区或文件系统集群的大小。这提供了最佳性能（因为 HD 一次只能写入一个完整扇区，即使只更改一个字节，整个扇区也会被重写）和最佳空间利用率（因为驱动器上的每个数据条目至少等于一个集群或集群大小的倍数，无论数据实际有多大）。由于硬件将数据视为扇区并且文件系统将扇区分组为簇，B 树可以为文件系统提供比任何其他树结构更好的性能和空间利用率；这就是为什么它们在文件系统中如此受欢迎的原因。
当您的应用程序不断更新树，向其中添加或删除值时，与高阶 B-Tree 相比，RB-Tree 或 AVL-Tree 的平均性能可能会更好。查找更糟，它们可能还需要更多内存，但因此修改通常很快。实际上，RB-Trees 的修改速度甚至比 AVL-Trees 还要快，因此 AVL-Trees 的查找速度要快一些，因为它们通常不那么深。
所以像往常一样，这在很大程度上取决于您的应用程序在做什么。我的建议是：
- 大量查找，少量修改：B-Tree（高阶）
- 大量查找，大量修改：AVL-Tree
- 少量查找，大量修改：RB-Tree
所有这些树的替代品是AA-Trees。正如这篇PDF 论文所暗示的，AA-Trees（实际上是 RB-Trees 的一个子组）在性能上几乎与普通 RB-Trees 相同，但它们比 RB-Trees、AVL-Trees、或 B 树。这是一个完整的实现，看看它有多小（主函数不是实现的一部分，一半的实现行实际上是注释）。
正如 PDF 论文所示，Treap也是经典树实现的有趣替代方案。Treap 也是一棵二叉树，但它不会尝试强制平衡。为了避免在不平衡二叉树中遇到的最坏情况（导致查找变为 O(n) 而不是 O(log n)），Treap 为树添加了一些随机性。随机性不能保证树的平衡良好，但它也使得树极不可能非常不平衡。
于 2009-07-28T16:39:45.167 回答
27
没有什么能阻止只在内存中工作的 B-Tree 实现。事实上，如果键比较便宜，内存 B-Tree 可以更快，因为它在一个节点中打包多个键将减少搜索期间的缓存未命中。有关性能比较，请参阅此链接。引用：“速度测试结果很有趣，显示 B+ 树对于包含超过 16,000 个项目的树要快得多。” （B+Tree 只是 B-Tree 的一种变体）。
于 2009-03-15T10:42:09.803 回答
14
这个问题很老，但我认为它仍然是相关的。Jonas Kölker 和 Mecki 给出了很好的答案，但我不认为答案涵盖了整个故事。我什至会争辩说整个讨论都没有抓住重点:-)。
当条目相对较小（整数、小字符串/单词、浮点数等）时，关于 B 树的说法是正确的。当条目很大（超过 100B）时，差异变得更小/微不足道。
让我总结一下关于 B-Trees 的要点：
由于内存局部性（导致更少的缓存和 TLB 未命中），它们比任何二叉搜索树 (BST) 都快。
如果条目相对较小或条目大小可变，则 B 树通常更节省空间。空闲空间管理更容易（您分配更大的内存块）并且每个条目的额外元数据开销更低。B-Trees 会浪费一些空间，因为节点并不总是满的，但是，它们最终仍然比二叉搜索树更紧凑。
两者的大 O 性能（ O(logN) ）是相同的。此外，如果您在每个 B-Tree 节点内进行二分搜索，您甚至会得到与 BST 中相同数量的比较（这是一个很好的数学练习来验证这一点）。如果 B-Tree 节点大小合理（1-4 倍缓存行大小），由于硬件预取，每个节点内部的线性搜索仍然更快。您还可以使用 SIMD 指令来比较基本数据类型（例如整数）。
B-Trees 更适合压缩：每个节点有更多的数据需要压缩。在某些情况下，这可能是一个巨大的好处。想想关系数据库表中用于构建索引的自动递增键。B-Tree 的前导节点包含压缩得非常非常好的连续整数。
当存储在辅助存储（需要进行块 IO）时，B 树显然要快得多。
在纸面上，B-Trees 有很多优点，几乎没有缺点。那么是否应该只使用 B-Trees 以获得最佳性能？
答案通常是否定的——如果树适合内存。在性能至关重要的情况下，您需要一个线程安全的树状数据结构（简单地说，多个线程可以比单个线程做更多的工作）。让 B-Tree 支持并发访问比让 BST 更成问题。使树支持并发访问的最直接方法是在遍历/修改节点时锁定节点。在 B 树中，每个节点锁定更多条目，导致更多序列化点和更多竞争锁。
所有树版本（AVL、Red/Black、B-Tree 等）都有无数的变体，它们在支持并发方面的方式不同。在大学课程中教授或从一些入门书籍中阅读的普通算法几乎从未在实践中使用过。因此，很难说哪棵树表现最好，因为对于每棵树背后的确切算法没有官方协议。我建议将提到的树更像是遵循某些树状不变量的数据结构类，而不是精确的数据结构。
以 B 树为例。vanilla B-Tree 几乎从未在实践中使用过——你不能让它很好地扩展！最常用的 B-Tree 变体是 B+-Tree（广泛用于文件系统、数据库）。B+-Tree 和 B-Tree 之间的主要区别： 1）您不将条目存储在树的内部节点中（因此当修改存储在内部节点中的条目时，您不需要在树的高处写锁） ; 2）您在同一级别的节点之间有链接（因此在进行范围搜索时您不必锁定节点的父节点）。
我希望这有帮助。
于 2013-02-13T01:02:22.723 回答
8
谷歌的人最近发布了他们基于 B-trees 的 STL 容器的实现。他们声称与通过红黑树实现的标准 STL 容器相比，他们的版本更快并且消耗更少的内存。更多细节在这里
于 2013-02-14T07:53:10.963 回答
2
对于某些应用程序，B 树比 BST 快得多。您可以在这里找到的树木：
http://freshmeat.net/projects/bps
相当快。它们还比常规 BST 实现使用更少的内存，因为它们不需要每个节点 2 或 3 个指针的 BST 基础结构，以及一些额外的字段来保持平衡信息。
于 2011-07-19T14:21:24.480 回答
0
它们在不同的情况下使用 - 当树节点需要一起保存在存储中时使用 B 树 - 通常因为存储是磁盘页面，因此重新平衡可能非常昂贵。当您没有此约束时，将使用 RB 树。因此，如果您想实现（例如）关系数据库索引，B-trees 可能会更快，而 RB 树对于（例如）内存搜索可能会更快。
于 2009-03-15T09:29:37.030 回答
0
它们都具有相同的渐近行为，因此性能更多地取决于实现而不是您使用的树类型。树结构的某种组合实际上可能是最快的方法，其中 B 树的每个节点都完全适合缓存行，并且某种二叉树用于在每个节点内进行搜索。自己管理节点的内存也可能使您能够实现更大的缓存局部性，但代价非常高。
就个人而言，我只是将标准库中的任何内容用于我正在使用的语言，因为它需要做很多工作才能获得非常小的性能提升（如果有的话）。
从理论上讲... RB-trees 实际上与 B-trees 非常相似，因为它们模拟 2-3-4 树的行为。AA-trees 是一种类似的结构，而是模拟 2-3 棵树。
于 2009-06-18T11:58:35.320 回答
0
此外......红黑树的高度是 O(log[2] N) 而 B-tree 的高度是 O(log[q] N) ，其中天花板 [N]<= q <= N 。因此，如果我们考虑在 B 树的每个键数组中进行比较（如上所述固定），那么 B 树的时间复杂度 <= 红黑树的时间复杂度。（相同大小的单个记录的大小等于块大小）
于 2011-07-03T16:06:53.530 回答