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

Question

我正在查看我的数据结构类(class)中的 Material ，我对这三种树的用法感到有些困惑。那么在什么情况下我们最好分别使用二叉搜索树、2-3树和B-tree呢？优缺点是什么？

非常感谢!我对数据结构很陌生......

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 树、张开树、treap、替罪羊树、权重平衡树、RAVL 树等。 这些数据结构中的每一个都试图使用一些规则来平衡 BST这样查找、插入和删除都很快。 2-3 树是 BST 的一种变体，它允许每个节点有多个键，以便给出保持平衡的简单规则。问题通常不会是“什么时候 BST 比 2-3 树更好，反之亦然”，而是“2-3 树与其他平衡 BST 相比有什么优势，反之亦然”，这就是问题你必须通过分析来弄清楚。

希望这可以帮助!