The Story That Explains Indexes
A database index is exactly this: a small, sorted side-structure of (search key → pointer) entries that lets the engine jump to the rows it needs instead of scanning the whole table. This tutorial builds the idea up from first principles — why indexes are fast, how they are organised, and the two structures that power them: hashing and the B-tree / B+-tree.
An index trades a little extra storage and write cost for dramatically faster reads. The whole game is reducing how many disk blocks the engine must read to answer a query. Hold that sentence in mind — the next section makes it precise.
Anatomy of an Index Entry
Every index entry has two parts: a search key (the value you look up) and a pointer (the block or row address where the matching record lives).
Because the index is far smaller than the table and kept in sorted order, the engine finds the pointer fast, then makes one jump to the record.
Why Indexes Are Fast — The Disk-Block Cost Model
To understand why indexes help, you must understand what is actually expensive. A database does not read one row at a time; it reads fixed-size blocks (also called pages, typically 4–16 KB) from disk, each holding many rows. Reading a block from disk is thousands of times slower than any work the CPU does in memory. So the cost of a query is measured in block accesses (disk I/Os) — not in CPU cycles.
A single random disk read can take roughly 10,000–100,000× longer than reading the same data from RAM. That is why we count how many blocks a query touches and treat everything else as free. Indexes win by slashing that count.
Same data, same query. The index converts a linear sweep into a near-instant jump — the entire reason indexes exist.
Dense vs Sparse Indexes
This single distinction underlies every index type that follows, and it is a direct consequence of the cost model above.
| Property |
|---|
| One entry for every record |
| Larger, but finds any key directly |
| Required when the file is not sorted by the key |
| Used by secondary indexes |
| Property |
|---|
| One entry per data block |
| Smaller, less storage, fewer index blocks to search |
| Needs the file sorted by the key |
| Used by primary & clustering indexes |
A sparse index stores just the first key of each block. To find key 50, you locate the largest index key that is ≤ 50, jump to that block, and scan within it. This only works because the records are physically in sorted order — otherwise 50 could be in any block, forcing a dense entry for every single record.
Multilevel Indexes — An Index on the Index
Here is the key theoretical leap. Even an index can grow large. A dense index on a million records has a million entries — far too big to search in a couple of block reads. So we apply the same trick to the index itself: treat the (sorted) index as a file and build a smaller sparse index over it. That outer level is smaller still, so we can index it too — repeating until the topmost level fits in a single block.
Each level is the blocking factor smaller than the one below it, so the number of levels grows only logarithmically with the data.
A multilevel index reaches any record in about logfan-out(N) block
reads. The catch: a plain multilevel index becomes lopsided and expensive to maintain as rows
are inserted and deleted. The B+-tree is precisely a multilevel index that
keeps itself balanced automatically — which is why Section 12 builds on this.
Primary Index — Sparse, on the Ordering Key
A primary index is built on the ordering key field of a file that is physically sorted by that field (typically the primary key). It is sparse: one entry per block, pointing to the block's first record. The animation shows a lookup for key 50.
The index has only 3 entries for 9 records: locate the right block via the index, then scan inside that one block.
-- In most engines the PRIMARY KEY automatically creates the primary/clustered index
CREATE TABLE students (
roll_no INT PRIMARY KEY, -- file ordered by roll_no; sparse index built
name VARCHAR(50),
branch VARCHAR(20)
);Clustered Index — Data Physically Sorted by the Key
A clustered index determines the physical order of the rows on disk: the table's data is the index's leaf level. Because rows can be laid out in only one order, a table can have at most one clustered index. A primary index is one kind of clustered index; a clustering index is the variant built on an ordering non-key field, where many rows share the same value (e.g. all students of one branch stored together).
When the rows you want are physically adjacent (high clustering), a range query like
roll_no BETWEEN 100 AND 200 reads a handful of consecutive blocks. With a
non-clustered index the same matching rows may be scattered across hundreds of blocks —
one random read each — which is why the optimiser sometimes prefers a full scan instead.
Secondary Index — Dense, on a Non-ordering Field
A secondary index is built on a field the file is not sorted by —
say, looking up students by name when the file is ordered by roll_no.
Since the target values are scattered across the file, a secondary index must be
dense: one entry per record (there is no "first key of the block" to anchor a
sparse entry). You can create many secondary indexes on one table, each
supporting a different access path into the same data.
-- Secondary (non-clustered) index to speed lookups by name
CREATE INDEX idx_students_name ON students(name);
-- A unique secondary index also enforces uniqueness
CREATE UNIQUE INDEX idx_students_email ON students(email);
Every secondary index must be updated on each INSERT, UPDATE, and
DELETE, and it consumes disk space. Index the columns you actually filter, join,
or sort on — not every column "just in case." More on choosing indexes in Section 15.
Primary vs Clustering vs Secondary — At a Glance
| Aspect | Primary index | Clustering index | Secondary index |
|---|---|---|---|
| Built on | ordering key field | ordering non-key field | non-ordering field |
| File sorted on this field? | Yes | Yes | No |
| Dense or sparse | Sparse | Sparse (one per value) | Dense |
| How many per table | One | One | Many |
| Index size | Smallest | Small | Largest |
Hashing — Computing the Location Directly
Indexes search for a location; hashing computes it. A
hash function h(key) maps the key to a bucket number,
and the record is stored in that bucket. A lookup applies the same function and goes straight to the
bucket — no tree to descend, no list to scan. On average this is O(1):
constant time, independent of table size.
Key 27 hashes to bucket B2. Because B2 is already full, the collision is resolved by chaining to an overflow bucket.
Collisions, Load Factor & Dynamic Hashing
Two different keys can hash to the same bucket — a collision. Collisions are unavoidable, so every hashing scheme needs a strategy to handle them, and a way to stay fast as the data grows.
| How it works |
|---|
| Each bucket links to overflow buckets |
| Collisions extend a chain |
| Simple; buckets never "fill up" |
| Long chains slow lookups |
| How it works |
|---|
| No overflow buckets; probe nearby slots |
| Linear / quadratic / double hashing |
| Cache-friendly, compact |
| Degrades sharply when nearly full |
The load factor = (number of stored records) ÷ (total bucket slots). The closer it gets to 1, the more collisions occur and the slower lookups become. Good hash tables keep the load factor moderate — and grow when it climbs too high.
Both extendible and linear hashing are forms of dynamic hashing: the number of buckets adapts to the amount of data, so performance stays near O(1) even as the table grows or shrinks — fixing the central weakness of static hashing.
B-tree / B+-tree Basics
The B+-tree is the workhorse index of nearly every relational database. It is the self-balancing realisation of the multilevel index from Section 5: a shallow, wide, always-balanced tree that reaches any key in just a few disk reads and supports both exact lookups and range scans.
Height ≈ logfan-out(N). With a fan-out of 100 and
one million keys, the height is just log100(1,000,000) = 3.
So any record is reachable in about 3–4 block reads, versus
10,000 for a full scan. High fan-out is the whole trick — it keeps the tree flat.
Each level narrows the search. For a range query like 40–70, find 40 in the leaf, then walk the dashed leaf links rightward.
-- B-tree is the DEFAULT index type in almost every relational database
CREATE INDEX idx_emp_salary ON employees(salary); -- B-tree implied
-- Some engines let you request a hash index explicitly (great for = only)
CREATE INDEX idx_emp_email ON employees(email) USING HASH;Staying Balanced — Insertion, Splitting & B-tree vs B+-tree
What makes a B+-tree better than a hand-built multilevel index is that it repairs its own balance on every insert and delete, so all leaves always stay at the same depth.
Remove the key from its leaf. If the leaf falls below half-full, it borrows a key from a sibling, or merges with one — possibly propagating up and, when the root loses its last separator, shrinking the tree's height. Borrowing and merging are what keep every node at least half-full.
| Aspect | B-tree | B+-tree |
|---|---|---|
| Where data pointers live | in all nodes | only in leaf nodes |
| Internal nodes hold | keys + data | keys only (routing) |
| Leaves linked together? | No | Yes — sequential chain |
| Range / ordered scans | Awkward (tree traversal) | Excellent (walk the leaves) |
| Fan-out (keys per node) | Lower (data takes space) | Higher → shallower tree |
| Used by most databases? | Rarely | Yes — the default |
Hashing vs B-tree — When to Use Which
| Query need | Hash index | B+-tree index |
|---|---|---|
Exact match (=) | Excellent — O(1) avg | Good — O(log n) |
Range (>, BETWEEN) | Useless — keys scattered | Excellent — ordered leaves |
Sorting / ORDER BY | No help | Already sorted |
Prefix / LIKE 'abc%' | No | Yes |
| Worst-case lookup | Bad with many collisions | Always O(log n) |
Reach for hashing when every query is an exact-match equality lookup. Reach for a B+-tree when you also need ranges, sorting, or prefix searches — which is why it is the default almost everywhere.
Choosing & Using Indexes Well
Knowing the structures is half the battle; the other half is deciding which indexes to create. These ideas come straight out of the cost model.
(a, b, c) is sorted by a, then b, then c. Column order is a design decision — put the most-filtered column first.
A composite index on (a, b, c) can serve queries filtering on a,
on a AND b, or on a AND b AND c — but not on
b alone or c alone. The leftmost column(s) must be used, because the
index is sorted left-to-right.
Practice Problems
h(k) = k mod 7, which bucket holds key 100? → 100 mod 7 = 2.
WHERE salary BETWEEN 50000 AND 70000? → a B+-tree — hashing can't do ranges.
(dept_id, salary). Will it speed up WHERE salary = 60000 alone? → No — the left-prefix (dept_id) is missing.
Golden Rules
logfan-out(N) reads — the idea the B+-tree automates and keeps
balanced.