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_{\text{leaf}} = \left\lceil \frac{N_{\text{rows}}}{\left\lfloor \frac{S_{\text{page}} - H_{\text{page}}}{S_{\text{entry}} \times \left(\frac{F}{100}\right)} \right\rfloor} \right\rceil$$ where \(S_{\text{page}}\) is the page size (8192 bytes), \(H_{\text{page}}\) is the page header overhead (24 bytes), \(S_{\text{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. In a standard B-Tree implementation, the entry size is: $$S_{\text{entry}} = 8\text{ (key)} + 8\text{ (header)} + 4\text{ (line pointer)} = 20\text{ bytes}$$. The entries per page are: $$E = \lfloor ((8192 - 24) \times 0.90) / 20 \rfloor = \lfloor 7351.2 / 20 \rfloor = 367\text{ entries/page}$$. Leaf pages required: $$N_{\text{leaf}} = \lceil 50,000,000 / 367 \rceil = 136,240\text{ pages}$$. Adding 2% interior node overhead yields 138,964 total pages, representing $1,138,401,280\text{ bytes (1.14 GB)}$ of index storage.
If you create multiple secondary indexes (e.g., on email or creation date), each index represents a separate B-Tree array. If a table has 3 secondary indexes with an average key size of 16 bytes, the secondary index storage overhead is: $$S_{\text{secondary}} = 3 \times N_{\text{pages}} \times S_{\text{page}} = 3.65\text{ GB}$$. Sizing these indexes shows that index storage can easily exceed raw table storage, especially for tables with wide text columns, requiring careful column selection.