B+ Tree Index
Balanced tree data structure for database indexing
A B+ Tree index is a balanced, sorted tree data structure used by most relational databases to enable fast lookups, range scans, and ordered traversal of indexed columns.
Definition
A B+ Tree index is a balanced, sorted tree data structure used by most relational databases to enable fast lookups, range scans, and ordered traversal of indexed columns.
Overview
A B+ Tree is a variant of the B-tree data structure, adapted specifically for the way databases read and write data in fixed-size disk pages. Like a standard B-tree, it stays balanced as data is inserted and deleted, keeping all leaf nodes at the same depth so that any lookup takes a predictable, small number of page reads regardless of how large the table grows. Its key difference from a plain B-tree is that all actual data references live only in the leaf nodes, while internal nodes hold only routing keys used to navigate down to the correct leaf; the leaf nodes are also linked together in sorted order, forming an efficient path for range scans and ordered traversal. This structure is what makes B+ Trees the default index type in nearly every relational database — PostgreSQL, MySQL's InnoDB, SQLite, and Oracle all use B+ Trees as their primary index structure. A query like `WHERE age > 30` can walk down to the first leaf matching `age = 30` and then simply follow the linked leaf nodes forward, reading a contiguous sorted range without needing to re-traverse the tree for every row, which is far more efficient than the equivalent operation would be on a hash index, which offers fast equality lookups but no ordering. Each node in a B+ Tree typically holds many keys — often hundreds — sized to fill a single disk page, which keeps the tree's height very small even for tables with millions of rows; a table with a billion rows might still only require three or four page reads to find any given entry. Insertions and deletions maintain this balance automatically by splitting overfull nodes or merging underfull ones, which is what keeps lookup performance consistent as data changes over time. Databases also support other index types for different access patterns — hash indexes for pure equality lookups, and specialized structures like GiST, GIN, or inverted indexes for full-text search and complex data types — but B+ Trees remain the default general-purpose choice because they handle both equality and range queries well.
Key Concepts
- Balanced tree structure with all leaf nodes at equal depth
- Leaf nodes linked together in sorted order for efficient range scans
- Internal nodes hold routing keys only, not data references
- Default index structure in PostgreSQL, MySQL InnoDB, SQLite, and Oracle
- Node size tuned to disk page size, minimizing tree height and page reads
- Automatically rebalances via node splits and merges on insert or delete
- Supports both equality lookups and ordered range queries efficiently