The Balanced Search Tree (B-Tree) in Sql Databases
The index leaf nodes are stored in an arbitrary order—the position on the disk does not correspond to the logical position according to the index order.
A database needs a second structure to find the entry among the shuffled pages quickly: a balanced search tree—in short: the B-tree.
The doubly linked list establishes the logical order between the leaf nodes. The root and branch nodes support quick searching among the leaf nodes.
Once created, the database maintains the index automatically. It applies every insert, delete and update to the index and keeps the tree in balance, thus causing maintenance overhead for write operations.
The tree traversal is a very efficient operation—so efficient that I refer to it as the first power of indexing. It works almost instantly—even on a huge data set. That is primarily because of the tree balance, which allows accessing all elements with the same number of steps, and secondly because of the logarithmic growth of the tree depth.