AVL 树与 B 树

Question

AVL 树与 B 树有何不同？

Answer 1

AVL 树旨在用于内存中使用，其中随机访问相对便宜。 B 树更适合磁盘支持的存储，因为它们将大量的键分组到每个节点中，以最大限度地减少读取或写入操作所需的查找次数。 （这就是为什么 B 树经常用于文件系统和数据库，例如 SQLite。）

Answer 2

AVL 树和 B 树的相似之处在于，它们都是数据结构，通过它们的要求，导致各自树的高度最小化。这种“短度”允许在 O(log n) 时间内执行搜索，因为最大可能的读取次数对应于树的高度。

    5
   / \
  3   7
 /   / \
1   6   9

这是一棵AVL树，其核心是一棵二叉搜索树。然而，它是自平衡的，这意味着当您向树添加元素时，它会自行重组以尽可能保持高度的均匀性。基本上，它不会允许长分支。

B 树也可以做到这一点，但通过不同的重新平衡方案。写起来有点太复杂了，但是如果你在 Google 上搜索“B 树动画”，就会发现一些非常好的小程序可以很好地解释 B 树。

它们的不同之处在于，AVL 树是基于基于内存的解决方案来实现的，而 B 树是基于基于磁盘的解决方案来实现的。 AVL 树并不是为了保存大量数据而设计的，因为它们使用动态内存分配和指向下一个内存块的指针。显然，我们可以使用磁盘位置和磁盘指针来复制 AVL 树的功能，但速度会慢得多，因为我们仍然需要大量的读取来读取非常大的树。

当数据集合太大而无法放入内存时，解决方案是 B 树（有趣的事实：对于“B”实际代表什么还没有达成共识）。一棵 B 树在一个节点上保存有许多子节点，并且有许多指向子节点的指针。这样，在磁盘读取期间（读取单个磁盘块可能需要大约 10 毫秒），将返回最大量的相关节点数据以及指向“叶节点”磁盘块的指针。这使得数据的检索时间可以摊销到 log(n) 时间，使得 B 树对于数据库和大型数据集检索实现特别有用。

Answer 3

AVL 树是一种自平衡二叉搜索树，平衡以保持 O(log n) 高度。

B树是平衡树，但它不是二叉树。节点有更多的子节点，这会增加每个节点的搜索时间，但会减少搜索需要访问的节点数量。这使得它们非常适合基于磁盘的树。有关更多详细信息，请参阅维基百科文章。

Answer 4

AVL 树是一种自平衡二叉树，它可以实现 O(lgN) 平均和最坏情况的搜索插入和删除操作。它用于内存支持的搜索树（中等大小的数据集）。

B 树主要用作非常大的数据集的存储支持的搜索树，因为它需要较少的磁盘读取（因为每个节点包含 N 个键，其中 N > 1）。 B 树被称为 (N,N+1) B 树，其中 N 是每个节点的键数，N+1 是每个节点的子节点数。每个节点的键越多，您需要从磁盘读取的次数就越少，并且它自然也会是一个更浅的树（更少的级别）。

Answer 5

其他回答者已经提供了有关 AVL 和 B 树的相当深入的技术细节，但我想添加有关这两者的相对新手信息：

• AVL 树是二叉树，而 B 树是多路树（N -ary 树）即 AVL 树中的任何节点都可以最多两个子节点和一条信息/数据而 B-tree可以有n个节点和n-1条信息/数据。对于 B 树，n 也称为它的阶数。

Answer 6

它们确实非常不同，尽管它们的目的大致相同：支持关联表。从历史上看，AVL 树在内存操作方面优于 B 树，但当访问内存比 CPU 周期便宜时尤其如此。

虽然 B 树通常用于数据库存储可变长度键，但 B 树对于固定长度和短记录（键 + 数据）表现最佳。对于此类用途，无论是在内存占用（因为它们存储数据更紧凑）还是速度（它们有更好的缓存局部性）方面，这可能会明显优于内存中使用的 AVL 树。

L2 是一个数据结构库，通过 B 树实现非常快速的关联表和序列。它还具有 AVL 树，可以轻松比较两者的性能。

Answer 7

B 树使用了上述所有思想。特别是 B 树：

1)keeps keys in sorted order for sequential traversing
2)uses a hierarchical index to minimize the number of disk reads
3)uses partially full blocks to speed insertions and deletions
4)keeps the index balanced with an elegant recursive algorithm

此外，B 树通过确保内部节点至少半满来最大限度地减少浪费。 B 树可以处理任意数量的插入和删除。

Answer 8

AVL 是自平衡的，保证所有操作在平均和最坏情况下都是 O(log n)。

Answer 9

B 树

这里的一个典型用例是磁盘上的数据库，在树中向下一级查找项目的成本很高。当你必须这样做时，你需要尽可能减少工作量。每个b树都有一个最大度，每个节点保存项目和对其他节点的引用（n个项目，n+1个引用）。这一事实使得在磁盘上存储和稍后查找项目块变得容易。它还允许您在添加/删除项目时避免重写树的大块。

AVL 树

一种自平衡平衡二叉树变体。平衡二叉树是最大高度为 log(n) 的一棵树。

Answer 10

树是编程中一种简单抽象（保护私有存储数据）的分层数据结构。它有具有父子关系的节点。根节点是没有父节点的节点，是树的起始节点。

二叉树是对树的修改，它遵循以下条件：
每个节点最多可以有 2 个子节点

二叉搜索树是二叉树的进一步修改。除了二叉树的条件外，父级和子级之间必须具有以下关系：
左子树 <= 父树 <= 右子树

AVL 树是 BST 的进一步修改。它必须具有以下性质：

1. 必须满足 BST 的条件
2. 必须是一棵平衡树，除了最后一层外，每一层都被完全填满，并且最底层有从左到右添加的节点。这样，如果节点的底层存在右子节点，则也必须有左子节点。