B-Tree Algorithm

The B-tree algorithm organizes a self-balancing tree whose nodes can each hold many keys and many child pointers rather than the single key and two children of an ordinary binary search tree, keeping every leaf at the same depth and allowing search, insertion and deletion to run in time proportional to the logarithm of the number of stored keys. Searching descends from the root by comparing the target key against the separating keys held in each node to choose which child to follow; inserting or deleting a key can leave a node holding too many or too few keys, which the algorithm resolves by splitting an overfull node into two or merging or redistributing keys around an underfull one, always preserving the tree's balance in the process. Because a wide, shallow B-tree needs far fewer node visits to reach any given key than a binary tree of the same size, and each node visit can be an expensive disk access on a system with large data sets, the structure is a standard building block of database indexes and file systems. Rudolf Bayer and Edward McCreight invented the B-tree in 1970 while working at Boeing's research labs, needing an efficient way to index very large randomly accessed files, and first circulated their paper "Organization and maintenance of large ordered indices" that July; neither author left a definitive account of what the letter B in the name stands for, with Balanced, Boeing, Broad and Bayer himself all offered as candidates.