B-Tree
A B-tree is a self-balancing multi-way search tree where each node holds multiple keys and child pointers, guaranteeing O(log N) lookups with O(1)-ish fan-out.
Purpose
To understand the core data structure of database indexes and analyze its read/write performance and page fill.
Mechanism
An order-m B-tree has at most m children per node and at least ceil(m/2). Inserts split and deletes merge to stay balanced; all leaves are at the same depth. Node size aligns with database page I/O (e.g., 16KB), and high fan-out keeps the tree short (3-4 levels index TBs).
Use cases
- Index data structures
- Database internals
- Storage optimization