Indexing Overview for Query Access

An index is a data structure, separate from the table's raw storage, that maps values of a search key to the locations of the records containing those values. Formally, an index on attribute $A$ supports a function

in time far better than scanning every record. Without an index, answering `WHERE A = v` requires reading every block of the table — a linear scan costing $O(n)$ block accesses, where $n$ is the number of blocks. A primary index (sometimes called a clustering index) is built on the attribute(s) that determine the physical sort order of the file — typically the primary key. Because the file is physically ordered, primary indexes can be sparse: one index entry per block is enough, since once you land in the right block you scan a handful of records to find the exact match. A secondary index is built on a non-ordering attribute. Since the file is not sorted by that attribute, a secondary index must be dense — one entry per distinct search-key value (or per record) — because there is no way to infer which block holds a given value without an explicit pointer for each value. Two access-path technologies dominate: ordered indexes, almost universally implemented as B+-trees, and hash indexes. A B+-tree keeps keys sorted in a balanced multiway tree, supporting equality search, range search, and ordered traversal, all in $O(\log_B n)$ disk accesses where $B$ is the tree's fanout. A hash index applies a hash function to the search key to compute a bucket address directly, giving expected $O(1)$ access for exact-match queries but no support for range queries or ordering — hashing scatters keys, so `WHERE age BETWEEN 20 AND 30` cannot be answered by jumping to one bucket. Choosing between them is a direct consequence of the query workload: point lookups favor hashing, range queries and sorting favor B+-trees.

B+-tree structure. A B+-tree of order $n$ is a balanced tree where every internal node holds between $\lceil n/2 \rceil$ and $n$ pointers (and $\text{pointers}-1$ keys), and all actual data pointers live in the leaf nodes, which are linked together left-to-right to support fast range scans. Internal nodes exist purely to route search — they hold copies of keys to guide traversal, not data pointers. This design keeps the tree shallow (height $O(\log_n N)$ for $N$ keys) while making sequential range scans cheap, since leaves form a linked list.

Search algorithm. Starting at the root, at each internal node the search compares the target key against the node's keys to pick the correct child pointer, descending until a leaf is reached; the leaf is then scanned for the matching key(s). ``` function BPlusTreeSearch(node, key): if node is a leaf: for each (k, pointer) in node.entries: if k == key: return pointer // found: pointer to record (or record itself) return NOT_FOUND // internal node: find the child to descend into i = 0 while i < node.numKeys and key >= node.keys[i]: i = i + 1 return BPlusTreeSearch(node.children[i], key) function RangeSearch(node, low, high): leaf = BPlusTreeFindLeaf(node, low) // descend to leftmost leaf >= low results = [] while leaf != null: for each (k, pointer) in leaf.entries: if k > high: return results if k >= low: results.append(pointer) leaf = leaf.nextLeaf // follow the leaf-level linked list return results ```

Insertion. Insert the new key into the correct leaf (found via search). If the leaf overflows (exceeds capacity), split it into two leaves and push a copy of the middle (or first key of the right half) up into the parent. If the parent overflows, split it too, and the process may propagate up to the root, possibly creating a new root and increasing the tree's height by one. ``` function Insert(tree, key, pointer): leaf = FindLeaf(tree.root, key) InsertIntoLeaf(leaf, key, pointer) if leaf.numEntries > MAX_LEAF_ENTRIES: SplitLeaf(leaf) // may recursively split ancestors function SplitLeaf(leaf): newLeaf = new LeafNode() move upper half of leaf.entries to newLeaf newLeaf.nextLeaf = leaf.nextLeaf leaf.nextLeaf = newLeaf promoteKey = newLeaf.entries[0].key InsertIntoParent(leaf.parent, promoteKey, newLeaf) // may cascade upward ```

Hash index structure and search. A hash index applies a hash function $h$ to the search key to compute a bucket number, then follows that bucket's pointer directly to the data (or to an overflow chain if the bucket is full). ``` function HashSearch(hashTable, key): bucketIndex = h(key) mod numBuckets bucket = hashTable.buckets[bucketIndex] for each (k, pointer) in bucket.entries: // includes overflow chain if k == key: return pointer return NOT_FOUND ``` Static hashing fixes `numBuckets` at creation time, so heavy growth causes long overflow chains and degraded performance; extendable hashing and linear hashing grow the bucket directory dynamically to keep chains short, at the cost of extra bookkeeping (a directory of pointers reinterpreted via a growing number of hash bits).

B+-tree time complexity. Let $N$ be the number of keys and $n$ the tree's fanout (order). The tree height is

because each level partitions the key space among up to $n$ children, and a perfectly balanced tree of height $h$ can hold up to $n^h$ keys. Since $n$ is chosen so that one node fits in one disk block (typically hundreds of entries for 4KB–16KB blocks), $h$ is very small in practice — a tree with fanout 100 needs only $\log_{100} N$ levels, so even a billion-row table needs about 5 block accesses. Each descent step does $O(1)$ work at a node (binary search within the node, or even linear scan if $n$ is small), so total search cost is $O(\log_n N)$ disk I/Os, and range queries of size $k$ cost $O(\log_n N + k/n)$ since matching leaves are linked sequentially. Insertion and deletion also cost $O(\log_n N)$, since they follow the same root-to-leaf path and any node split or merge propagates along at most that path.

Why it's balanced (invariant argument). The key invariant is: every leaf is at the same depth. Insertion never adds a new leaf below existing ones — it only splits a full leaf into two leaves at the same depth, pushing a separator key up. If the split propagates all the way to the root, a new root is created above the old one, uniformly increasing the depth of every leaf by exactly one. Because splits are the only way the tree grows, and they preserve uniform depth, the invariant holds by induction on the number of insertions. This guarantees worst-case $O(\log_n N)$ height, unlike an unbalanced binary search tree which can degrade to $O(N)$.

Space complexity. A B+-tree occupies $O(N/n)$ leaf blocks (data pointers) plus $O(N/n)$ internal blocks (proportional across levels, geometric series bounded by a constant factor of leaf count), so total space is $O(N)$ — linear in the number of indexed entries, with a constant-factor overhead controlled by fanout.

Hash index complexity. Assuming a good hash function distributes keys uniformly across $m$ buckets, and load factor $\alpha = N/m$ is kept near 1 (via dynamic resizing), expected search cost is $O(1 + \alpha) = O(1)$ amortized. This follows directly from the expected chain length in each bucket under uniform hashing — a standard hashing argument, the same one underlying hash join-style algorithms. Worst case, if all keys collide into one bucket (an adversarial or pathological hash function), search degrades to $O(N)$; this is why production hash indexes use strong, well-tested hash functions and dynamic bucket splitting (extendable/linear hashing) to bound chain length.

Honest tradeoffs. Hash indexes cannot answer range queries, ordering (`ORDER BY`), or prefix matches (`LIKE 'abc%'`) efficiently, because semantically-close keys are scattered to unrelated buckets by design. B+-trees pay a $\log$ factor that hashing avoids for pure equality lookups, and every index — hash or tree — adds write-path cost: each insert/update/delete must also update every affected index, and each index consumes disk space proportional to the indexed column's size times the row count. A table with five secondary indexes may see inserts run several times slower than an unindexed table, which is why indexing decisions are workload-driven, not automatic.

Consider a `Students` table with 10,000 rows, physically stored sorted by `student_id` (the primary key), block size holding 100 records, so the file spans 100 blocks.

Case 1 — primary sparse index lookup, `WHERE student_id = 8420`.

Case 2 — secondary dense index lookup, `WHERE major = 'Computer Science'` (non-ordering column, 1,200 matching rows scattered across the file). Since the file is sorted by `student_id`, not `major`, a secondary index on `major` must be dense: it holds one entry per matching row (or a value plus a list of record pointers), because the file gives no clue where CS majors physically live.

This second case is the classic lesson: a secondary index accelerates finding qualifying keys but does not guarantee cheap retrieval of the rows themselves, because the underlying data is not physically clustered by that attribute. This is exactly the tension that a query optimizer must weigh — covered formally in Cost Estimation for Query Plans — when deciding whether using the index beats a full scan.

Case 3 — hash index, `WHERE student_id = 8420` on a hash index instead.

The B-tree, ancestor of the B+-tree used in essentially every production database and file system today, emerged from a need to organize large sequential files on slow disk hardware efficiently.

Every major relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — uses B+-trees as the default index structure for `CREATE INDEX`, and most also expose hash indexes for pure equality workloads (PostgreSQL's `USING HASH`, and hash-based partitioning in distributed systems). Primary key constraints typically create a clustering B+-tree index automatically, physically organizing the table itself. Key-value stores and in-memory caches (Redis, memcached-style systems) rely on hash tables for their core $O(1)$ lookup guarantee, while search engines and time-series databases lean on B+-tree-like structures (or LSM-trees, a write-optimized cousin) to support range and ordered scans efficiently. Beyond single-table lookups, indexes are the backbone of efficient joins: an indexed nested-loop join, previewed in Join Algorithms: Nested-Loop, uses an index on the inner relation's join key to avoid a full inner scan per outer row, turning an $O(n \cdot m)$ join into something closer to $O(n \log m)$. The query optimizer's decision of which index to use for which operator — scan, join, sort avoidance via index order — is the central subject of the Query Processing Overview and is quantified precisely by the cost models in Cost Estimation for Query Plans, which weigh index selectivity, I/O cost, and clustering against the alternative of a full scan.

Ask the tutor: How does the query optimizer decide between using an index and doing a full table scan, in terms of concrete cost formulas?