AVL树 vs. B树

Question

AVL树 vs. B树

data-structuresb-treeavl-tree

50

AVL树和B树有何不同之处？

- neuromancer

10个回答

47

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

这是一棵AVL树，本质上是一棵二叉搜索树。但是，它是自平衡的，也就是说，当您向树中添加元素时，它会重新构造自身以保持尽可能均匀的高度。基本上，它不会允许长分支。

B树也可以通过不同的重新平衡方案实现此功能。但是它有点复杂，不过如果您在Google上搜索“B-tree animation”，就会有一些非常好的程序解释B-tree所要实现的功能。

它们的不同之处在于AVL树是用内存为基础来实现的，而B树则是用磁盘为基础来实现的。由于AVL树使用动态内存分配和指向下一个内存块的指针，因此它们并不适合存储大量数据。显然，我们可以使用磁盘位置和磁盘指针来复制AVL树的功能，但是速度会慢很多，因为我们仍然需要读取数量相当大的树的节点。

当数据集太大无法放入内存时，解决方案是使用B树（有趣的事实：对于“B”的含义，人们没有共识）。B树在一个节点上保存多个子节点和指向子节点的指针。这样，在磁盘读取期间（可能需要约10毫秒来读取一个磁盘块），会返回最大量的相关节点数据以及指向“叶节点”磁盘块的指针。这使得检索数据的时间可以将其平均为log(n)时间，使B树在数据库和大型数据集检索实现中特别有用。

- Keshav Saharia

在谷歌上搜索了“B树动画”，并找到了一个相关的SO线程。动画确实非常有帮助。感谢这个想法。 - RBT

21

AVL树是一种自平衡的二叉搜索树，通过平衡维护O(log n)的高度。

B树也是一种平衡树，但它不是二叉树。节点拥有更多子节点，这增加了每个节点的搜索时间，但减少了搜索需要访问的节点数。因此它们适用于基于磁盘的树。更多详细信息请参见维基百科文章。

- Michael Ekstrand

4

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

B-Tree主要用作存储支持的搜索树，用于处理非常大的数据集，因为它需要较少的磁盘读取（每个节点包含N个键，其中N>1）。B-Tree被称为(N,N+1) B-Tree，其中N是每个节点的键数，N+1是每个节点的孩子数。每个节点中有更多的键，则需要从磁盘中读取的次数更少，同时它也会自然地成为一个更浅的树（更少的层级）。

- Aaron Dancygier

3

它们确实非常不同，尽管它们基本上服务于相同的目的：支持关联表。历史上，AVL树被认为在内存操作方面优于B树，但是当访问内存比CPU周期便宜时，这点尤其正确。

B树通常用于存储可变长度键的数据库，但是对于定长和短记录（键+数据），B树的性能最佳。对于这样的用途，B树在内存使用方面可以显着优于AVL树，无论是在内存占用（因为它们更紧凑地存储数据）还是速度方面（它们具有更好的缓存位置）。

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

- Ciprian Niculescu

2

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树可以处理任意数量的插入和删除。

- Tanmoy De

它是 vs. 未定义 b+。 - Sohaib Aslam

2

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

- James Kolpack

4

非常正确，但B树也展示了同样的特性。不是吗？那么AVL树与B树有什么不同呢？ - RBT

2

其他回答者已经提供了关于AVL树和B-树的相当深入的技术细节，但我想补充一些相对新手的信息：

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

- RBT

0

B树

这里的一个典型应用场景是在硬盘上的数据库中，当你需要向下遍历树找到一个项目时会很耗费时间。当你必须执行此操作时，需要尽可能地减少工作量。每个B树都有一个最大度数，每个节点都包含一些项目和对其他节点的引用（n个项目，n+1个引用）。这个事实使得在硬盘上存储和查找项目的块变得很容易。它也允许您在添加/删除项目时避免重新编写树的大块。

AVL树

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

- Karuhanga

0

树是编程中简单的抽象层次数据结构，用于保护私有存储数据。它具有具有父子关系的节点。根节点是没有父节点的节点，并且是树的起始节点。

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

二叉搜索树是二叉树的进一步改进。除了满足二叉树的条件外，它必须在父子之间具有以下关系：

左子节点<= 父节点 <= 右子节点

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

必须遵循BST的条件
必须是平衡树，即除了最后一层外，每一层都完全填充，并且底层从左到右添加节点，如果一个节点的底层存在右侧子节点，则也必须存在左侧子节点。

- Vishal Sharma

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David · Accepted Answer

AVL树适用于内存中的使用，其中随机访问相对较便宜。B树更适合磁盘支持的存储，因为它们将更多的键值分组到每个节点中，以最小化读取或写入操作所需的查找次数。(这就是为什么B树通常用于文件系统和数据库，例如SQLite。)