Actually written as a B-Tree.

A DataStructure frequently used for disk based ISAM index files (eg SQL tables).

The Tree is built up from nodes like a BinaryTree, but unlike a binary tree each node can have more than two pointers. Pointers will be added to a node until it exceeds the size of a disk block at which point the node is split into two nodes which are now both half full.

This optimizes for minimum node access, assuming node storage reads and writes are expensive compared to in-memory key comparisons.

----
CategoryDataStructure