Database Indexing

An index is a separate data structure that maps column values to the location of the rows containing them, so the database can find rows without scanning the whole table. Without an index, a query with a WHERE clause reads every row (a full table scan, O(n)). With a suitable index, it reads only the matching entries, typically in O(log n).

B-tree and B+tree indexes

The default index type in most relational databases is a B+tree, a balanced tree designed for data stored in fixed-size pages (commonly 4 to 16 KB) on disk.

• Internal nodes hold sorted keys and pointers to child pages. They guide the search.
• Leaf nodes hold the keys and either the rows or pointers to them. Leaves are linked in key order, so range scans follow the links.
• The tree stays balanced: all leaves are at the same depth.
• Each page holds hundreds of keys, so the tree is shallow. An index over hundreds of millions of rows commonly has 3 to 4 levels, so a lookup takes a few page reads, with the upper levels usually cached in memory.

graph TB
    R["root: 30 | 60"] -->|"keys below 30"| A["20"]
    R -->|"keys 30 to 59"| B["50"]
    R -->|"keys 60 and above"| C["80"]
    A --> L1["leaf: 5 10 15"]
    A --> L2["leaf: 20 25"]
    B --> L3["leaf: 30 40 45"]
    B --> L4["leaf: 50 55"]
    C --> L5["leaf: 60 70 75"]
    C --> L6["leaf: 80 90"]
    L1 -.->|"next leaf"| L2 -.-> L3 -.-> L4 -.-> L5 -.-> L6

For example, a lookup of key 45 compares against the root keys (30 <= 45 < 60), follows the middle pointer to the node with separator 50 (45 < 50), follows its left pointer to the leaf 30 40 45, and finds the key there. A range query for 20 to 50 finds the leaf containing 20, then follows the next-leaf links until a key above 50 appears.

The height is set by the fan-out, the number of children per node. With an 8 KB page and roughly 25 bytes per key and pointer, a node holds on the order of 300 entries. Three levels then address about 300^3 = 27 million entries and four levels about 300^4 = 8 billion. Real pages are not completely full, so actual fan-out is lower, but the depth stays in the single digits.

Supported operations:

Inserts that overflow a page split it into two and add a key to the parent. Splits can propagate upward. The storage engine trade-offs are covered in storage engines: B-tree vs LSM-tree.

Clustered and secondary indexes

• A clustered index determines the physical order of the table: the leaf pages of the index are the table rows. There can be only one per table. In MySQL InnoDB, the table is always stored as a clustered index on the primary key. SQL Server allows choosing the clustered index.
• A secondary (non-clustered) index is a separate structure whose leaves store the indexed columns plus a row locator.
  • In InnoDB, the locator is the primary key value. A secondary index lookup then does a second lookup in the clustered index.
  • In PostgreSQL, tables are heaps, and the locator is a tuple identifier (page and offset) into the heap.

Consequences:

• Range queries on the clustered key read contiguous pages.
• A secondary index lookup that returns many rows performs many random reads into the table, which can be slower than a sequential scan.
• In InnoDB, a long or random primary key (such as a random UUID) enlarges every secondary index and causes page splits across the tree. Sequential keys append to the right edge.

Composite indexes

A composite (multi-column) index sorts entries by the first column, then the second within equal first values, and so on.

An index on (country, city, created_at) serves:

• WHERE country = 'DE'
• WHERE country = 'DE' AND city = 'Berlin'
• WHERE country = 'DE' AND city = 'Berlin' AND created_at > ...
• WHERE country = 'DE' ORDER BY city

It does not efficiently serve WHERE city = 'Berlin' alone, because entries for one city are scattered across countries. This is the leftmost prefix rule.

Column order guidelines:

1. Equality-tested columns first, then the range or sort column last. Once a column has a range predicate, entries are no longer ordered by the columns after it within the scanned range, so those columns cannot narrow the scan or provide ordering.
2. Among equality columns, order also depends on which query prefixes must be supported.

Covering indexes

A query is covered when an index contains every column the query needs, so the database answers from the index without visiting the table (an index-only scan).

CREATE INDEX idx_orders_user ON orders (user_id, created_at) INCLUDE (total);
-- SELECT created_at, total FROM orders WHERE user_id = 7
-- can be answered from the index alone

INCLUDE (PostgreSQL, SQL Server) adds payload columns to leaves without making them part of the sort key. In InnoDB, secondary indexes implicitly include the primary key, so queries needing only indexed columns and the primary key are covered. PostgreSQL index-only scans also depend on the visibility map showing that pages are all-visible, which vacuum maintains.

Other index types

A hash index gives O(1) average equality lookup but cannot serve <, >, ORDER BY, or prefix matches, so B+trees are the general default. In-memory stores use hash tables as their primary structure.

Cost of indexes

Indexes speed up reads and slow down writes.

• Every insert and delete updates every index on the table. An update of an indexed column updates that index.
• Indexes use disk and memory. A table with many indexes can have index size exceeding table size.
• More indexes give the planner more plans to consider and give maintenance (vacuum, rebuild) more work.
• Low-selectivity indexes (a boolean column) rarely help: the planner prefers a scan when a large fraction of rows match.

Add indexes for queries that are frequent or latency-critical. Remove unused ones. Write-heavy tables warrant fewer indexes.

Query planner basics

The query planner (optimizer) generates candidate execution plans and picks the one with the lowest estimated cost. It relies on statistics: row counts, distinct value counts, and value histograms per column.

flowchart LR
    Q["SQL query"] --> P["Parser"]
    P --> O["Planner: estimate cost of candidate plans using statistics"]
    O --> E["Executor: run chosen plan"]
    S[("Table statistics")] --> O

Choices the planner makes:

• Access path: sequential scan, index scan, index-only scan, bitmap scan. A bitmap scan (PostgreSQL) first collects the matching row locations from the index, sorts them by page, then reads the table pages in order, which suits predicates that match a moderate fraction of rows.
• Join algorithm: nested loop (good with an index on the inner side and few outer rows), hash join (build a hash table on the smaller input), merge join (both inputs sorted).
• Join order: the sequence in which tables are combined.

Use EXPLAIN (and EXPLAIN ANALYZE, which executes the query and reports actual rows and timings) to see the plan. Common causes of an unused index: stale statistics, a function applied to the column, a type mismatch forcing a cast, a leading wildcard, a non-leftmost prefix, or a predicate matching a large fraction of the table.

Interview questions

• Why are B+trees preferred over binary trees for database indexes? Nodes are sized to a disk page and hold hundreds of keys, so the tree is only a few levels deep and each level costs one page read. A binary tree would need many more levels and page reads.
• What is the leftmost prefix rule? A composite index can be used for predicates on its first column, or first several columns in order. It cannot be used efficiently for predicates that skip the first column.
• Why can an index scan be slower than a full scan? For a non-selective predicate, an index scan performs random row lookups for a large number of matches, whereas a sequential scan reads pages in order. The planner estimates this and may choose the scan.
• What is a covering index and what is its cost? An index containing all columns a query needs, avoiding table access. It is larger and adds write cost for each included column.
• Why avoid random UUIDs as an InnoDB primary key? Inserts land at random positions in the clustered index, causing page splits and poor cache locality, and the key is copied into every secondary index.