我知道性能永远不会是黑白的,通常一个实现在X情况下更快,在Y情况下更慢等等,但一般来说 - B树比AVL或RedBlack-Trees快吗？它们比AVL树(甚至可能是RedBlack-trees？)要复杂得多,但它们更快(它们的复杂性是否得到回报)？
编辑:我还想补充一点,如果它们比等效的AVL/RedBlack树更快(就节点/内容而言) - 为什么它们更快？
肖恩的帖子(目前接受的帖子)包含几个不正确的声明.对不起肖恩,我不是故意粗鲁; 我希望我能说服你,我的陈述是基于事实.
它们的使用情况完全不同,因此不可能进行比较.
它们都用于维护一组完全有序的项目,具有快速查找,插入和删除功能.它们具有相同的界面和相同的意图.
RB树通常是内存中结构,用于为数据提供快速访问(理想情况下为O(logN)).[...]
总是 O(log n)
B树通常是基于磁盘的结构,因此本质上比内存数据慢.
废话.在磁盘上存储搜索树时,通常使用B树.那是真的.将数据存储在磁盘上时,访问速度比内存中的数据慢.但是存储在磁盘上的红黑树也比存储在内存中的红黑树慢.
你在这里比较苹果和橘子.真正有趣的是内存中的B树和内存中的红黑树的比较.
[旁白:与红黑树相比,B树在理论上在I/O模型中是有效的.我已经通过实验测试(并验证了)I/O模型进行排序; 我希望它也适用于B树.]
B树很少是二叉树,节点可以拥有的子节点数通常很大.
需要说明的是,B树节点的大小范围是树的参数(在C++中,您可能希望使用整数值作为模板参数).
当数据改变时,B树结构的管理可能非常复杂.
我记得他们比红黑树更容易理解(和实施).
B-tree尝试最小化磁盘访问次数,以便数据检索具有合理的确定性.
那是真的.
在非常数据库中查找一些数据所需的4 B树访问权限并不罕见.
得到数据？
在大多数情况下,我会说内存中的RB树更快.
得到数据？
因为查找是二进制的,所以很容易找到一些东西.B树可以在每个节点上有多个子节点,因此在每个节点上,您必须扫描节点以查找适当的子节点.这是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树更快.为什么？我猜想这是由于内存局部性,更好的缓存行为和更少的指针追逐(如果不是相同的东西,在某种程度上重叠).
实际上,维基百科有一篇很棒的文章,显示每个RB树都可以很容易地表达为B树.以下面的树为例:
现在只需将其转换为B树(为了使这更明显,节点仍然是彩色R/B,你通常在B树中没有):
与B树相同的树
(由于一些奇怪的原因,不能在这里添加图像)
任何其他RB树也是如此.它来自这篇文章:
http://en.wikipedia.org/wiki/Red-black_tree
引用本文:
然后,红黑树在结构上等同于4阶B树,每个聚类的最小填充因子为33%,最大容量为3.
我发现没有数据表明其中一个明显优于另一个.如果是这样的话,我想其中一个已经消失了.它们在内存中必须存储多少数据以及从树中添加/删除节点的复杂程度各不相同.
我的个人测试表明,B-Trees在搜索数据时更好,因为它们具有更好的数据局部性,因此CPU缓存可以更快地进行比较.B树的顺序越高(顺序是注释可以拥有的子数),查找得到的速度就越快.另一方面,他们的订单越高,添加和删除新条目的表现就越差.这是因为在节点内添加值具有线性复杂性.由于每个节点都是一个有序数组,因此在向中间添加元素时,必须在该数组中移动大量元素:新元素左侧的所有元素必须向左移动一个位置或向右移动所有元素新元素必须向右移动一个位置.如果一个值在插入过程中向上移动一个节点(在B树中频繁发生),则会留下一个洞,必须通过将所有元素从左侧的一个位置向右移动或者将所有元素移动到左边的右边一个位置.这些操作(在C中通常由memmove执行)实际上是O(n).因此,B树的顺序越高,查找越快但修改越慢.另一方面,如果您选择的订单太低(例如3),B-Tree在实践中显示出优于其他树结构的优点或缺点(在这种情况下,您也可以使用其他结构).因此,我总是创建高订单的B树(至少4,8和更好).
文件系统通常基于B树,使用更高的订单(订单200甚至更多) - 这是因为它们通常选择足够高的订单,以便注释(当包含允许的元素的最大数量时)等于硬盘驱动器或文件系统集群上扇区的大小.这给了最佳性能(因为HD只能在同一时间写一个完整的部门,即使只是一个字节被改变,全部门无论如何重写)和最佳的空间利用率(如在驱动器的每个数据录入等于至少大小一个集群或者是集群大小的倍数,无论数据有多大).由于硬件将数据视为扇区而文件系统将扇区分组到群集,因此B-Trees可以为文件系统提供比任何其他树结构更好的性能和空间利用率.这就是为什么它们如此受文件系统欢迎的原因.
当您的应用程序不断更新树,添加或删除树时,与具有高阶的B树相比,RB-Tree或AVL-Tree可能表现出更好的性能.查找更糟糕,它们可能还需要更多内存,但因此修改通常很快.实际上RB-Trees甚至比AVL-Trees更快地进行修改,因此AVL-Tree对于查找来说要快一点,因为它们通常不那么深.
像往常一样,它很大程度上取决于你的应用程序在做什么.我的建议是:
大量查找,少许修改:B-Tree(高阶)
大量的查找,大量的修改:AVL-Tree
小查找,大量修改:RB-Tree
所有这些树的替代品是AA树.正如本文所述,AA-Trees(实际上是RB-Trees的一个子组)在性能上与普通RB-Tree几乎相同,但它们比RB-Tree,AVL-Trees更容易实现,或B树.这是一个完整的实现,看它有多么微小(主函数不是实现的一部分,一半的实现行实际上是注释).
正如PDF文件所示,Treap也是经典树实现的有趣替代品.Treap也是一个二叉树,但不会尝试强制平衡.为了避免您可能遇到不平衡二叉树的最坏情况(导致查找变为O(n)而不是O(log n)),Treap会为树添加一些随机性.随机性不能保证树的平衡性很好,但它也使树不太可能非常不平衡.
没有什么能阻止只在内存中工作的B-Tree实现.实际上,如果密钥比较便宜,内存中的B-Tree可以更快,因为在一个节点中打包多个密钥会在搜索期间导致更少的缓存未命中.请参阅此链接以进行性能比较.引用:"速度测试结果很有趣,并且显示B +树对于包含超过16,000个项目的树木要快得多." (B + Tree只是B-Tree的变种).
这个问题已经过时了,但我认为它仍然具有现实意义.JonasKölker和Mecki给出了非常好的答案,但我不认为答案涵盖整个故事.我甚至认为整个讨论都忽略了这一点:-).
当条目相对较小(整数,小字符串/单词,浮点数等)时,关于B-Trees的说法是正确的.当条目很大(超过100B)时,差异变得更小/不显着.
让我总结关于B树的要点:
由于内存局部性(导致较少的缓存和TLB未命中),它们比任何二进制搜索树(BST)更快.
如果条目相对较小或条目大小可变,则B树通常更节省空间.可用空间管理更容易(您分配更大的内存块),每个条目的额外元数据开销更低.B-Trees将浪费一些空间,因为节点并不总是满的,但是,它们最终仍然比二进制搜索树更紧凑.
两者的大O性能(O(logN))是相同的.此外,如果你在每个B树节点内进行二进制搜索,你甚至会得到与BST相同数量的比较(这是一个很好的数学运算来验证这一点).如果B树节点大小合理(1-4倍高速缓存行大小),则由于硬件预取,每个节点内的线性搜索仍然更快.您还可以使用SIMD指令比较基本数据类型(例如整数).
B-Tree更适合压缩:每个节点有更多数据要压缩.在某些情况下,这可能是一个巨大的好处.只需考虑用于构建索引的关系数据库表中的自动递增键.B树的主节点包含非常非常好地压缩的连续整数.
当存储在二级存储(您需要执行块IO)时,B树显然要快得多.
在纸面上,B树有许多优点,几乎没有缺点.那么应该只使用B树来获得最佳性能吗？
答案通常是否定的 - 如果树适合记忆.在性能至关重要的情况下,您需要一个线程安全的树状数据结构(简单地说,几个线程可以完成比单个线程更多的工作).使B-Tree支持并发访问比制作BST更成问题.使树支持并发访问的最直接方法是在遍历/修改节点时锁定节点.在B树中,每个节点锁定更多条目,从而产生更多序列化点和更多竞争锁.
所有树版本(AVL,Red/Black,B-Tree,其他版本)都有无数的变体,它们在支持并发性方面有所不同.在大学课程中教授或从一些入门书籍中阅读的香草算法几乎从未在实践中使用过.因此,很难说哪棵树表现最好,因为没有关于每棵树背后的确切算法的正式协议.我建议将所提到的树更像是数据结构类,它们遵循某些树状不变量而不是精确的数据结构.
以B树为例.香草B树几乎从未在实践中使用 - 你无法使其成型!最常用的B-Tree变体是B + -Tree(广泛用于文件系统,数据库).B + -Tree和B-Tree之间的主要区别:1)您不在树的内部节点中存储条目(因此在修改存储在内部节点中的条目时,您不需要在树中写高锁) ; 2)您在同一级别的节点之间有链接(因此您在进行范围搜索时不必锁定节点的父节点).
我希望这有帮助.
Google最近发布了他们的STL容器实现,这些容器基于B树.他们声称,与通过红黑树实现的标准STL容器相比,他们的版本更快,占用的内存更少.更多细节在这里
京公网安备 11010802040832号 | 京ICP备19059560号-6 