Introduction to Indexing

An index is an auxiliary data structure, stored alongside a data file, that supports efficient lookup of records by the value of one or more fields. The field or combination of fields used for lookup is called the search key. Crucially, a search key is not necessarily a candidate key of the relation — you can index on `age` even though many customers share the same age, and you can index on `customer_id` because it happens to be unique. The index does not care about uniqueness; it only cares about being queried on that value. What the index physically stores for each distinct search-key value is called a data entry. There are three classical choices for what a data entry can be, all of which appear across real systems: 1. The actual record itself, keyed and physically stored in search-key order (this is really the data file organized as an index — no separate structure). 2. A pair `(search-key value, record ID)`, where the record ID (RID) is a pointer to the record's location in a separate data file (e.g., page number + slot number). 3. A pair `(search-key value, list of record IDs)`, used when many records share the same key value, avoiding repeating the key for every match. This distinction feeds directly into dense vs. sparse indexes, a topic covered separately, but the essential idea to internalize now is: an index entry is not the record — it is a lightweight proxy that tells you where the record lives. The second foundational distinction is between primary and secondary indexes, based on the relationship between the index's search key and the physical ordering of the underlying data file:

• A primary index (sometimes called a clustering index in some textbooks, though that term is used more precisely later) is built on a field that determines, or matches, the physical sort order of the data file. If the heap file's records are sorted by `customer_id`, an index on `customer_id` is primary. There is at most one primary index per file, because a file can only be physically sorted one way at a time.
• A secondary index is built on any field that does not match the file's physical ordering — for instance, an index on `last_name` when the file is physically sorted by `customer_id`. A file can have arbitrarily many secondary indexes, one for every field or field combination queries commonly filter on.

This primary/secondary distinction is the seed of the later, more refined distinction between clustered and unclustered indexes, and understanding it now — in terms of physical file order — makes that later material almost automatic.

The mechanism is simplest to understand by contrasting two paths for the same query: "find all records with search key = k."

Without an index (scanning a heap file): the system must read every page of the file and check every record's key, because records are stored in no particular order relevant to the query.

With an index: the system first searches the (much smaller) index structure for k, obtains the data entries — record IDs — for matching records, and then does a small number of targeted reads into the data file to fetch the actual records. The index search itself is fast because indexes are built as compact, ordered, or hashed structures (arrays, trees, or hash tables) specifically optimized for lookup, not for holding full records. The general algorithm for an index-assisted equality lookup: ``` function INDEX_LOOKUP(index, key):

# Step 1: locate the position of `key` inside the index structure.

# For a sorted array index this is a binary search;

# for a tree index this is a root-to-leaf traversal;

# for a hash index this is a hash-bucket computation. position = index.locate(key) if position is NOT_FOUND: return [] # no matching records entries = index.dataEntriesAt(position) results = [] for entry in entries: if entry.isFullRecord(): results.append(entry) # Alternative 1 index else: record = dataFile.fetch(entry.rid) # Alternative 2 index results.append(record)

# entry may itself be a list of RIDs (Alternative 3);

# in that case, fetch every RID in the list return results

function RANGE_LOOKUP(index, lowKey, highKey):

# Only efficient on ORDERED indexes (sorted arrays, B+-trees), not hash indexes position = index.locateFirstGreaterOrEqual(lowKey) results = [] while position is valid and index.keyAt(position) <= highKey: for entry in index.dataEntriesAt(position): record = resolve(entry) # same resolution as above results.append(record) position = index.next(position) return results ``` Two implementation details matter for correctness:

• `index.locate` must be a search procedure whose cost is much smaller than scanning the whole data file — otherwise the index provides no benefit. This is why indexes are themselves built as sorted arrays (binary search), balanced trees, or hash tables, never as unsorted lists.
• Resolving a data entry to a record (the `dataFile.fetch(entry.rid)` step) costs one additional I/O per matching record when the index stores RIDs rather than full records. This extra hop is the price paid for keeping the index small; it is central to the cost analysis below and to why clustering (covered in a later article) matters so much.

The following diagram shows the architecture: a sorted index file of `(key, RID)` data entries sitting above an unordered (heap) data file. A lookup for key `483201` binary-searches the index, finds the RID, and follows the pointer to the exact page and slot in the data file.

Cost without an index. A linear scan of a heap file with `n` pages costs `O(n)` I/Os in the worst case (the matching record is on the last page, or there is no match at all), because every page must be examined. This holds regardless of how many records match — even a query that returns zero rows still costs a full scan, since the absence of a match can only be confirmed by checking everything.

Cost with a sorted-array index using binary search. If the index itself occupies `m` pages (typically `m ≪ n`, since the index stores only keys and RIDs, not full records), binary search over the index costs ``` O(log2 m) ``` I/Os to locate the first matching data entry, since each comparison halves the candidate region — this is the standard binary-search argument: after `i` probes, the search space size is `m / 2^i`, and the loop terminates when this reaches 1, giving `i = log2 m`. Then, for each of the `k` matching records, one additional I/O is needed to fetch the record from the data file (in the worst case, when data entries store RIDs rather than full records and matches are scattered across different pages). Total: ``` O(log2 m + k) ``` Since `m ≤ n` (the index is never larger than the data, and is usually much smaller because entries are smaller than full records), this is an exponential improvement over `O(n)` whenever `k` is small — exactly the case of a selective query, which is the query pattern indexes are built for.

Why this is correct, not just fast. Correctness of `INDEX_LOOKUP` rests on one invariant: the index's mapping from search-key values to data entries must always reflect the current contents of the data file. Formally, at every point in time, for every record `r` in the data file with search-key value `v`, the index must contain a data entry for `v` that resolves (directly or via RID) to `r`, and conversely, every data entry in the index must correspond to a record that actually exists. This invariant must be maintained transactionally: every `INSERT`, `DELETE`, or `UPDATE` on the data file must be paired with a corresponding update to every index defined over the modified fields. If this invariant is violated — say, a record is deleted from the data file but its stale RID is left in the index — a subsequent lookup silently returns garbage or a dangling pointer. Maintaining this invariant is precisely the index maintenance cost traded for lookup speed.

Honest tradeoffs.

• Storage overhead. Each index consumes additional disk space proportional to the number of records times the size of a `(key, RID)` pair (or key list). Multiple secondary indexes multiply this cost.
• Write amplification. Every insert/update/delete must update every affected index, not just the data file. A table with five secondary indexes turns one logical write into up to six physical writes (one to the heap, five to the indexes).
• Range queries need order. The `O(log m + k)` bound for range lookups (`RANGE_LOOKUP` above) only holds for indexes built on an ordered structure (sorted array, or later, a B+-tree). A hash-based index — foreshadowed later — gives excellent `O(1)` expected-time equality lookup but cannot efficiently answer range queries at all, because hashing destroys order.
• Selectivity matters. If a query matches a large fraction of the file (`k` close to `n`), the `O(log m + k)` index path can actually be slower than a raw sequential scan, because random-access I/O to fetch scattered records is more expensive per-record than sequential I/O. Query optimizers use estimated selectivity to decide whether to use an index at all — this is why "add an index" is not a universal performance fix.

Consider a `Students` table stored as a heap file across 4 data pages (as drawn above), and a secondary index built on `student_id`, stored as a sorted array of 5 `(key, RID)` entries across 1 index page (in reality index files span many pages; we keep this small for tracing).

Data file (heap, unordered by student_id):

Index (sorted array, one entry per record with that key — dense, Alternative 3 style, list of RIDs):

Query: `SELECT * FROM Students WHERE student_id = 483201;`

Trace of `INDEX_LOOKUP(index, 483201)`: 1. Binary search over 5 sorted keys `[102344, 217005, 483201, 601122, 771309]`.

• Probe 1: middle index = 2, key = `483201`. Match found immediately.
• Comparisons used: 1 (best case here, but worst case for 5 entries is `⌈log2 5⌉ = 3`).

2. `entries = [(p5,s1), (p9,s0), (p9,s2)]` — three RIDs. 3. Resolve each RID against the data file:

• `(p5,s1)` → fetch Page 5 → slot 1 → Wren
• `(p9,s0)` → fetch Page 9 → slot 0 → Alam
• `(p9,s2)` → fetch Page 9 → slot 2 → Torres
• (Page 9 is fetched once and reused for both slots in a real buffer-managed system — one I/O, not two — illustrating that even the "+k" term can be optimized when matches share a page.)

4. Return `{Wren, Alam, Torres}`.

Cost comparison for this query:

Here `n = 4` data pages and the index costs 1 page read plus 2 targeted data page reads — already a meaningful reduction, and the gap widens dramatically as the table grows to millions of pages while the index (holding only keys and RIDs) grows far more slowly, and its internal search stays logarithmic.

Contrast — why `student_id` was the right choice but `name` might not be, if instead the query were `WHERE name = 'Patel'` with no index on `name`: no index exists, so the system falls back to a full heap scan of all 4 pages, checking all 10 slots individually — exactly the cost indexing was introduced to avoid. This motivates building a secondary index on `name` as well, at the cost of maintaining a second structure on every insert/update/delete.

The concept of indexing predates computers entirely — library card catalogs and book indexes are the direct ancestors — but its formalization inside database systems is tied to the earliest work on file organization and access methods in the 1960s and 70s, as researchers sought principled alternatives to sequential scanning for the newly emerging large-scale data-processing systems.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — implements the primary/secondary index distinction directly: a `PRIMARY KEY` in InnoDB determines the clustering order of the table itself, while every `CREATE INDEX` statement on another column builds a secondary structure of exactly the `(key, RID)` shape described here. Query optimizers rely on estimated selectivity — the fraction of rows a predicate is expected to match — to decide, at query-planning time, whether to use an available index or fall back to a sequential scan, exactly mirroring the tradeoff analyzed above. Beyond relational databases, the same idea underlies search engines (an inverted index maps search terms to document IDs, the textual analogue of mapping search keys to RIDs), key-value stores (LSM-tree indexes in RocksDB and Cassandra), and file systems (directory structures are indexes mapping filenames to inode locations). Understanding the primitive — search key, data entry, primary vs. secondary — is what makes the subsequent, more specialized structures (B+-Tree Indexes, Hash Indexes) legible as refinements of a single idea rather than unrelated tricks. It also underlies the distinction between Dense vs Sparse Indexes (how many data entries exist per distinct key) and Clustered vs Unclustered Indexes (whether the index order matches physical storage order), both of which sharpen the vocabulary introduced here.

Ask the tutor: How does the choice between a dense and a sparse index change the space and lookup-time tradeoffs discussed here?