The Mathematics of Indexing: Page Layouts and Leaf Overheads
Database indexes are essential structures used to speed up query retrieval. By creating an ordered map of keys, the database engine can locate specific rows without scanning the entire table. However, indexes are not free; they consume substantial disk space and require dedicated RAM caches. Sizing this overhead requires evaluating the physical page geometry of the index engine.
Relational databases (like PostgreSQL and MySQL) utilize B-Tree indexes. A B-Tree page is structured into fixed-size blocks (typically 8 KB). Within each leaf page, the index stores the key, a pointer to the physical row (tuple identifier), and block headers. The capacity of a page is limited by its fill factor. The number of leaf pages required is: N_(leaf) = ⌈ \frac{N_(rows)}{⌊ (S_(page) - H_(page))/(S_(entry) × (F/100)) ⌋} ⌉ where S_(page) is the page size (8192 bytes), H_(page) is the page header overhead (24 bytes), S_(entry) is the entry size (key + tuple pointer + line pointer + padding), and F is the fill factor percentage.
To model broad database scaling architectures, you can project capacity limits using the database sharding capacity planner or track cache memory boundaries with the Redis cluster memory sizing calculator. Sizing indexing overhead is key to preventing system disk exhaustion.
Let's calculate the index size for a table with 50 million rows, utilizing a 64-bit integer primary key (8 bytes) in a B-Tree index with a 90% fill factor. Each leaf entry adds roughly 16 bytes of overhead (row header, line pointer, and alignment padding) on top of the key itself, so the entry size is: S_(entry) = 8 (key) + 16 (overhead) = 24 bytes. The entries per page are: E = ⌊ ((8192 - 24) × 0.90) / 24 ⌋ = ⌊ 7351.2 / 24 ⌋ = 306 entries/page. Leaf pages required: N_(leaf) = ⌈ 50,000,000 / 306 ⌉ = 163,399 pages. Adding 2% interior node overhead yields 166,667 total pages, representing $1,365,336,064 bytes (1.27 GB)$ of primary index storage.
If you create multiple secondary indexes (e.g., on email or creation date), each index represents a separate B-Tree array. With a 16-byte secondary key, the entry size is 32 bytes, giving 229 entries/page and 222,708 total pages for one index — about 1.70 GB. For a table with 3 such secondary indexes, the combined secondary index overhead is: S_(secondary) = 3 × 222{,}708 × 8192 ≈ 5.10 GB. Sizing these indexes shows that secondary index storage can easily exceed the primary index and even approach raw table storage, especially with several wide text columns, requiring careful column selection.