二叉搜索树、2-3树和B树的用法、优缺点

Question

我正在复习数据结构课上的材料，我对这三种树的用法有点困惑。那么什么情况下我们最好分别使用二叉搜索树、2-3树和B树呢？有什么优点和缺点？

太感谢了！我对数据结构很陌生......

Answer 1

所有这三个结构都是有序字典的实现 - 它们维护一个集合，同时有效地支持插入、删除、查找、后继和前驱查询。

二叉搜索树和 2-3 树与 B 树的不同之处在于，BST 和 2-3 树（通常）是主存储器数据结构，而 B 树（通常）是外部存储器数据结构。具体来说，B 树被设计为存储在磁盘上，其中读取或写入磁盘页面的成本明显高于执行简单计算的成本。如果您计划存储主存无法容纳的大量数据，那么 B 树是数据结构的绝佳选择。另一方面，在主存中，具有非常大分支因子的B树将比BST或2-3树慢，因为每次B树插入或删除可能需要大量的指针重新分配。对于适合主存的数据集，2-3 树和 BST 通常是更好的选择（尽管有一些研究表明，由于缓存效应，低阶 B 树在主存中的性能可以优于 BST。）

至于 BST 和 2-3 树：“二叉搜索树”不是单一的数据结构。存在没有平衡的纯 BST、红/黑树、AVL 树、AA 树、伸展树、treaps、替罪羊树、权重平衡树、RAVL 树等。这些数据结构中的每一个都尝试使用一些规则来平衡 BST以便查找、插入和删除速度很快。2-3 树是 BST 的变体，它允许每个节点有多个键，以便给出维持平衡的简单规则。问题通常不是“BST 何时比 2-3 树更好，反之亦然”，而是“2-3 树相对于其他平衡 BST 有何优势，反之亦然”，这就是问题所在您必须通过分析来弄清楚。

希望这可以帮助！