An index is defined on a wide key — say a 60-byte composite of text columns — instead of an 8-byte integer. Structurally, what changes inside the B+tree, and what are the practical consequences?

## The arithmetic Fanout is a byte budget: ``` entries per page ≈ usable page bytes / (key bytes + pointer bytes + slot overhead) ``` On an 8 KB page with ~8 KB usable minus headers, an 8-byte key plus a pointer and slot overhead lands near 16-20 bytes per entry — roughly 400-500 entries. A 60-byte key pushes the entry to ~70 bytes — roughly 100-110 entries. Fanout falls by about 5x. ## Effect one: tree height Height ≈ `ceil(log_f N)`. For a billion rows: - f = 500 → `log500(1e9) ≈ 3.6` → 4 levels - f = 100 → `log100(1e9) ≈ 4.5` → 5 levels So one extra level. Each level is one more page access per lookup — but the upper levels are cached, so this alone might cost close to nothing. ## Effect two: index footprint — the one that actually hurts The leaf level contains one entry per indexed row, so leaf bytes scale linearly with entry width. A 7x wider entry is a roughly 7x larger index. This is the effect that changes system behaviour, because caching is a cliff, not a slope: - If the index fits in the buffer pool, lookups are memory accesses: microseconds. - If it does not, leaf accesses become random reads against storage: hundreds of microseconds on SSD, milliseconds on spinning disk. An index that was comfortably resident at 2 GB and is now 14 GB may push not just itself but *other* hot data out of cache, degrading unrelated queries. The blast radius is the whole instance, not just queries using that index. Secondary costs follow the size: longer index builds and rebuilds, more write-ahead-log volume for index maintenance, more backup bytes, slower replication catch-up. ## Effect three: comparison cost Wide keys are usually strings, and string comparison under a collation is far more expensive than an integer compare. Every page descent does a binary search — around `log2(fanout)` comparisons per page — so a collation-aware comparison in the inner loop turns a formerly free CPU cost into a measurable one on high-QPS lookups. ## Effect four: the ripple through other indexes In a clustered (index-organized) storage model, every secondary index entry stores the primary key as its row reference. So a wide primary key is not paid once — it is paid in *every* secondary index on that table, inflating all of them and lowering their fanout too. This is the classic reason engines that cluster on the primary key push hard for narrow, ideally integer, primary keys. ## Effect five: what stays fine Correctness and query capability do not change. Range predicates, ordering, and prefix matching all still work. The index is not "broken" by being wide — it is simply more expensive per row it indexes, and the question is always whether the selectivity it buys is worth the bytes. ## Mitigations worth naming - **Narrow the key.** Use a compact surrogate key rather than a natural composite of text columns; store the wide natural value as a non-key column with a uniqueness constraint if you still need it enforced. - **Index a derived, narrow value.** Index a fixed-length hash or a truncated prefix of the wide column when equality lookup is the access pattern (accepting that you then verify the full value after the index probe, and that ranges no longer work on a hash). - **Trim the column list.** Composite indexes often carry columns that add little selectivity; the leading discriminating columns usually do nearly all the filtering work. - **Order columns by width and usefulness.** Once selectivity requirements are met, avoiding a very wide trailing column in the key keeps entries smaller. - **Rely on engine-side prefix truncation for separators.** Many engines already store abbreviated separators in branch pages, so the branch levels suffer less than the leaves — which reinforces that the leaf level is where the cost lives. ## How to answer aloud "Fanout is page bytes over entry bytes, so a 60-byte key cuts fanout roughly five-fold, from ~500 to ~100. That adds about one level of height for a billion rows, which is minor. The real cost is the leaf level: it holds one entry per row, so the index gets several times bigger and stops fitting in memory, turning cached lookups into random reads and evicting other hot pages. And under clustered storage a wide primary key inflates every secondary index too. I'd reach for a narrow surrogate key, or index a hash or prefix if the access pattern is equality."