i want to know which data structure(AVL, B-Tree, etc...) is used in most popular relational databases. and also in what way the data structure is superior than other in-class data structures? if possible a small comparison could help me a lot! thanks in advance!
A:
It's usually B-tree or variants thereof, primarily because it packs nodes into blocks, unlike binary trees such as AVL.
A node of a B-tree has a fixed maximum size and holds multiple keys and multiple pointers to child nodes, meaning fewer blocks need to be retrieved from disk to look up a value (compared to a binary tree).
The Wikipedia article on B+ trees has a good introduction from the angle of its application to databases.
Joey Adams
2010-10-26 19:31:25