B+Tree

Overview

An evolution of the B-Tree structure, optimized specifically for database systems and disk-based storage
Primary difference: B+ Trees separate key storage from data storage
Used by most modern database management systems (DBMS) for indexing

Internal Nodes: Store only keys (no values/data pointers)
- More compact, allowing more keys per node
- Enables faster traversal with fewer I/O operations
- Better CPU cache utilization
Leaf Nodes:
- Store both keys and data pointers (or actual data)
- All leaf nodes are linked together in a sequential linked list
- All data is stored at the same level (leaf level)
- Some implementations duplicate keys to improve search efficiency

Efficient Range Queries: The linked leaf nodes make range-based operations highly efficient
Faster Traversal: Internal nodes without data pointers can hold more keys, reducing tree height
More Balanced I/O: All records are at the same level, creating predictable access patterns
Sequential Access: Linked leaves allow fast sequential scanning of values
Space Efficiency: Higher fanout (branching factor) in internal nodes

Leaf pointer overhead is minimal (cheap in terms of storage)
Designed so one node typically fits exactly into one disk page (8KB in PostgreSQL, 16KB by default in MySQL InnoDB)
Internal nodes are small enough to be cached in memory for fast traversal
Where leaf nodes live depends on the engine: in PostgreSQL the index leaves are in the index file and hold pointers (TIDs) to rows in the separate heap; in InnoDB the clustered (PK) index leaves are the table rows
The majority of modern DBMS systems implement B+ Tree as their primary index structure

Secondary indexes point to the primary key rather than directly to the row
“Clustered index” architecture where the primary key IS the table organization
Leaf nodes contain the complete row data since it’s an IOT (Index-Organized Table)
Consideration: If the primary key is large (e.g., UUID), all secondary indexes become bloated