B-tree
Balanced multi-way search tree; the shape of every relational index.
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. B-trees became the standard relational index almost immediately.
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
Sources & further reading
Found this useful?