Storage & Databases

B-tree

A balanced search tree whose nodes each hold many keys; the usual structure behind database indexes.

Main article: B-tree simulator and visualizer

In plain terms

Rudolf Bayer and Edward McCreight, Boeing Scientific Research Laboratories: a 1970 report, published in 1972. Wide nodes keep the tree shallow: with 200 keys per node, a billion records fit in 4 levels, where a balanced binary tree needs about 30.

Origin

Rudolf Bayer and Edward McCreight, working at Boeing Research Labs, published "Organization and Maintenance of Large Ordered Indexes" in 1972. The "B" is famously ambiguous: Bayer never said what it stood for. By 1979 Douglas Comer could title his survey "The Ubiquitous B-Tree".

Where it shows up in production

PostgreSQL Default index type for everything: primary keys, secondary indexes, unique constraints.
MySQL InnoDB Clustered B+tree: the table itself is the index, sorted by primary key.
Filesystems (ext4, NTFS, XFS) Directory entries and extent maps use B-tree variants.

On Semicolony

Simulator: btree Simulator: btree Data structures: data structures Data structures: data structures

Sources & further reading

Found this useful?