Indexing and Database Motivation

The (Key, Value) Store Abstraction

Databases store records indexed by key. The core operation: given a key, find the associated record (or records). In the Cambridge course, we treat the index as an abstract data type holding a collection of (key, value) pairs, ordered by key. Values are typically small (e.g. pointers to records in memory or on disk).

Abstract operations on an index:

• search(k): return a cursor to the (key, value) pair with key k, or indicate absence.
• search_gt(k): return a cursor to the first pair with key > k (range query start).
• next(c), prev(c): move the cursor forward or backward in key order.
• insert(k, v), delete(k): modify the index contents.

Point queries (lookup by exact key) and range queries (keys in [a, b]) are the two fundamental search patterns. Sensible database indices allow multiple items with the same key; the course assumes unique keys for consistency with CLRS.

Why Indexing Matters

Without an index, answering a query like SELECT * FROM movies WHERE year > 2015 requires scanning every row of the table (linear time in the number of rows). With an index on year, the database can seek directly to the first matching entry and scan forward, touching only the relevant records.

The speed-up is dramatic: a linear scan of a billion-row table can take minutes; an indexed range query examines only the matching rows plus a logarithmic number of index nodes.

Primary vs Secondary Indices

A primary index determines the physical ordering of data on disk. The data records themselves are organised in key order (e.g. a B-tree clustered index in InnoDB). There is exactly one primary index per table.

A secondary index is a separate data structure that maps keys to record pointers (or primary key values). A table can have many secondary indices. A lookup via a secondary index requires two steps: search the secondary index to find the record pointer, then fetch the actual record.

Updates (insert, delete) must maintain all indices, so indices speed up reads but slow down writes. Read-heavy workloads benefit most from indexing.

The Disk Access Model

Database indices are typically stored on disk (SSD or HDD), not in main memory. The cost model changes fundamentally:

• Follow a pointer to a node stored on disk: ~2,000,000 CPU cycles.
• CPU operations (comparisons, arithmetic): ~1 cycle each.

The dominant cost is disk I/O: the number of disk pages read or written. An SSD consists of blocks made of pages; reads and writes operate on entire pages (e.g. 4 KB) at a time.

Nodes of the search tree should therefore be sized to fit within one disk page. A node containing many keys and child pointers means fewer levels, and thus fewer disk accesses, to reach any given key.

Why Multi-Way Search Trees?

A balanced binary search tree stores one key per node and has height ~log₂(n). With 10⁹ records, that is roughly 30 levels, requiring up to 30 disk seeks per lookup.

A B-tree with branching factor 100 (i.e. each node holds roughly 100 keys) has height ~log₁₀₀(n). With 10⁹ records, that is roughly 5 levels, requiring only 5 disk seeks per lookup. The motivation for B-trees is directly about minimising disk I/O.

Summary

Concept	Description
Index ADT	Collection of (key, value) pairs, ordered by key
Primary index	Determines physical data ordering
Secondary index	Separate structure pointing to data
Point query	Lookup by exact key
Range query	Keys in [a, b]
Disk access cost	~2M CPU cycles per seek
B-tree motivation	Minimise tree height to reduce disk I/O
Node size	Designed to fit one disk page