Dense vs Sparse Indexes
Imagine a library catalog for ten million books. One design writes a card for every single book. These cards are sorted by title. Another design writes a card only for the first book on each shelf. It trusts that once you find the shelf, you can scan the few books yourself. Both catalogs answer "where is this book?" correctly. But they cost very different amounts of paper. They also require very different amounts of walking. This is exactly the choice a database system faces when it builds an index over a file of records. It can build a dense index, with one entry per record. Or it can build a sparse index, with one entry per block. This decision sits at the heart of every storage engine. Indexes exist to avoid scanning an entire file for a handful of matching rows. But the index itself takes space and must be searched. Dense indexes give the fastest possible lookup. They let you check existence or uniqueness without ever touching the data file. The price is an index entry for every record. Sparse indexes shrink the index dramatically. They often let it fit in memory even when the data file does not. But they force a final scan within a block. They only work cleanly when the data file is physically sorted on the search key. Real systems rarely pick one extreme. A clustering index on a sorted file is almost always sparse. One entry per block already pins down the record's neighborhood. A secondary index on an unsorted file must be dense. There is no "block ordering" to exploit — the matching record could be anywhere. Understanding this trade-off is a conceptual bridge. It connects the basic idea of "an index speeds up lookup" to concrete data structures. Those structures are B+-Tree Indexes, which production databases actually use. They organize dense and sparse entries hierarchically. This article builds precise definitions of dense and sparse indexes. It walks through search algorithms for each. It derives their space and time costs from first principles. It traces a worked example byte-for-byte through a small file. It closes with the practical rules engines use during Index Selection. These rules decide which kind of index to build on which column.
- A dense index stores one index entry for every record in the data file; a sparse index stores one entry per block (only for the first record of each block).
- Dense indexes work on any file (sorted or not) and support direct existence/uniqueness checks without touching data; sparse indexes require the data file to be sorted on the index's search key.
- Sparse index size scales with the number of blocks `⌈n/f⌉`; dense index size scales with the number of records `n` — sparse is smaller by roughly the blocking factor `f`.
- Lookup in both cases is `O(log(index size))` via binary search, plus a bounded scan inside one block for sparse indexes.
- A clustering (primary) index is usually made sparse; a non-clustering (secondary) index over an unordered file must be dense.
- The dense/sparse trade-off is the conceptual seed for multilevel indexes and B+-Tree Indexes, which apply a sparse-index-of-an-index recursively.
Dense indexes trade space for guaranteed one-entry-per-record precision; sparse indexes trade a bounded in-block scan for an index small enough to keep in memory.
The idea
An index is an auxiliary data structure of `(search-key value, pointer)` pairs that lets a database locate records faster than scanning the whole file. The search key is the attribute (or attribute set) the index is built on — not necessarily a candidate key of the relation. Given a file of `n` records stored `f` per block (the blocking factor), the number of blocks is `b = ⌈n / f⌉`. A dense index contains an index record for every search-key value that appears in the data file (one entry per record if the search key is a candidate key, or one entry per distinct key value if duplicates are grouped and the pointer chains to the first of a run of matching records). A sparse index, by contrast, contains an index record only for some of the search-key values — canonically, one entry per block, holding the search key of the first record in that block and a pointer to the block. Because a sparse index only tells you which block a key's neighborhood lives in, it is only correct if the data file is sorted on the search key: only then does "first key in a block ≤ target key" reliably bracket the target's location. This is the crucial asymmetry: dense indexes place no ordering requirement on the data file, while sparse indexes are meaningful only as a companion to a sorted (or index-sequential) file — typically the file's clustering index, i.e., the index whose search key determines the physical order of records. A file can have at most one clustering index (there is only one physical order) but many non-clustering (secondary) indexes, and every secondary index over an unordered file must be dense, since there is no block-level ordering to exploit.
How it works
Dense index lookup. The index itself is stored as a sorted array (or sequence) of `(key, pointer)` pairs. To find records with search key `K`, binary search the index for `K`, follow the pointer directly to the matching record(s) in the data file. If duplicates are allowed, the dense index typically stores one entry per first occurrence, and that record links to the next record with the same key (or the index stores pointers to every occurrence, if the key is not sorted with duplicates grouped).
Sparse index lookup. Binary search the sparse index for the largest key `≤ K`. This identifies the block that would contain `K` if it exists. Fetch that block, then linearly scan its `f` records (which are sorted, since the data file is sorted) to find the exact match — or conclude `K` is absent if the scan passes where it should be. ```pseudocode // DENSE INDEX SEARCH // index: sorted array of (key, pointer), one entry per record (or per distinct key) function DENSE_SEARCH(index, K): lo = 0 hi = length(index) - 1 result_ptr = NULL while lo <= hi: mid = (lo + hi) / 2 if index[mid].key == K: result_ptr = index[mid].pointer // exact hit hi = mid - 1 // keep searching left for first match else if index[mid].key < K: lo = mid + 1 else: hi = mid - 1 if result_ptr == NULL: return NOT_FOUND return FOLLOW_CHAIN(result_ptr, K) // collect all records with key == K // SPARSE INDEX SEARCH // index: sorted array of (key, pointer), one entry per BLOCK (key = first key of block) function SPARSE_SEARCH(index, K): lo = 0 hi = length(index) - 1 best = -1 while lo <= hi: // find rightmost entry with key <= K mid = (lo + hi) / 2 if index[mid].key <= K: best = mid lo = mid + 1 else: hi = mid - 1 if best == -1: return NOT_FOUND // K smaller than every block's first key block = READ_BLOCK(index[best].pointer) // one I/O return SCAN_BLOCK_FOR_KEY(block, K) // O(f) linear scan inside the block ``` `FOLLOW_CHAIN` in the dense case walks a linked list of records sharing key `K` (built when duplicates exist); for a candidate-key search field this step is `O(1)`. `SCAN_BLOCK_FOR_KEY` in the sparse case examines up to `f` records, but since the block is sorted it can itself use binary search intra-block if desired — in practice `f` is small (tens to low hundreds of records) so a linear scan is fast and cache-friendly.
Complexity & correctness
Space. A dense index has exactly one entry per record (or per distinct key, if grouping duplicates), so its size is `Θ(n)` entries, occupying `⌈n / fᵢ⌉` blocks, where `fᵢ` is the index's own blocking factor (index entries are small, so `fᵢ` is typically much larger than the data file's `f`). A sparse index has one entry per data block, so its size is `Θ(n/f)` entries, occupying `⌈(n/f) / fᵢ⌉` blocks. Since `f ≥ 1` (usually `f` is tens to hundreds), the sparse index is smaller than the dense index by roughly a factor of `f`. This is the whole point of sparseness: with `n = 10⁷` records and `f = 100`, a dense index has `10⁷` entries while a sparse index has `10⁵` — often the difference between an index that must live partly on disk and one that fits entirely in a memory buffer.
Lookup time. Both use binary search over a sorted array of index entries, costing `O(log₂ m)` comparisons where `m` is the number of index entries — but the number of block I/Os, which dominates real cost, is `O(log_{fᵢ}(m))` if the index itself is stored across multiple blocks and each comparison step reads one index block (standard for on-disk binary search over paged storage). For the sparse index, add one more I/O to fetch the target data block, plus `O(f)` in-memory comparisons to scan within it — negligible against I/O cost, since that block is already resident. In big-O terms restricted to I/O: ``` Dense lookup I/O: O(log_fᵢ(n)) (search index; pointer leads straight to record) Sparse lookup I/O: O(log_fᵢ(n/f)) + 1 (search index; then one data-block fetch + in-block scan) ``` Because `n/f < n`, the sparse index search is over a strictly smaller structure and needs at most as many I/Os as the dense search, often one fewer level of the search tree — the "+1" for fetching the data block is usually cheaper than the I/O saved by the smaller index, and is unavoidable for a sparse index regardless.
Correctness argument (sparse index). The key invariant is: the data file is sorted by the search key, and the sparse index stores, for each block, the minimum key present in that block, in the same sorted order as the blocks themselves. Given this invariant, for any query key `K`: 1. Binary search finds the rightmost index entry `e` with `e.key ≤ K` (or reports "none," meaning `K` is less than every record's key, hence absent). 2. Because blocks are contiguous ranges of sorted keys and `e.key` is the minimum of its block, every record in blocks after `e`'s block has a key `> e.key`. If `K` exists, it cannot be in any later block, because those blocks' minimums already exceed `e.key ≤ K`... more precisely, since `e` is the rightmost entry with `key ≤ K`, the next block's minimum is `> K`, so `K` cannot appear there or later. 3. Symmetrically, `K` cannot be in an earlier block, because all earlier blocks contain keys `≤` the minimum of `e`'s block `≤ K`... actually the bound needed is simpler: earlier blocks' maximum key is `<` the minimum key of `e`'s block (by sortedness and block contiguity), and that minimum is `≤ K`, but we need `K`'s possible presence ruled out only if `K` is strictly less than the earlier block's range — which holds since blocks partition the sorted sequence without overlap. Hence `K`, if present, must lie in `e`'s block, and a linear (or binary) scan within that one block correctly finds it or confirms its absence. This proof leans essentially on the sortedness invariant — it is why sparse indexes cannot be built over unsorted files: without global sortedness, "first key of a block" carries no information about what else is in the block or where other keys live.
Correctness argument (dense index). Trivial in comparison: since every key has its own entry, binary search directly locates it (or its absence) with no auxiliary scan needed, and no ordering assumption on the data file is required at all — the data file can be a pure heap file. This is why dense indexes are the only valid option for secondary indexes on unsorted files: there is no block structure to exploit, so every record needs its own pointer.
Trade-off summary.
| Dense | Sparse | |
|---|---|---|
| Data file ordering required | none | must be sorted on search key |
| Index size | `Θ(n)` | `Θ(n/f)` |
| Lookup I/O | `O(log_fᵢ n)` | `O(log_fᵢ(n/f)) + 1` |
| Insert/delete maintenance | may need to shift many entries (or use overflow) | cheaper — only affects one block's minimum, and only if the inserted record becomes the new first record of the block |
| Existence check without reading data | yes (index alone suffices) | usually no (must fetch the block to confirm) |
Worked example
Consider a relation `Employee(id, name, dept)` stored as a data file sorted by `id`, with blocking factor `f = 3` (3 records per block). Suppose there are `n = 12` records, so `b = ⌈12/3⌉ = 4` blocks.
Data file (sorted by id):
| Block | Records (id, name) |
|---|---|
| B1 | (101, Ann), (103, Bo), (107, Cy) |
| B2 | (110, Di), (112, Ed), (115, Fi) |
| B3 | (120, Gu), (121, Hu), (130, Iv) |
| B4 | (133, Jo), (140, Ka), (145, Lu) |
Dense index (one entry per record — 12 entries): ``` 101→B1r1 103→B1r2 107→B1r3 110→B2r1 112→B2r2 115→B2r3 120→B3r1 121→B3r2 130→B3r3 133→B4r1 140→B4r2 145→B4r3 ```
Sparse index (one entry per block — 4 entries, storing each block's minimum key): ``` 101→B1 110→B2 120→B3 133→B4 ```
Query: find `id = 121`.
- Dense path: binary search the 12-entry array for `121`. With `lo=0, hi=11`: `mid=5` → key `115 < 121`, move right; `mid=8` → key `130 > 121`, move left; `mid=6` → key `120 < 121`, move right; `mid=7` → key `121`, found. That's 4 comparisons, then follow the pointer straight to `B3r2` — one data-block I/O. Total: ~4 comparisons + 1 data I/O (plus the I/O to bring the relevant index page into memory).
- Sparse path: binary search the 4-entry array for the rightmost key `≤ 121`. `lo=0, hi=3`: `mid=1` → key `110 ≤ 121`, record `best=1`, move right; `mid=2` → key `120 ≤ 121`, record `best=2`, move right; `mid=3` → key `133 > 121`, move left; loop ends, `best=2` → entry `120→B3`. Fetch block `B3` (one I/O): records `(120, Gu), (121, Hu), (130, Iv)`. Scan the 3 records: `120 ≠ 121`, `121 = 121` — found `Hu`. Total: ~2 comparisons + 1 data I/O + 2 in-block comparisons.
Both approaches return the correct record. The dense index needed a slightly larger binary search (3× as many entries) but no in-block scan; the sparse index needed a smaller binary search but a few extra comparisons inside the fetched block — a wash in this tiny example, but at scale (n in the millions), the sparse index's search-space reduction by factor `f` dominates and typically saves whole levels of index I/O, especially once the index is itself organized as a multilevel tree, foreshadowing B+-Tree Indexes.
Query: find `id = 125` (absent).
- Dense: binary search fails to find `125` exactly among the 12 keys — returns `NOT_FOUND` directly from the index, with zero data-file I/O.
- Sparse: binary search finds rightmost key `≤ 125` is `120→B3`. Fetch `B3`, scan `(120, 121, 130)`: none equals `125`, and since block is sorted and `130 > 125`, conclude absent. This required one wasted data-file I/O that the dense index avoided.
This exposes a genuine trade-off: dense indexes can sometimes answer non-existence purely from the (smaller-footprint-per-check, though larger overall) index; sparse indexes always require a confirming block fetch.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Building a sparse index on an unsorted file | Sparse correctness depends entirely on file-level sort order; without it "first key of block" is meaningless | Only build sparse indexes as the clustering index of a file physically sorted on that key |
| Forgetting the in-block scan cost for sparse lookups | Treating sparse index lookup as "just binary search" ignores the mandatory linear/binary scan inside the located block | Always account for the extra `O(f)` (or `O(log f)`) step and the extra I/O for the data block |
| Assuming dense index avoids all data I/O | True only for existence/uniqueness checks; retrieving actual attribute values still needs the data block unless the index is covering | Distinguish "index-only" queries from queries that project non-key columns |
| Maintaining a sparse index naively on inserts | Inserting into the middle of a sorted file may shift many blocks (or require overflow blocks), invalidating multiple sparse entries | Use overflow chains or periodic reorganization instead of shifting the whole file per insert |
| Confusing "dense/sparse" with "clustering/non-clustering" | Every non-clustering index must be dense, but not every dense index is non-clustering — the two axes are related but distinct | Keep the two classifications separate: sort-order relationship (clustering vs not) and entry granularity (dense vs sparse) |
| Ignoring duplicate keys in dense indexes | Naively storing one dense entry per record with a duplicate key wastes space when a single entry with a chain pointer suffices | Store one entry per distinct key value in the dense index, chaining to all matching records |
Pioneers & history
The dense/sparse index distinction, and the broader machinery of index-sequential file organization, grew out of practical file-system design for early sequential-and-random-access storage — long before relational databases existed. The concept was codified in IBM's ISAM (Indexed Sequential Access Method) systems and carried directly into relational query processing, where it remains one of the first trade-offs taught alongside file organization.
Origins · 1 minEdgar F. Codd and how this was discovered
Codd's 1970 paper on the relational model reframed data access as a logical, set-oriented problem, separating what to retrieve from how it is physically stored — including whether an index is dense or sparse. This separation is precisely why the dense/sparse trade-off could later be treated as an internal storage-engine decision, invisible to the relational query language itself.
Where this matters
Every production relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — implements a clustering index as a sparse structure at the leaf level of its B+-tree (in InnoDB's clustered index, the leaf pages are the sorted data pages, so the tree above them is effectively a multilevel sparse index) and a secondary index as a dense structure over an unordered heap or over the clustering key. Search engines and log-structured storage systems (e.g., LSM-tree–based stores like Cassandra, RocksDB, LevelDB) also exploit sparse indexing: an SSTable's in-memory sparse index samples one key per block, and a binary search there narrows to one block before a bounded on-disk scan finds the exact key — a direct descendant of the sparse-index idea. Column-store analytics engines use sparse "zone maps" (min/max per block) as an even coarser cousin of the sparse index to skip irrelevant blocks entirely during full scans. Understanding dense versus sparse indexing is the essential prerequisite for the recursive, multilevel structure of B+-Tree Indexes, and it directly informs the heuristics used during Index Selection, where a query optimizer or DBA weighs index size, maintenance cost, and lookup speed against the specific workload's read/write mix — building on the foundational vocabulary from Introduction to Indexing.
Ask the tutor: How does the dense/sparse trade-off change once the index itself is organized as a B+-tree instead of a flat sorted array?
Can a data file have both a dense and a sparse index at the same time?
Yes. A file typically has one clustering index — sparse, since the file is sorted on that key — and any number of secondary indexes, which must be dense if the file itself is not additionally sorted on those other attributes. For example, an `Employee` file clustered (sorted) by `id` might carry a sparse index on `id` and a separate dense index on `name`, since the file is not sorted by name. Each index is independent; the dense/sparse choice is made per index based on whether the file happens to be physically ordered by that particular search key.
Does a sparse index always save space compared to a dense index?
In terms of number of entries, yes — a sparse index has one entry per block versus one per record, so it is smaller by roughly the blocking factor `f` (often 10× to 1000× fewer entries). However, "always smaller" assumes the same underlying file; a sparse index is only valid when the file is sorted on the key, so the comparison "dense vs. sparse for the same column" only makes sense when a sorted file already exists. You cannot freely choose sparse over dense for an arbitrary unsorted file — sortedness is the entry ticket for sparseness, not just an optimization.
How do inserts and deletes affect dense versus sparse indexes differently?
For a dense index, inserting a new record requires inserting a new index entry at the correct sorted position, potentially shifting many subsequent entries (mitigated in practice with overflow areas or tree structures). For a sparse index, an insert only requires updating an existing entry if the new record becomes the new minimum key of some block; otherwise the sparse index needs no change at all, since it only tracks block-level minimums. This makes sparse indexes cheaper to maintain on average, but both structures suffer if the underlying sorted file itself must be reorganized to keep records in order — a cost usually addressed with overflow chaining rather than in-place shifting.
Is a sparse index the same thing as a multilevel index?
No, though they are closely related. A sparse index is a single level of entries, one per block of the underlying file. A multilevel index applies the same idea recursively: if the (sparse or dense) first-level index itself grows too large to search efficiently, you build a second-level sparse index over the first-level index's blocks, and so on, until the top level fits in memory. B+-trees generalize this recursive sparse-index-of-an-index idea into a self-balancing structure, which is why understanding plain sparse indexing is the natural stepping stone to B+-Tree Indexes.
Why not just always use a dense index, since it never needs an in-block scan?
Dense indexes trade away space and, at scale, that space cost becomes a real performance cost: a dense index over a billion-row table has roughly a billion entries, which may not fit in memory, forcing extra disk I/O just to search the index itself. A sparse index over the same table, with blocking factor 100, has roughly ten million entries — potentially small enough to keep entirely in a memory buffer, so the only disk I/O per query is the single data-block fetch. The in-block scan sparse indexes pay is cheap (in-memory, small `f`) compared to the I/O saved by keeping the whole index resident.
What happens to a sparse index when the data file's sort order does not match any single query's needs?
If queries frequently filter or sort by a column other than the file's physical order, the sparse index built on the clustering key does not help those queries at all — searching it only bounds the clustering key range, not the unrelated attribute's range. In that case, the system needs a separate dense secondary index on the other attribute, since that attribute's values are scattered arbitrarily across blocks with respect to physical order. This is a central concern in Index Selection: choosing which single column gets the sparse clustering index, since a table can only be physically sorted one way at a time.
Do NoSQL and log-structured storage engines still use this dense/sparse distinction?
Yes, in a directly analogous form. LSM-tree-based engines (used in Cassandra, RocksDB, LevelDB) write sorted, immutable files (SSTables) and keep a small in-memory sparse index recording one key sample per data block, exactly mirroring the classical sparse index over a sorted file. A lookup binary-searches this sparse in-memory structure to find the candidate block, then scans or binary-searches within that block on disk — the same two-phase algorithm covered here, just relabeled for a different storage engine.