AVL tree vs. B-tree

Question

How is an AVL tree different from a B-tree?

Answer 1

AVL is self balancing, guaranteeing that all operations are O(log n) in average and worst cases.

Answer 2

An AVL tree is a self-balancing binary search tree, balanced to maintain O(log n) height.

A B-tree is a balanced tree, but it is not a binary tree. Nodes have more children, which increases per-node search time but decreases the number of nodes the search needs to visit. This makes them good for disk-based trees. For more details, see the Wikipedia article.

Answer 3

AVL trees are intended for in-memory use, where random access is relatively cheap. B-trees are better suited for disk-backed storage, because they group a larger number of keys into each node to minimize the number of seeks required by a read or write operation. (This is why B-trees are often used in file systems and databases, such as SQLite.)