database - AVL 树与平衡树

Question

AVL树是众所周知的内部存储器数据结构，而平衡树是众所周知的外部存储器数据结构。 为什么我们不能将平衡树也用于内存？

Answer 1

您可以在内存中拥有平衡树。 AVL 树只是平衡树的一种，还有其他树，例如红黑树和 2-3-4 树。

所以，我不确定你从哪里得到平衡树不可能存在于内存中的想法，但如果我是你，我会重新考虑这一点。

事实上，如果您愿意的话，您也可以将 AVL 树放在磁盘上。

---

根据您的评论，我怀疑您可能想到的是一棵 BTree，它就像一棵二叉树，但每个节点可以保存多个值并且有两个以上的子节点，如:

root node -,
           |
           V
 +------+------+------+
 | Val1 | Val2 | val3 |
 +------+------+------+
/       |      |      \
<other nodes down here>

这与更通用的术语“平衡树”不同，它们通常用于磁盘情况，因为您倾向于一次读/写整个 block /集群/扇区。

因此，如果您可以将十个值放入一个磁盘 block 中，那么使用 BTree 会更有效(而内存没有 block 大小的概念，因此最好使用更简单的算法 - BTree 必须将两者结合起来树搜索查找节点，线性/二元搜索查找节点中的值。

但是，虽然 BTree 可以是平衡树的类型，但它也只是一种类型。