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

Technology CommunityCategory: Binary TreeHow is an AVL tree different from a B-tree?
VietMX Staff asked 3 years ago

Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This “shortness” allows searching to be performed in O(log n) time, because the largest possible number of reads corresponds to the height of the tree.

But:

  • An AVL tree is a self-balancing binary search tree. AVL trees are intended for in-memory use, where random access is relatively cheap. AVL trees are not designed to hold massive collections of data, as they use dynamic memory allocation and pointers to the next block of memory.
  • B-tree is a balanced tree, but it is not a binary tree )rather it’s multi-way tree (N-ary tree)). B-Trees are better suited for disk-backed storage. A B-tree holds many children at one node and many pointers to children node. This way, during a disk read (which can take around 10 ms to read a single disk block), the maximum amount of relevant node data is returned, as well as pointers to “leaf node” disk blocks. This allows retrieval time of data to be amortized to log(n) time, making the B-tree especially useful for database and large dataset retrieval implementations.