Storage & Indexing

Before writing a single line of SQL, a database engineer must internalize the storage hierarchy. At the top sits DRAM: nanosecond access, gigabytes of capacity, volatile. Below sits NVMe SSD: microsecond access, terabytes of capacity, persistent. Further down sits spinning HDD: millisecond access (dominated by a 5–10 ms mechanical seek), terabytes of capacity, persistent but sequential-friendly.

The key insight is that every layer of this hierarchy moves data in fixed-size chunks, not individual bytes. A CPU cache line is 64 bytes. An OS memory page is 4 KB. A database page (also called a block) is typically 8 KB (Postgres) or 16 KB (InnoDB), though configurable. When the database wants a single row, it must read the entire page containing that row into the buffer pool.

This chunked access has profound consequences:

1. Sequential access is vastly cheaper than random access. On an HDD, reading 1 MB sequentially takes ~1 ms; reading 1 MB in 128 random 8-KB seeks takes ~640 ms — a 640× difference. Even on NVMe, random reads burn IOPS budget faster than sequential reads.

2. The page is the unit of I/O, buffering, locking, and logging. Every abstraction above — buffer pool, B+ tree, WAL — thinks in pages, not rows.

3. Locality matters. Rows that are accessed together should live on the same page. This is the physical argument for clustered indexes.

A heap file is the simplest page-based storage: an unsorted collection of pages, each containing a sequence of variable-length slots (one per row). Each row is identified by its Record ID (RID) = (page_id, slot_number). The heap file is simple to write to (append) but requires a full scan to find a specific row.

# Conceptual page layout (simplified)
# Each database page = 8192 bytes

PAGE_SIZE = 8192

class Page:
    def __init__(self, page_id: int):
        self.page_id = page_id
        self.header = PageHeader()   # free space pointer, slot count, LSN
        self.slots: list[Row] = []   # variable-length records
        self.free_space = PAGE_SIZE - sizeof(PageHeader)

    def insert(self, row: Row) -> (int, int):  # returns (page_id, slot)
        if row.size > self.free_space:
            raise PageFull
        slot = len(self.slots)
        self.slots.append(row)
        self.free_space -= row.size
        return (self.page_id, slot)  # this is the Record ID

# Record ID: the physical address of a row
RID = namedtuple('RID', ['page_id', 'slot'])

The buffer pool is the database's own memory manager: a large region of RAM (often 70–80% of available memory) divided into fixed-size frames, each holding one disk page. When a query needs page P, the database first checks whether P is already in a buffer pool frame (a buffer pool hit); if not, it loads P from disk into a free frame (a buffer pool miss, triggering I/O).

The buffer pool manager maintains:

• A page table: a hash map from page_id to frame_id (and metadata: dirty bit, pin count).
• A replacement policy: when all frames are occupied and a new page must be loaded, which frame gets evicted?
• Pin counts: a frame with pin_count > 0 is being actively accessed and must not be evicted.
• Dirty bits: a frame modified in memory but not yet written back to disk is "dirty" and must be flushed before eviction (or lazily by a background writer).

LRU (Least Recently Used) is the classic replacement policy — evict the frame not used for the longest time. It works well for most workloads. But databases often know something the OS does not: if a query is doing a sequential scan of a large table, those pages will never be needed again. Pure LRU would evict the useful cached pages to make room for scan pages that are immediately discarded. Real systems use LRU-K, clock replacement, or scan-resistant policies (Postgres uses a "clock sweep").

The hit ratio — fraction of page requests served from memory — is the single most important metric for buffer pool health. A hit ratio of 99% means only 1 in 100 page requests goes to disk. Since disk is 1000× slower than DRAM, going from 99% to 99.9% hit ratio can halve total I/O time.

This is why database sizing advice says: "give Postgres as much RAM as you can afford." The buffer pool is the most leverage you have.

// Simplified buffer pool (C-style pseudocode)

#define POOL_FRAMES 10000  // e.g. 80 GB / 8 KB = 10M frames

typedef struct Frame {
    PageID  page_id;    // which disk page is here
    byte    data[PAGE_SIZE];
    int     pin_count;  // active users of this frame
    bool    dirty;      // modified but not written back
} Frame;

Frame pool[POOL_FRAMES];
HashMap page_table;  // page_id -> frame_index

Frame* pin_page(PageID pid) {
    if (page_table.contains(pid)) {
        Frame* f = &pool[page_table[pid]];
        f->pin_count++;
        return f;  // buffer pool HIT
    }
    // MISS: find a victim frame
    Frame* victim = choose_victim_lru();  // must have pin_count == 0
    if (victim->dirty)
        write_to_disk(victim);   // flush before eviction
    read_from_disk(pid, victim);
    page_table.remove(victim->page_id);
    victim->page_id = pid;
    victim->pin_count = 1;
    victim->dirty = false;
    page_table[pid] = frame_index(victim);
    return victim;
}

void unpin_page(PageID pid, bool modified) {
    Frame* f = &pool[page_table[pid]];
    if (modified) f->dirty = true;
    f->pin_count--;
}

The most consequential architectural decision in database storage is how you lay out rows on disk: do all fields of one row live contiguously, or do all values of one column live contiguously?

Row store (NSM — N-ary Storage Model): Each page holds complete tuples. The record for employee (id=42, name='Alice', dept='Eng', salary=120000) is stored as a single contiguous byte sequence. This is the layout of Postgres, MySQL/InnoDB, Oracle, and SQL Server.

Row store wins when: you need the full row (OLTP — an app fetching a user profile, updating an order). Each tuple read is a single I/O; writes and updates touch one location.

Column store (DSM — Decomposition Storage Model): Each column is stored as its own array, potentially in a separate file or segment. All salary values live together; all name values live together. This is the layout of DuckDB, Snowflake, BigQuery, Redshift, Vertica, and ClickHouse.

Column store wins when: you need to aggregate one or a few columns across many rows (OLAP — "what is the average salary by department across 100 million employees?"). You only read the salary and dept columns from disk, skipping id and name entirely. This is called projection pushdown to storage.

Column stores also compress dramatically better. A column of 100 million salary integers has much lower entropy than interleaved tuples — run-length encoding, dictionary encoding, and delta encoding all exploit the homogeneity. BigQuery routinely achieves 10× compression on analytical columns.

The reconstruction problem: Column stores must reassemble rows when needed. Modern implementations use late materialization — keep data in columnar form through all filter and aggregation operators, and only reconstruct full rows at the last moment (or not at all, if the query never needs the full row).

PAX (Partition Attributes Across): A hybrid: pages are split into mini-pages, one per column, so all values of a column within one page are contiguous. This preserves the write locality of row stores (one page for the whole row group) while enabling SIMD vectorized scans within a page.

-- The difference made concrete:

-- OLTP query (row store wins: fetch 1 full row)
SELECT * FROM employees WHERE id = 42;
-- Hits a B+ tree index -> 1 page read -> done.
-- Column store would need to read from 4 separate column segments.

-- OLAP query (column store wins: scan 1 column, 100M rows)
SELECT dept, AVG(salary)
FROM employees
GROUP BY dept;
-- Row store: reads ALL columns even though only 2 are used.
--   100M rows × 100 bytes/row = 10 GB of I/O.
-- Column store: reads ONLY salary (400 MB) + dept (maybe 200 MB compressed).
--   10-25x less I/O before a query even starts.

The B+ tree is the most important data structure in database systems. It is a balanced search tree designed specifically for the page-based I/O model. Every professional database (Postgres, MySQL, Oracle, SQL Server, SQLite) uses a B+ tree as its primary index structure.

Why not a binary search tree? A BST with N nodes has height O(log₂ N). For N = 1 billion, that is ~30 levels. If each node is on a different disk page, that is 30 I/Os per lookup — unusable. The B+ tree solves this by making each node very wide: a page-sized node with fan-out d (hundreds of keys per node). Height becomes O(log_d N). For d = 200 and N = 1 billion: height = log₂₀₀(10⁹) ≈ 3.7, so 4 levels. Only 3–4 disk I/Os per lookup, regardless of table size. This is the central magic.

Structure:

• Internal nodes store only keys (search values) and pointers to child pages. They never store actual record data.
• Leaf nodes store the actual (key, record_pointer) pairs — the record pointer is either the full row (clustered index) or a Record ID pointing into the heap (secondary index).
• Leaf nodes are linked in a doubly-linked list, enabling efficient range scans: find the first key with a tree traversal, then walk the leaf chain without returning to internal nodes.

Order (d) invariant: Every node except the root has between ⌈d/2⌉ and d keys. The root has between 1 and d keys. This guarantees at least 50% utilization and bounds height.

Why B+ vs B tree? In a B-tree, internal nodes also store records, which wastes internal node space (fewer keys → lower fan-out → more levels). The B+ tree keeps internal nodes lean (keys only), maximizing fan-out and compressing tree height. The linked leaf list makes range scans O(1) additional overhead after the first lookup.

# B+ tree node structure
# Assume ORDER = 3 (each node holds 2–6 keys in practice;
# real systems use 100–500)

ORDER = 3  # max keys per node

class BPlusNode:
    def __init__(self, is_leaf=False):
        self.is_leaf = is_leaf
        self.keys = []          # sorted list of search keys
        # Internal node: len(children) == len(keys) + 1
        self.children = []      # pointers to child nodes (internal)
        # Leaf node:
        self.records = []       # (key -> RID) pairs
        self.next_leaf = None   # linked list pointer

# Search: O(log_d N) disk I/Os
def search(node: BPlusNode, key) -> RID | None:
    if node.is_leaf:
        for k, rid in zip(node.keys, node.records):
            if k == key:
                return rid
        return None
    # Binary search for correct child pointer
    i = bisect_left(node.keys, key)
    return search(node.children[i], key)

# Range scan: walk leaf chain after initial lookup
def range_scan(root, low, high):
    # 1. Find leftmost leaf containing low
    leaf = find_leaf(root, low)
    results = []
    while leaf is not None:
        for k, rid in zip(leaf.keys, leaf.records):
            if k > high: return results
            if k >= low: results.append(rid)
        leaf = leaf.next_leaf
    return results

The B+ tree's self-balancing property is maintained through splits on insertion and merges/redistributions on deletion. Understanding these operations is essential for reasoning about write amplification and index maintenance costs.

Insertion algorithm:

1. Search for the correct leaf node L (O(log_d N) I/Os).
2. If L has room (< d keys), insert and done — best case, 1 page write.
3. If L is full (d keys), split L into two leaves L and L'. The median key goes up to the parent as a separator. This may cascade: if the parent is also full, it splits too, all the way up to the root.
4. If the root splits, a new root is created (the only way tree height increases).

Deletion algorithm:

1. Find the leaf, remove the key.
2. If the leaf still has ≥ ⌈d/2⌉ keys, done.
3. If underflowing: try to redistribute from a sibling (borrow a key). If redistribution is not possible (sibling also at minimum), merge with the sibling and pull down the separator key from the parent. This can cascade up.
4. If the root ends up with 0 keys, it is deleted and the tree shrinks by one level.

Write amplification in practice: A single-row INSERT into a full leaf page causes: the leaf to split (2 page writes), the parent to update (1 write), potentially cascading. In the worst case, every level splits: O(log_d N) pages written for one row insert. In practice, splits are rare because pages are not always full — databases pre-leave some free space (fill factor). Postgres's default fill factor for B+ tree leaves is 90%.

The critical implementation detail: Splitting must be atomic with respect to crashes. Real databases use a Write-Ahead Log (WAL): before modifying any pages, write a log record describing the change. If a crash occurs mid-split, the WAL allows recovery to either complete or undo the operation. This is why B+ tree maintenance is intertwined with transaction logging.

# Leaf split (the core structural operation)
def split_leaf(parent: BPlusNode, leaf: BPlusNode, idx_in_parent: int):
    """
    Split a full leaf into two. Push middle key up to parent.
    idx_in_parent: position of 'leaf' in parent.children
    """
    mid = len(leaf.keys) // 2

    new_leaf = BPlusNode(is_leaf=True)
    new_leaf.keys    = leaf.keys[mid:]     # right half
    new_leaf.records = leaf.records[mid:]
    new_leaf.next_leaf = leaf.next_leaf    # maintain linked list

    leaf.keys    = leaf.keys[:mid]         # left half
    leaf.records = leaf.records[:mid]
    leaf.next_leaf = new_leaf

    # Push separator (first key of new_leaf) up to parent
    push_up_key = new_leaf.keys[0]
    parent.keys.insert(idx_in_parent, push_up_key)
    parent.children.insert(idx_in_parent + 1, new_leaf)

    # If parent is now full, caller will split parent too
    # (recursion up the tree — can hit root, creating new root)

# Internal node split (same idea, but median key is pushed up, not copied)
def split_internal(parent, node, idx_in_parent):
    mid = len(node.keys) // 2
    push_up_key = node.keys[mid]  # KEY DIFFERENCE: middle key goes UP, not copied

    new_node = BPlusNode(is_leaf=False)
    new_node.keys     = node.keys[mid+1:]
    new_node.children = node.children[mid+1:]

    node.keys     = node.keys[:mid]
    node.children = node.children[:mid+1]

    parent.keys.insert(idx_in_parent, push_up_key)
    parent.children.insert(idx_in_parent + 1, new_node)

A hash index trades the B+ tree's ordered structure for constant-time exact-match lookups. The idea is simple: apply a hash function to the search key to get a bucket number, then look in that bucket for the matching record.

Static hashing: Pre-allocate B buckets. To find key k, read bucket h(k) mod B. Problem: if the table grows, many keys collide into the same bucket (overflow pages degrade to a linked list scan) or you must rehash the entire file — an O(N) operation.

Extendible hashing: The elegant dynamic solution. Maintain a directory of 2^d pointers (d = global depth). Each bucket has a local depth ℓ ≤ d. When a bucket overflows:

1. Split the bucket into two.
2. If ℓ < d: update the directory pointers that map to this bucket. Only two pointers change. No other buckets are affected.
3. If ℓ = d: double the directory (2d → 2d+1) — cheap since the directory itself is small — then split.

No full rehash ever occurs. The directory doubles, not the data.

Linear hashing: Another dynamic scheme that grows the number of buckets one at a time using a "split pointer" that advances through buckets. Avoids doubling the directory at the cost of slightly more complex lookup.

When does a hash index beat a B+ tree?

• Equality predicates only: WHERE id = 42. Hash is O(1) vs O(log N).
• Very high-selectivity lookups where the constant factor of the hash matters.

When does a hash index lose badly?

• Range queries: WHERE salary BETWEEN 50000 AND 80000. Hash destroys order; you must scan all buckets — O(N).
• ORDER BY, GROUP BY, min/max queries: all require the ordered structure of a B+ tree.
• Postgres's hash indexes are now crash-safe (fixed in Postgres 10) but still rarely used because B+ trees handle ranges too.

The real-world lesson: In OLTP databases, hash indexes are a niche optimization. In-memory hash tables (like Postgres's hash joins) are ubiquitous, but on-disk hash indexes are comparatively rare. B+ trees win in practice because most query workloads mix equality and range predicates.

# Extendible hashing — the elegant dynamic hash index

class Bucket:
    def __init__(self, local_depth: int):
        self.local_depth = local_depth
        self.records: dict = {}   # key -> RID
        self.capacity = 4         # simplified: 4 records per bucket

class ExtendibleHashIndex:
    def __init__(self):
        self.global_depth = 1
        # Directory: 2^1 = 2 slots, both pointing to the same bucket initially
        b = Bucket(local_depth=1)
        self.directory = [b, b]   # both entries share one bucket

    def _bucket_for(self, key) -> int:
        mask = (1 << self.global_depth) - 1
        return hash(key) & mask

    def lookup(self, key):
        return self.directory[self._bucket_for(key)].records.get(key)

    def insert(self, key, rid):
        idx = self._bucket_for(key)
        bucket = self.directory[idx]
        if len(bucket.records) < bucket.capacity:
            bucket.records[key] = rid
            return
        # Bucket full: split
        if bucket.local_depth == self.global_depth:
            # Double the directory
            self.directory = self.directory * 2
            self.global_depth += 1
        self._split_bucket(idx)
        self.insert(key, rid)   # retry after split

    def _split_bucket(self, idx):
        old = self.directory[idx]
        new_b = Bucket(old.local_depth + 1)
        old.local_depth += 1
        # Re-hash all old entries between old and new bucket
        old_records = old.records.copy()
        old.records.clear()
        for k, v in old_records.items():
            target_idx = hash(k) & ((1 << self.global_depth) - 1)
            self.directory[target_idx].records[k] = v
        # Update directory pointers
        for i, b in enumerate(self.directory):
            if b is old:
                if (i >> (old.local_depth - 1)) & 1:
                    self.directory[i] = new_b

One of the most practically important distinctions in indexing is whether the index determines the physical order of the data (clustered) or merely provides a lookup path into a separately-stored heap (secondary/unclustered).

Clustered index (also called primary index or index-organized table): The leaf pages of the B+ tree are the data pages. The rows are physically stored in key order. InnoDB (MySQL) always stores tables as clustered B+ trees on the primary key. In SQL Server, a "clustered index" does the same.

Consequences:

• Range scans on the clustered key are maximally efficient: sequential I/O through the leaf level of the tree.
• There can be only one clustered index per table — you can only sort the rows one way.
• Inserts of out-of-order keys (e.g., random UUIDs as primary key in InnoDB) cause many page splits — a known anti-pattern.
• Postgres does NOT have clustered indexes in the InnoDB sense: tables are heap files. CLUSTER tablename USING indexname physically reorders the heap once, but it is not maintained on future writes.

Secondary (unclustered) index: The leaf pages of the index B+ tree store (key, RID) pairs, where RID is the page_id + slot of the row in the heap. A lookup traverses the index tree to find the RID, then fetches the heap page.

The double I/O problem (Index Scan vs Heap Fetch):

Index leaf page → RID → Heap page containing the row

This is 2 I/Os for one row. For a range scan returning K rows scattered across the heap, it can degrade to K random I/Os into the heap — potentially worse than a sequential heap scan.

Index-Only Scans: If all columns needed by the query are in the index (either as keys or as "included columns"), the heap fetch can be skipped entirely. Postgres calls these "Index Only Scans" and they can be dramatically faster. This is why CREATE INDEX ... INCLUDE (col1, col2, ...) exists in Postgres 11+.

The rule of thumb for unclustered index scan performance: An unclustered index is efficient when the query selects a small fraction of rows (< ~5–10%). Above that threshold, the random I/O overhead of heap fetches exceeds the cost of a sequential scan. The query optimizer must estimate this fraction and choose accordingly.

-- Clustered (InnoDB PRIMARY KEY): rows stored IN key order
CREATE TABLE orders (
    order_id   INT         PRIMARY KEY,   -- clustered on this
    customer_id INT,
    total      DECIMAL(10,2),
    created_at DATETIME
);
-- Range scan: highly efficient, sequential leaf pages
SELECT * FROM orders WHERE order_id BETWEEN 1000 AND 2000;

-- Secondary index: separate B+ tree, leaf -> heap RID
CREATE INDEX idx_orders_customer ON orders(customer_id);
-- Lookup: traverse index tree -> get RID -> fetch heap page
SELECT * FROM orders WHERE customer_id = 42;

-- Index-Only Scan: avoid heap fetch entirely
CREATE INDEX idx_orders_cust_total
    ON orders(customer_id)
    INCLUDE (total);          -- Postgres 11+ syntax
-- Now this query never touches the heap:
SELECT customer_id, SUM(total)
FROM orders
GROUP BY customer_id;

-- EXPLAIN in Postgres reveals the access path:
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;
-- Look for: "Index Scan" vs "Index Only Scan" vs "Seq Scan"

A composite index is a B+ tree built on a tuple of columns (col1, col2, ..., colN). The keys are sorted lexicographically: first by col1, then by col2 for equal col1 values, and so on. This seemingly simple extension has non-obvious and powerful consequences.

The left-prefix rule: A composite index on (a, b, c) can answer queries filtering on (a), (a, b), or (a, b, c) using the index efficiently. It cannot efficiently answer a query filtering only on (b) or (c), because those values are scattered across all leaf pages (the index is only sorted by a first). This is the most commonly misunderstood indexing rule.

Index selectivity: The leading column should be the most selective (highest cardinality) in equality-filter queries. For range queries on the last column, composite indexes shine: WHERE a = 'x' AND b BETWEEN 10 AND 20 uses the index to narrow to all rows with a='x', then scans the sub-range by b.

Covering index: An index that contains all columns referenced by a query (in filters, projections, joins, or order-bys). The query is answered entirely from the index without touching the heap. The classic example:

-- Query: find recent orders for a customer
SELECT order_id, total FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 10;

-- Covering index:
CREATE INDEX idx ON orders(customer_id, created_at DESC, order_id, total);
-- (customer_id, created_at) -> seek + range scan in the index
-- order_id, total -> included so no heap fetch

Multi-column statistics: The query optimizer must estimate the selectivity of composite predicates. Without multi-column statistics, it assumes independence: P(a AND b) ≈ P(a) × P(b). This under- or over-estimates for correlated columns (e.g., city and zip code). Postgres 10+ supports CREATE STATISTICS to teach the optimizer about column correlations.

-- LEFT PREFIX RULE demonstration
CREATE INDEX idx_abc ON t(a, b, c);

-- Uses index efficiently (left prefix a)
SELECT * FROM t WHERE a = 1;

-- Uses index efficiently (left prefixes a, b)
SELECT * FROM t WHERE a = 1 AND b = 2;

-- Uses index efficiently (range on last col after equalities)
SELECT * FROM t WHERE a = 1 AND b = 2 AND c > 5;

-- Does NOT efficiently use this index (no a filter)
SELECT * FROM t WHERE b = 2;
-- Postgres will likely choose a Seq Scan here
-- Solution: create a separate index on (b) or (b, c)

-- ORDER BY optimization: if ORDER BY matches index order,
-- no sort step needed
SELECT * FROM t WHERE a = 1 ORDER BY b, c;
-- Uses idx_abc: already in correct order within a=1 range

An index is not free. Every index you add:

1. Costs storage (a B+ tree on a large table is 10–30% of the table size).
2. Slows down writes: every INSERT/UPDATE/DELETE must update every index defined on the table.
3. Can confuse the optimizer into choosing a worse plan if statistics are stale.

Index when:

• Columns used in WHERE clauses with high selectivity (filters out most rows).
• Columns used in JOIN conditions (especially foreign keys).
• Columns used in ORDER BY or GROUP BY when the result set is large.
• Columns that appear in range queries on large tables.
• You need an index-only scan for a hot analytical query.

Do not index when:

• The table is tiny (full scan is faster than any index overhead).
• The column has very low cardinality (e.g., a boolean flag, status IN ('active','inactive')). An index on a boolean selects ~50% of rows — the random I/O heap fetches would be catastrophic. (Exception: partial indexes can help here.)
• The table is a write-heavy append log with infrequent reads.
• You are indexing every column "just in case" — this is a common and expensive mistake.

Partial indexes: Index only a subset of rows matching a predicate. This is one of the most under-utilized Postgres features:

-- Only index active users — ignores the 95% who are inactive
CREATE INDEX idx_active_users ON users(email)
    WHERE status = 'active';

This index is smaller, faster to build, and trivially eliminates the low-cardinality problem.

The index decision process:

1. Profile first. Look at pg_stat_user_indexes for unused indexes and pg_stat_statements for slow queries.
2. Use EXPLAIN (ANALYZE, BUFFERS) to see what the optimizer actually does.
3. For a slow query, hypothesize the needed index, create it, check if the optimizer uses it.
4. Monitor write throughput after adding — if your write-heavy service slows down, an index is the likely culprit.

-- Practical indexing workflow in Postgres

-- 1. Find slow queries
SELECT query, calls, mean_exec_time, total_exec_time
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 10;

-- 2. Find unused indexes (wasting write overhead)
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0  -- never been used!
ORDER BY pg_relation_size(indexrelid) DESC;

-- 3. Examine a slow query plan
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT * FROM orders
WHERE customer_id = 42 AND status = 'pending'
ORDER BY created_at DESC;

-- 4. Create index CONCURRENTLY (no table lock in production)
CREATE INDEX CONCURRENTLY idx_orders_cust_status
    ON orders(customer_id, status, created_at DESC)
    WHERE status = 'pending';  -- partial index bonus

-- 5. Re-run EXPLAIN to confirm index is used
-- Look for: "Index Scan using idx_orders_cust_status"