AVL树与B树

AVL树与B树有何不同？

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

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

    5
   / \
  3   7
 /   / \
1   6   9

这是一个AVL树,它的核心是二叉搜索树.但是,它是自平衡的,这意味着当您向树中添加元素时,它将重构自身以保持尽可能高的均匀.基本上,它不允许长分支.

B树也可以这样做,但是通过不同的重新平衡方案.写出来有点过于复杂,但如果你谷歌搜索"B树动画",那里有一些非常好的小程序可以很好地解释B树.

它们的不同之处在于AVL树是在考虑基于内存的解决方案的情况下实现的,而B树是在考虑基于磁盘的解决方案的情况下实现的.AVL树不是为容纳大量数据而设计的,因为它们使用动态内存分配和指向下一块内存的指针.显然,我们可以使用磁盘位置和磁盘指针来复制AVL树的功能,但它会慢很多,因为我们仍然会有大量的读取来读取非常大的树.

当数据收集太大而不适合内存时,解决方案就是一个B树(有趣的事实:对于"B"实际上代表什么没有达成共识).B树在一个节点处拥有许多子节点,并且有许多指向子节点的指针.这样,在磁盘读取期间(读取单个磁盘块大约需要10毫秒),将返回最大量的相关节点数据,以及指向"叶节点"磁盘块的指针.这允许将数据的检索时间分摊到log(n)时间,使得B树对于数据库和大型数据集检索实现特别有用.

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

B树是平衡树,但它不是二叉树.节点有更多子节点,这会增加每个节点的搜索时间,但会减少搜索需要访问的节点数.这使它们适用于基于磁盘的树.有关更多详细信息,请参阅Wikipedia文章.