B+ Tree

Rudolf Bayer & Edward M. McCreight, 1973

The B+ tree (1973) keeps satellite data in leaves so internal nodes stay small and sequential I/O scans only touch the leaf chain. This exhibit traces a key lookup routing through internal nodes down to the correct leaf.