何时selectRB树，B-Tree或AVL树？
作为程序员，我应该什么时候考虑使用RB树，B-树或AVL树？ 在决定select之前，需要考虑哪些关键点？
有人可以解释一下每个树形结构的场景，为什么它是参照关键点select的？
拿一点盐，
B树，当你pipe理数以千计的项目，你从磁盘或一些缓慢的存储介质分页。
RB树，当你在树上相当频繁的插入，删除和检索。
AVL树在插入和删除相对于您的检索不经常。
我认为即使在主存中，B +树也是一个很好的通用有序容器数据结构。 即使在虚拟内存不是问题时，caching友好性通常也是如此，B +树对于顺序访问特别有利 – 与链表相似的渐近性能，但具有接近简单数组的caching友好性。 所有这些和O（log n）search，插入和删除。
然而，B +树确实有问题，例如在插入/删除节点时在节点内移动的项目，使指向这些项目的指针无效。 我有一个“游标维护”的容器库 – 游标将自己附加到它们当前在链接列表中引用的叶节点，所以它们可以自动修复或失效。 由于很less有超过一两个游标，所以它可以很好地工作，但是这也是一个额外的工作。
另一件事是B +树本质上就是这样。 我想你可以剥离或重新创build非叶节点，这取决于你是否需要它们，但是使用二叉树节点，你会获得更多的灵活性。 一个二叉树可以被转换成一个链表并返回而不需要复制节点 – 你只需要改变指针，然后记住你现在将它视为一个不同的数据结构。 除此之外，这意味着你可以非常容易地将树合并，将两棵树都转换成列表，然后将它们合并，然后再转换成树。
另一件事是内存分配和释放。 在二叉树中，这可以从algorithm中分离出来 – 用户可以创build一个节点，然后调用插入algorithm，删除可以提取节点（从树中分离它们，但不释放内存）。 在B树或B +树中，这显然不起作用 – 数据将存在于多项目节点中。 编写插入方法，在不修改节点的情况下“计划”操作，直到他们知道需要多less新节点并且可以分配为止是一个挑战。
红黑vs AVL？ 我不确定这有什么重大的不同。 我自己的库有一个基于策略的“工具”类来操作节点，包括双链表，简单的二叉树，splay树，红黑树和treaps（包括各种转换）的方法。 其中一些方法只是实施，因为我在这个或那个时候感到无聊。 我不确定我是否testing过这种方法。 我之所以select红黑树而不是AVL，是因为我个人更了解这些algorithm – 这并不意味着它们更简单，只是我对它们更熟悉的历史侥幸。
最后一件事 – 我只是最初开发我的B +树容器作为一个实验。 这是那些永远不会结束的实验之一，但我不鼓励别人重复。 如果你所需要的只是一个有序的容器，最好的答案就是使用你现有的库提供的那个 – 例如C ++中的std :: map等。 我的图书馆进化了多年，花了相当长的一段时间才得到它的稳定，而且我刚刚发现它在技术上是不可移植的（取决于一些未定义的行为WRT抵消）。
在内存中，B-Tree在项数超过32000时具有优势…请参阅stx-btree中的 speedtest.pdf 。
当select数据结构时，你正在交换诸如
- 检索速度与更新速度
- 结构如何处理最坏情况的操作，例如插入以sorting顺序到达的logging
- 空间浪费了
我将首先阅读Robert Harvey引用的维基百科文章。
实际上，在使用像Java这样的语言时，一般的程序员倾向于使用提供的集合类。 如果在性能调优活动中发现收集性能有问题，那么可以寻求替代实现。 很less有企业主导的发展需要考虑的第一件事。 手工实现这样的数据结构是非常罕见的，通常有一些库可以使用。
