B-tree

A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.

In more detail

A B-tree of minimum degree t keeps between t minus one and 2t minus one keys in each node (the root may hold fewer) and up to 2t children. Each node is sized to one disk block, so every level costs one disk read, and a fan-out in the hundreds or thousands keeps even billions of keys within three or four levels. Inserts split full nodes on the way down, so all leaves stay at the same depth.

Related terms

Taught in

References