B树比AVL还是RedBlack-Tree快？
我知道性能从来就不是黑白的，通常情况下X的执行速度更快，情况Y的执行速度更慢，但总的来说 – B树快于AVL或RedBlack-Trees？ 他们实现AVL树（甚至可能是RedBlack-tree？）要复杂得多，但它们是否更快 （复杂性是否得到了回报）呢？
编辑：我还要补充说，如果他们更快，那么等效的AVL / RedBlack树（节点/内容） – 为什么他们更快？
肖恩的post（目前接受的）包含了几个不正确的说法。 对不起，肖恩，我不是故意的; 我希望我能说服你，我的发言是基于事实的。
他们的用例完全不同，所以不可能做出比较。
它们都用于维护一套快速查找，插入和删除的完全有序的项目。 他们有相同的界面和相同的意图。
RB树通常是用于为数据提供快速访问（理想情况下为O（logN））的内存中结构。 […]
总是 O（log n）
B树通常是基于磁盘的结构，因此本质上比内存数据要慢。
废话。 将search树存储在磁盘上时，通常使用B树。 这是真的。 将数据存储在磁盘上时，访问速度比内存中的数据慢。 但是存储在磁盘上的红黑树也比存储在内存中的红黑树慢。
你在这里比较苹果和橘子。 有趣的是内存B树和内存中的红黑树的比较。
[旁白：B型树，而不是红黑树，在I / O模型中理论上是有效的。 我已经通过实验testing（并validation了）用于sorting的I / O模型; 我希望它也能用于B树。]
B树很less是二叉树，一个节点可以拥有的孩子的数量通常是很大的。
清楚的是，B树节点的大小范围是树的参数（在C ++中，您可能希望使用整数值作为模板参数）。
数据变化时，B树结构的pipe理可能相当复杂。
我记得他们比红黑树更容易理解和实施。
B树尽量减less磁盘访问次数，以便数据检索是合理的确定性的。
这是真的。
在一个数据库中查看一些数据需要4 B树访问是很常见的。
有数据？
在大多数情况下，我会说内存中的RB树更快。
有数据？
因为查找是二元的，所以很容易find一些东西。 B树可以在每个节点上有多个子节点，因此在每个节点上都必须扫描节点以查找适当的子节点。 这是一个O（N）操作。
每个节点的大小是一个固定的参数，所以即使你做线性扫描，它是O（1）。 如果我们超过每个节点的大小，请注意，您通常将数组保存为O（log n）。
在一棵RB树上，它会是O（logN），因为你正在做一个比较然后分支。
你正在比较苹果和橘子。 O（log n）是因为树的高度最多是O（log n），就像B树一样。
另外，除非你用红黑树玩弄讨厌的分配技巧，否则猜测B树具有更好的caching行为似乎是合理的（它访问一个数组，而不是遍布整个地方的指针，并且分配开销更less，增加了内存甚至更多），这可能会在速度竞赛中帮助它。
我可以指出，实validation据表明，B树（具体尺寸参数为32和64）与小尺寸的红黑树竞争非常激烈，甚至比中等大的n值更胜一筹。 见http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
B树更快。 为什么？ 我猜想这是由于记忆的局部性，更好的caching行为和更less的指针追逐（即使不是相同的事物，在某种程度上是重叠的）。
实际上维基百科有一篇很棒的文章，显示每个RB树可以很容易地表示为一棵B树。 以下面的树为例：
现在只要把它转换成B-Tree（为了使这更明显，节点仍然是彩色的R / B，你通常没有在B-Tree中）：
与B-Tree相同的树
（不能在这里添加一些奇怪的原因）
其他任何RB-Tree也是如此。 这是从这篇文章：
http://en.wikipedia.org/wiki/Red-black_tree
引用这篇文章：
红黑树在结构上等价于阶数为4的B树，最小填充因子为每个簇的值的33％，最大容量为3个值。
我发现没有数据显示其中一个比另一个好得多。 如果是这样的话，我想其中一人已经死了。 他们不同的是他们必须在内存中存储多less数据，以及从树中添加/删除节点有多复杂。
更新：
我个人的testing表明，B树在search数据时更好，因为它们具有更好的数据局部性，因此CPUcaching可以比较快一些。 B-Tree的顺序越高（顺序是一个音符可以有的孩子的数量），查找得到的速度就越快。 另一方面，他们在添加和删除新条目时performance更差，订单越高。 这是由于在节点内添加一个值具有线性复杂性的事实造成的。 由于每个节点都是一个有序的数组，当向中间添加元素时，必须在该数组中移动大量元素：新元素左侧的所有元素必须移动到左侧的一个位置或右侧的所有元素新元素必须向右移动一个位置。 如果一个值在插入过程中向上移动一个节点（在B-Tree中频繁发生），则会留下一个空洞，该空洞也必须通过将所有元素从左边的一个位置移动到右边或者将所有元素移动到正确的一个位置在左边。 这些操作（在C中通常由memmove执行）实际上是O（n）。 所以B树的顺序越高，查找速度越快，但修改速度越慢。 另一方面，如果您select的顺序太低（例如3），则B-Tree在实践中与其他树结构相比几乎没有优点或缺点（在这种情况下，您还可以使用其他方法）。 因此，我总是创build高阶B树（至less4,8以上）。
通常基于B-Tree的文件系统使用更高的顺序（200阶甚至更多） – 这是因为他们通常select足够高的顺序，使得一个音符（当包含最大数目的允许元素时）等于硬盘驱动器上的扇区或文件系统集群的大小。 这样可以获得最佳性能（因为一次只能写入一个完整的扇区，即使只改变一个字节，整个扇区也会被重写）和最佳的空间利用率（因为每个数据input至less等于一个集群或者是集群大小的倍数，不pipe数据有多大）。 由于硬件将数据视为扇区，文件系统组将扇区视为集群，因此B树可以比文件系统的任何其他树结构都能提供更好的性能和空间利用率; 这就是为什么他们如此受欢迎的文件系统。
当您的应用程序不断更新树，添加或删除值时，与高阶B树相比，RB树或AVL树平均可以显示更好的性能。 对查找来说更糟糕的是，它们可能也需要更多的内存，但是因此修改通常很快。 实际上RB-Trees的修改速度比AVL-Tree更快，因此AVL-Tree的查找速度通常比较慢。
像往常一样，这取决于你的应用程序在做什么。 我的build议是：
- 很多查找，很less修改：B-Tree（高阶）
- 很多的查找，大量的修改：AVL树
- 小查找，大量修改：RB-Tree
所有这些树的替代品是AA树 。 正如本PDF文件所示 ，AA树（实际上是RB树的一个子集）在性能上几乎与普通的RB树相同，但是它们比RB树，AVL树，或B-树。 这是一个完整的实现 ，看看它是多么的微小 （主要function不是实现的一部分，实现的一半实际上是评论）。
正如PDF文件显示的那样， Treap也是经典树实现的一个有趣的select。 Treap也是一个二叉树，但是并不试图强制平衡。 为了避免在不平衡的二叉树中引起最坏的情况（导致查找变成O（n）而不是O（log n）），Treap会为树添加一些随机性。 随机性不能保证树的平衡性，但也使得树极不平衡。
没有什么能阻止仅在内存中工作的B-Tree实现。 事实上，如果关键比较便宜，内存中的B-Tree可以更快，因为它在一个节点中的多个密钥的打包在search期间将导致较less的高速caching未命中。 请参阅此链接进行性能比较。 一句话：“速度testing结果很有意思，显示B +树对于包含超过16,000个项目的树来说要快得多。” （B +树只是B树上的变体）。
问题是古老的，但我认为它仍然是相关的。 乔纳斯·科尔克（JonasKölker）和麦基（Mecki）给出了很好的答案，但我不认为答案涵盖了整个故事。 我甚至会争辩说整个讨论都没有提到:-)。
当条目相对较小时（整数，小string/字，浮游物等），关于B树的说法是正确的。 当条目很大（超过100B）时，差异变小/不显着。
让我总结一下B树的要点：
-
由于内存局部性（导致caching和TLB未命中），它们比任何二进制search树（BST）都快。
-
如果条目相对较小或者条目大小不一，则B-树通常更节省空间。 可用空间pipe理更容易（您分配更大的内存块），每项的额外元数据开销更低。 B树会浪费一些空间，因为节点并不总是满的，但是它们最终会变得比二叉search树更紧凑。
-
大O性能（O（logN））对于两者都是相同的。 而且，如果你在每个B-Tree节点内进行二分search，你甚至会得到与BST相同数量的比较（这是一个很好的math练习来validation这一点）。 如果B-Tree节点大小是合理的（1-4倍caching行大小），则由于硬件预取，每个节点内部的线性search仍然更快。 您还可以使用SIMD指令来比较基本数据types（例如整数）。
-
B-Tree更适合压缩：每个节点有更多的数据要压缩。 在某些情况下，这可能是一个巨大的好处。 只要想一想用于构build索引的关系数据库表中的自动递增键。 B-Tree的前导节点包含非常非常好的连续整数。
-
B-Trees存储在辅助存储（当你需要阻塞IO时）显然要快得多。
在纸面上，B-树有很多优点，几乎没有缺点。 那么应该使用B-Tree来获得最佳性能吗？
答案通常是否定的 – 如果树适合内存。 在性能至关重要的情况下，您需要一个线程安全的树形数据结构（简单地说，多个线程可以完成比单个更多的工作）。 使B-Tree支持并发访问比构buildBST更麻烦。 使树支持并发访问最直接的方法是在遍历/修改节点时locking节点。 在B树中，每个节点locking更多的条目，从而产生更多的序列化点和更多的竞争锁。
所有的树版本（AVL，红/黑，B树和其他）都有无数的变体，它们在支持并发方面有所不同。 在大学课程中教授的或从一些入门书籍中读取的香草algorithm在实践中几乎从不使用。 所以，很难说哪棵树performance最好，因为在每棵树背后都没有正式的协议。 我会build议考虑所提到的树更像数据结构类服从某些树状不variables，而不是精确的数据结构。
以B-Tree为例。 香草B-Tree在实践中几乎从未被使用过 – 你不能把它做得很好！ 使用的最常见的B-Tree变体是B + -Tree（广泛用于文件系统，数据库）。 B + -Tree和B-Tree之间的主要区别在于：1）不要在树的内部节点中存储条目（因此当修改存储在内部节点中的条目时，不需要在树中写入高锁） ; 2）在同一级别的节点之间有链接（因此在进行范围search时，不必locking节点的父节点）。
我希望这有帮助。
Google的专家最近发布了基于B树的STL容器的实现。 他们声称，与通过红黑树实现的标准STL容器相比，它们的版本更快，消耗的内存更less。 更多细节在这里
对于某些应用，B树比BST快得多。 你可能在这里find的树木：
http://freshmeat.net/projects/bps
相当快 与普通的BST实现相比，它们使用的内存更less，因为它们不需要每个节点都有2或3个指针的BST基础结构，还有一些额外的字段来保持平衡信息。
在不同的情况下会使用B树 – 当树节点需要存储在一起时使用B树 – 通常是因为存储是一个磁盘页面，所以重新平衡可能非常昂贵。 当你没有这个约束时，使用RB树。 所以如果你想实现（比如说）一个关系数据库索引，B树可能会更快，而RB树可能会更快（例如）在内存中search。
它们都具有相同的渐近行为，所以性能更依赖于实现，而不是使用哪种types的树。 树结构的一些组合实际上可能是最快的方法，其中B树的每个节点恰好适合于caching行，并且使用某种二叉树在每个节点内进行search。 自己pipe理节点的内存也可能使您获得更大的caching局部性，但价格非常高。
就个人而言，我只是使用标准库中的任何一种语言来使用我正在使用的语言，因为对于很小的性能增益（如果有的话），这是很多的工作。
从理论上说，RB树实际上与B树非常相似，因为它们模拟2-3-4树的行为。 AA树是一个类似的结构，它可以模拟2-3棵树。
此外，红黑树的高度是O（log [2] N），而B树的高度是O（log [q] N），其中ceiling [N] <= q <= N。 因此，如果我们考虑在B树的每个关键数组（如上所述那样固定）中的比较，则B树的时间复杂度<=红黑树的时间复杂度。 （对于单个logging等于块大小的大小相等的情况）
