Indexing

B-tree internals, clustered vs non-clustered, and the cost every index adds to writes

Why

Indexes are the primary performance lever available to engineers without changing application code. A missing index on a join column turns a millisecond lookup into a full table scan. But every index slows down writes — INSERT, UPDATE, DELETE must update every index on the table. Understanding B-tree internals explains both why indexes help reads and why they have write costs.

Intuition

A B-tree index is a self-balancing sorted tree. Internal nodes store key ranges that guide traversal; leaf nodes store the actual keys and pointers to rows. Finding a value is O(log n) — typically 3–4 page reads even for tables with millions of rows (tree height stays shallow). A full table scan is O(n) pages — potentially thousands of reads.

A clustered index physically orders the table's rows by the index key — the leaf nodes ARE the rows. Every table can have only one. A non-clustered index stores key + pointer to the actual row; following the pointer is an extra random read.

Explanation

B-tree structure

B-tree index on employees(salary): Root node: [50k | 100k | 150k] / | \ Internal: [30k|40k] [80k|90k] [120k|140k] | | | Leaf nodes: [rows] [rows] [rows] → linked list across leaves Key properties: - All paths from root to leaf are the same length (balanced) - Leaf nodes form a linked list — efficient for range scans - Tree height ≈ log_b(n): b=100 fanout, 1M rows → ~3 levels - Each level = 1 page read → 3 page reads to find any row

Clustered vs non-clustered index

Clustered index

Table rows stored in index key order. Leaf nodes contain actual row data. One per table (it IS the table). In MySQL InnoDB, the primary key is always the clustered index. Range scans on the PK are extremely fast — data is already sorted.

Non-clustered index

Separate structure with key + row pointer (heap pointer or clustered key). Extra lookup step to fetch the actual row — "key lookup" or "RID lookup". A covering index avoids this by including all needed columns in the index itself.

-- Covering index: query answered entirely from the index CREATE INDEX idx_cov ON orders(customer_id) INCLUDE (amount, status); -- SELECT amount, status WHERE customer_id = 42 -- → Index Only Scan, no table touch -- Index selectivity matters: boolean column (2 values) → index rarely used -- High-cardinality columns (email, user_id) → index very effective

← Previous Next →