B and B+ trees

A B-tree is a search tree designed for disks, where reading one large block costs about the same as reading one byte. Instead of two children per node, each node fills a whole disk page and holds hundreds of sorted keys with pointers between them, so the tree is very wide and very shallow. A B+ tree, the common variant, keeps all actual records in the bottom layer and links those leaves in order, which makes range scans a straight walk. With hundreds of children per node, a billion rows are only three or four page reads from the root. Nearly every relational database index and many file systems are B+ trees.