B Trees
A B-tree is a balanced tree designed to be stored on a disk.
Disks can only read and write (large)fixed-size blocks of data at once. A B-tree stores multiple keys in each of its nodes so that (1) a single diskread can access a lot of keys, and (2) the branching factor of the tree is very high (in practice, 1000+), sothat a tree of small height can store a huge number of keys, any of which can be accessed with just a fewdisk operations
