The B-tree data structure serves as a fundamental building block for modern database management systems, including MySQL, Postgres, MongoDB, and Dynamo.
Engineers use these structures to create indexes that allow for efficient data lookups. By organizing data into a tree-like hierarchy, these systems can locate specific information without scanning entire datasets.
According to Ben Dicken of PlanetScale, B-trees are uniquely suited for large-scale data stored on long-term physical disks. The structure allows developers to align node sizes with disk blocks, such as 4k or 16k units.
Optimizing for Disk Storage
Unlike RAM, which is addressable by individual bytes, hard drives and SSDs read and write data in fixed blocks. B-trees leverage this by sizing nodes to match these hardware blocks.
This alignment minimizes the number of disk accesses required to find a key. A tree with only three levels can potentially manage over 300 million key/value pairs if the nodes are appropriately sized.
Searching a B-tree involves navigating from a root node through internal nodes until reaching the target. Because each node contains sorted keys, the system can quickly determine which child pointer to follow.
Many modern databases utilize a more advanced version known as the B+tree. In a B+tree, all actual key/value pairs reside exclusively in the leaf nodes, while non-leaf nodes only store keys and pointers.
This separation allows for more efficient range scans and streamlined navigation. The structure ensures that all leaf nodes remain on the same level, maintaining a predictable depth for data retrieval.