AVL 树与 B 树有何不同？
问问题
49321 次
9 回答
55
AVL 树旨在用于内存中，其中随机访问相对便宜。B 树更适合磁盘支持的存储，因为它们将大量的键分组到每个节点中，以最大限度地减少读取或写入操作所需的查找次数。（这就是为什么 B-trees 经常用于文件系统和数据库，例如SQLite。）
于 2010-04-29T04:07:44.187 回答
46
AVL 树和 B 树的相似之处在于它们都是数据结构，通过它们的要求，它们各自的树的高度被最小化。这种“短”允许在 O(log n) 时间内执行搜索，因为最大可能的读取数对应于树的高度。
5
/ \
3 7
/ / \
1 6 9
这是一棵 AVL 树，其核心是二叉搜索树。但是，它是自平衡的，这意味着当您向树中添加元素时，它会自行重组以尽可能保持高度一致。基本上，它不允许长分支。
B-tree 也这样做，但通过不同的重新平衡方案。写出来有点太复杂了，但是如果你用谷歌搜索“B-tree animation”，那里有一些非常好的小程序可以很好地解释 B-tree。
它们的不同之处在于，AVL 树的实现考虑了基于内存的解决方案，而 B-tree 的实现考虑了基于磁盘的解决方案。AVL 树不是为保存大量数据而设计的，因为它们使用动态内存分配和指向下一个内存块的指针。显然，我们可以使用磁盘位置和磁盘指针复制 AVL 树的功能，但它会慢得多，因为我们仍然需要大量读取来读取非常大的树。
当数据集合太大以至于无法放入内存时，解决方案是 B 树（有趣的事实：对于“B”实际代表什么没有达成共识）。一棵 B 树在一个节点上拥有许多子节点和许多指向子节点的指针。这样，在磁盘读取期间（读取单个磁盘块可能需要大约 10 毫秒），将返回最大数量的相关节点数据，以及指向“叶节点”磁盘块的指针。这允许将数据的检索时间摊销到 log(n) 时间，使 B-tree 对于数据库和大型数据集检索实现特别有用。
于 2011-04-05T21:16:19.770 回答
19
AVL 树是一个自平衡二叉搜索树，平衡到保持 O(log n) 高度。
B树是平衡树，但不是二叉树。节点有更多的子节点，这增加了每个节点的搜索时间，但减少了搜索需要访问的节点数量。这使得它们非常适合基于磁盘的树。有关更多详细信息，请参阅维基百科文章。
于 2010-04-29T04:06:10.460 回答
4
AVL 树是一种自平衡二叉树，它为搜索插入和删除操作启用 O(lgN) 平均和最坏情况。它用于内存支持的搜索树（中等大小的数据集）。
B-Tree 主要用作非常大数据集的存储支持搜索树，因为它需要较少的磁盘读取（因为每个节点包含 N 个键，其中 N >1）。B-Tree 被称为 (N,N+1) B-Tree，其中 N 是每个节点的键数，N+1 是每个节点的子节点数。每个节点的键越多，您需要从磁盘读取的次数就越少，而且它自然也会是更浅的树（更少的级别）。
于 2012-12-17T05:35:03.310 回答
2
B-tree 使用了上面描述的所有想法。特别是，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-tree 可以处理任意数量的插入和删除。
于 2012-10-02T07:17:42.240 回答
2
AVL 是自平衡的，保证所有操作在平均和最坏情况下都是 O(log n)。
于 2010-04-29T04:02:50.517 回答
2
其他回答者已经提供了关于 AVL 和 B-Tree 的相当深入的技术细节，但我想添加关于这两者的相对新手信息：
- AVL树是二叉树，而B树是多路树（N-ary树），即AVL树中的任何节点最多可以有两个子节点和一个信息/数据，而B树中的任何节点可以有n 个节点和 n-1 条信息/数据。对于 B-tree，n 也称为它的阶。
于 2017-12-30T00:04:12.497 回答
2
它们确实非常不同，尽管它们的目的大致相同：支持关联表。从历史上看，AVL 树在内存中操作方面的性能优于 B 树，但与 CPU 周期相比，当访问内存成本更低时尤其如此。
虽然通常在数据库中用于存储可变长度的键，但 B 树在固定长度和短记录（键 + 数据）中表现最好。对于此类用途，在内存占用（因为它们更紧凑地存储数据）和速度（它们将具有更好的缓存局部性）方面，这可能显着优于 AVL 树的内存使用。
L2是一个数据结构库，在 B 树上实现非常快速的关联表和序列。它也有 AVL 树，很容易比较两者的性能。
于 2018-01-18T10:35:21.367 回答
0
B树
这里的一个典型用例是磁盘上的数据库，在树中向下一层查找项目的成本很高。当你不得不这样做时，你需要尽可能多地削减工作量。每个 b 树都有一个最大度数，每个节点都保存项目和对其他节点的引用（n 个项目，n+1 个引用）。这一事实使存储和以后在磁盘上查找大块项目变得容易。它还允许您在添加/删除项目时避免重写树的大块。
AVL 树
自平衡平衡二叉树品种。平衡二叉树是最大高度为 的树log(n)。
于 2020-06-14T14:28:45.180 回答