Mediumb‑treeindexingdatabasesperformanceinterviews

Designing an Efficient B-Tree Index for Large Databases

A practical guide that turns B‑Tree theory into concrete index designs for billion‑row tables, covering fan‑out math, bulk‑load tricks, maintenance knobs, and interview‑ready scenarios.

glancED editorial

CS interview prep · Sep 2026

Most engineers treat a B‑Tree index as a black box and miss the lever that actually moves performance: how page size, key size, and fill factor shape fan‑out, height, and split cost. In real‑world systems a mis‑chosen fill factor can double write amplification, while a bulk‑load that respects disk block size can shave days off index build time. This guide shows the math, the knobs, and the interview questions you need to own when designing an efficient B‑Tree for massive databases.

B‑tree - Wikipedia PostgreSQL Documentation – B‑Tree Indexes MySQL Reference Manual – B‑Tree Indexes SQL Server Index Design Guide Cockroach Labs Blog – Inside B‑Tree Indexes CMU – B‑Tree Lecture Notes PostgreSQL BRIN Indexes

01From Theory to Disk: Mapping B‑Tree Parameters to Physical Pages

Fan‑out and height are pure functions of page size, key size and row count, and they predict I/O cost before any data lives on disk.

The first step is to translate abstract B‑Tree parameters into the concrete layout of a database page. Fan‑out = ⌊pageSize / (keySize + pointerSize)⌋. For an 8 KB page, a 16‑byte key, and an 8‑byte pointer, the theoretical maximum fan‑out is ⌊8192 / 24⌋ ≈ 341. In practice, every page reserves space for a header (page ID, checksum, free-space map), which reduces the usable byte count and lowers the effective fan‑out to ~335. Tree height follows ⌈log_fanout(N)⌉. With N = 1 billion rows and fan‑out ≈ 335, height = ⌈log₃₃₅(10⁹)⌉ = 3 (root → internal → leaf). This three‑level depth means a point lookup needs at most three random page reads, regardless of the billion rows. The math also shows why a 4 KB page halves fan‑out to ~170 and pushes height to 4, adding an extra I/O per lookup. Below is a tiny Python helper that prints fan‑out and height for any N, pageSize and keySize.

import math

def calc_fanout(page_size, key_size, pointer_size, header_size=64):
    usable = page_size - header_size
    return usable // (key_size + pointer_size)

def calc_height(n_rows, fanout):
    return math.ceil(math.log(n_rows, fanout))

# Example: 8KB page, 16B key, 8B pointer
fanout = calc_fanout(8192, 16, 8)
height = calc_height(1_000_000_000, fanout)
print(f"Fan-out: {fanout}, Height: {height}")

02B‑Tree vs B+Tree: Structural Differences and Range‑Query Impact

B+Trees store only keys in internal nodes and keep all data in linked leaf pages, which makes range scans dramatically cheaper than classic B‑Trees.

Classic B‑Trees duplicate data in every node, so a leaf‑to‑leaf scan incurs a random read for each leaf page. B+Trees, used by PostgreSQL, MySQL and SQL Server, keep only keys in internal nodes and store full rows exclusively in leaf pages that are linked via a sibling pointer. This design yields two practical benefits: (1) internal nodes are slimmer, increasing fan‑out and reducing height; (2) a range query walks the linked leaf chain with sequential I/O, cutting random reads by ~80 % (CMU notes). Use a B+Tree when you need fast point lookups and efficient ordered scans (e.g., ORDER BY or BETWEEN). Use a classic B‑Tree only in academic settings where you want to explore balanced tree invariants; production systems rarely choose it because the extra data duplication hurts both space and cache locality. The Postgres docs confirm that its default index type is a B+Tree precisely for these I/O characteristics.

03Bulk‑Load Strategies and Index Creation for Massive Tables

Loading a sorted dataset in bulk can cut index‑build I/O by up to 70 % versus inserting rows one‑by‑one.

When a table already lives on disk in sorted order on the indexed columns, the optimal path is a bulk‑load that writes leaf pages sequentially and builds internal nodes in a bottom‑up pass. PostgreSQL’s CREATE INDEX CONCURRENTLY avoids locking the table but still benefits from sorted input; MySQL’s ALTER TABLE … ALGORITHM=INPLACE does the same. The I/O estimate is simple: a bulk load writes each leaf page once and each internal page once, i.e. ≈ (N / fan‑out) + (N / fan‑out²) pages. In contrast, row‑by‑row inserts cause a page split for roughly every 1 / (1‑fill‑factor) insert, inflating I/O by up to 70 % (MySQL manual). The following SQL snippet shows a safe concurrent build in PostgreSQL, followed by an EXPLAIN that proves the index is used.

CREATE INDEX CONCURRENTLY idx_users_last_first ON users (last_name, first_name);
EXPLAIN ANALYZE SELECT * FROM users WHERE last_name='Smith' AND first_name > 'A';

04Maintenance Mechanics: Splits, Merges, and Fill Factor

Fill factor controls how much free space each page reserves, directly influencing split frequency and write amplification.

A page split occurs when an insert finds a leaf page at its fill‑factor limit. The DBMS creates two new pages, redistributes keys, and updates the parent – costing roughly 3 I/Os on SSD (Cockroach Labs). PostgreSQL’s default fill factor for B‑Tree indexes is 90 %, meaning each page leaves 10 % slack for future inserts. Lowering fill factor to 70 % reduces split frequency but wastes space; raising it to 95 % saves space but can cause frequent splits under heavy write workloads. Merges (or deletions) are the opposite: when a page falls below a low‑water mark, it can be merged with a sibling, reclaiming space. Some engines perform lazy merges during background vacuum, while others do eager merges on delete. The trade‑off is space versus write amplification: a 70 % fill factor may halve split‑related I/O but increase total index size by ~15 %. Choose the fill factor based on the write‑read ratio: heavy inserts → lower fill; read‑heavy workloads → higher fill.

05B‑Tree vs BRIN/GiST: Hybrid Indexing and Partitioning

Use BRIN for massive, append‑only columns; fall back to B‑Tree when selective point lookups dominate.

PostgreSQL’s BRIN (Block Range INdex) stores min/max summaries per block range, making the index 10‑100× smaller for monotonically increasing columns (Postgres docs). This is ideal for time‑series tables with billions of rows where queries filter by recent timestamps. However, BRIN’s selectivity is coarse; point lookups on a primary key still need a full scan of the range. GiST indexes support multidimensional data (e.g., geometric or full‑text) but have higher per‑lookup cost than B‑Tree. A practical hybrid is to partition a large table by month, then attach a B‑Tree on the primary key within each partition and a BRIN on the timestamp column across partitions. The optimizer can prune partitions early, then use the B‑Tree for exact matches, achieving low I/O and manageable index size. Use a B‑Tree when you need high selectivity and frequent range scans on non‑monotonic columns; switch to BRIN when the column is append‑only and queries are mostly time‑bounded.

06Cache, Buffer Pool, and I/O Cost Modeling

Estimating lookup I/O becomes a simple formula once you know tree height, buffer pool coverage, and working set size.

Assume an 8 KB page, fan‑out ≈ 335, height = 3, and a buffer pool that can hold 1,000 leaf pages (≈ 8 MB). For a point lookup, the root and internal nodes are almost always cached, so the expected I/O is 1 leaf‑page read if the target leaf is not in memory. With a 90% fill factor, each leaf holds ≈ 300 keys; for 1 billion rows, there are ~3.3 M leaf pages. The probability a random lookup hits a cached leaf is 1,000 / 3,300,000 ≈ 0.03%. This implies a disk read for the vast majority of lookups only if the working set (the subset of rows actively queried) exceeds the buffer pool capacity. If your application only accesses 500,000 rows, a 4 MB buffer pool would achieve a near-100% hit rate, making I/O cost negligible. If we increase the buffer pool to hold 100,000 leaf pages, the hit rate for the full table rises to 3%, and expected I/Os drop to 0.97. This simple model lets you quantify the ROI of adding RAM versus tuning fill factor. The math aligns with the Cockroach Labs split cost analysis: each split adds three extra I/Os, so reducing splits via a lower fill factor can be as valuable as a modest RAM increase.

07Interview‑Ready Scenarios and Common Pitfalls

Typical interview questions probe your ability to compute fan‑out, height, and the impact of fill factor on performance.

Scenario 1: Given N = 500 M rows, 8 KB pages, 12‑byte keys, compute expected lookup I/Os. → fan‑out ≈ 8192 / (12+8) ≈ 512, height = ⌈log₅₁₂(5×10⁸)⌉ = 3, so at most 3 random reads. Scenario 2: Design an index for a composite WHERE clause (country, created_at) with frequent range scans on `created_at`. → Use a B+Tree with (country, created_at) order; the leading column enables partition pruning, the linked leaves make the date range scan sequential. Pitfall A: Assuming an index is static – after many inserts the fill factor may drop, causing frequent splits and degrading performance. Pitfall B: Forgetting to analyze EXPLAIN output; an index can be ignored if the planner estimates a cheaper sequential scan due to outdated statistics. Pitfall C: Building an index on a low‑cardinality column without a composite key – the index size may outweigh any benefit. Master these patterns and you’ll impress interviewers with both theory and pragmatic system‑level insight.

function insert(node, key):
    if node.isLeaf:
        node.keys.append(key)
        if len(node.keys) > maxKeys:
            split(node)
    else:
        child = chooseChild(node, key)
        insert(child, key)
        if child.isOverflow():
            split(child)

function split(node):
    mid = len(node.keys)//2
    left = node.keys[:mid]
    right = node.keys[mid+1:]
    promote = node.keys[mid]
    newSibling = createNode(right)
    node.keys = left
    parent.insert(promote, newSibling)
    return newSibling

08Common interview questions

Rapid-fire Q&A an interviewer is likely to ask.

How do you estimate the number of I/Os for a point lookup on a B‑Tree index?

Compute fan‑out from page and key size, derive tree height = ⌈log_fanout(N)⌉, then assume the root and internal nodes are cached; the expected I/Os equal the probability the leaf page is in the buffer pool plus one for a miss.

When would you choose a BRIN index over a B‑Tree for a 10 billion‑row time‑series table?

If the timestamp column is strictly increasing and queries filter by recent intervals, a BRIN’s block‑range summaries give 10‑100× smaller storage and comparable scan speed, making it the right choice.

What effect does lowering the fill factor from 90 % to 70 % have on write performance?

It leaves more free space per page, reducing page‑split frequency and write amplification, at the cost of larger index size (≈ 15 % more pages).

Explain the cost of a page split on SSD and why it matters for bulk loads.

A split writes two new leaf pages and updates the parent, costing about three I/Os on SSD. During bulk loads you avoid splits by loading data in sorted order, saving millions of I/Os.

Write pseudocode for handling a node split during B‑Tree insertion and state its amortized cost.

Amortized cost is O(1) splits per insert because a split only occurs once every maxKeys inserts.

function insert(node, key):
    if node.isLeaf:
        node.keys.append(key)
        if len(node.keys) > maxKeys:
            split(node)
    else:
        child = chooseChild(node, key)
        insert(child, key)
        if child.isOverflow():
            split(child)

function split(node):
    mid = len(node.keys)//2
    left = node.keys[:mid]
    right = node.keys[mid+1:]
    promote = node.keys[mid]
    create new sibling with right
    insert promote into parent

Up next

Dynamic Programming

A hard‑level guide that teaches you how to choose DP state, prove optimal substructure, and squeeze memory, with real‑world interview examples and runnable code.