B+ Tree
A B+ tree is a B-tree variant: data lives only in leaf nodes, internal nodes hold only keys and pointers, and leaves are chained to support range scans.
Purpose
To understand the most common index variant in databases and optimize range queries and sequential access.
Mechanism
Internal nodes hold only index keys (high fan-out); leaf nodes hold keys + data + next pointers. Range scans read sequentially along the leaf chain. Deletions affect only leaves. Nearly all relational database indexes use B+ trees.
Use cases
- Range query optimization
- Index design
- Database internals