Dense vs Sparse Indexes
Sparse Index
Read aloud is unavailable in this browser.
The Economy of Selective Indexing
Having examined dense indexes with their one-entry-per-record approach, we now turn to the sparse index—an elegantly economical alternative that achieves dramatic storage savings by indexing only a carefully chosen subset of records.
The sparse index challenges a seemingly obvious assumption: that finding any record requires a direct pointer to that specific record. Instead, sparse indexing leverages data organization to provide efficient access with far fewer index entries. This approach trades some search steps for substantial storage and maintenance benefits.
By the end of this page, you will understand the complete mechanics of sparse indexing—the critical prerequisite of sorted data files, the one-entry-per-block strategy, search algorithms that combine index lookup with block scanning, and the mathematical relationship between sparse index size and data organization. You'll recognize when sparse indexing is possible and optimal.
Formal Definition of Sparse Index
A sparse index is an index structure where index entries exist for only a subset of records in the data file. Specifically, a sparse index typically contains one entry per data block (or per group of records), rather than one entry per record.
Formally:
Given a data file $D$ containing $n$ records organized into $b$ blocks, with data sorted on indexing attribute $K$, a sparse index $S$ on $K$ satisfies:
$$|S| = b \ll n$$
where each index entry $e_j \in S$ is a pair $(k_j, p_j)$ such that:
- $k_j$ is the search key value of the first (or anchor) record in block $j$
- $p_j$ is a pointer to block $j$ in the data file
The critical insight: because data is sorted on $K$, knowing the first key in each block is sufficient to locate any key through a combination of index lookup and sequential block scan.
Sparse indexes REQUIRE the data file to be sorted on the indexed attribute. Without sorted data, knowing the first key of a block provides no information about what other keys that block contains. This prerequisite fundamentally limits where sparse indexes can be applied—only to the primary ordering of the data.
The Block-Based Strategy:
Sparse indexing exploits a fundamental property of sorted data: if you know where a range begins, you can find anything within that range through sequential scan. Consider:
- Block 5 starts with key value 500
- Block 6 starts with key value 600
- Searching for key 547:
- Index tells us: 500 ≤ 547 < 600, so key 547 (if it exists) is in Block 5
- Read Block 5 and scan for key 547
This two-phase search (index lookup + block scan) is the defining characteristic of sparse index access.
Structural Anatomy of a Sparse Index
A sparse index has a simpler structure than its dense counterpart, containing far fewer entries. Let's examine its components:
- •Anchor Entries: Each entry represents one data block, containing the first (smallest) key in that block—the 'anchor' or 'fence' key.
- •Block Pointers: Pointers reference entire blocks, not individual records. This simplifies address calculation.
- •Sorted Order: Entries remain sorted by key value, enabling efficient binary search.
- •Implicit Coverage: Each entry implicitly covers all records in its block, not just the anchor record.
Visual Structure:
Consider a sparse index on a sorted Employee table:
SORTED DATA FILE (by employee_id):
┌─────────────────────────────────────────────────────────────┐
│ Block 0: [E101, "Alice"] [E102, "Bob"] [E103, "Carol"] │ ← Anchor: E101
├─────────────────────────────────────────────────────────────┤
│ Block 1: [E104, "David"] [E105, "Eve"] [E106, "Frank"] │ ← Anchor: E104
├─────────────────────────────────────────────────────────────┤
│ Block 2: [E107, "Grace"] [E108, "Henry"] [E109, "Ivy"] │ ← Anchor: E107
├─────────────────────────────────────────────────────────────┤
│ Block 3: [E110, "Jack"] [E111, "Kate"] [E112, "Leo"] │ ← Anchor: E110
└─────────────────────────────────────────────────────────────┘
SPARSE INDEX:
┌─────────────────────────────┐
│ [E101 → Block 0] │ ← Only FIRST key per block
│ [E104 → Block 1] │
│ [E107 → Block 2] │
│ [E110 → Block 3] │
└─────────────────────────────┘
Dense Index would have: 12 entries (one per employee)
Sparse Index has: 4 entries (one per block)
Storage reduction: 67% smaller index
The sparse index for 12 records requires only 4 entries—one-third the size of the dense equivalent.
Most systems use the minimum key in each block as the anchor. Some systems alternatively use the maximum key, which slightly changes the search algorithm but yields equivalent performance. The key insight is that exactly ONE representative key per block is sufficient.
Search Algorithms on Sparse Indexes
Searching a sparse index is a two-phase process: first locate the target block using the index, then scan within that block to find the specific record. This differs fundamentally from dense index search.
Point Query Search Algorithm:
SPARSE_SEARCH(sparse_index S, key K):
// Phase 1: Index Lookup - Find candidate block
block_ptr ← NULL
// Binary search for largest anchor ≤ K
for each entry (anchor, ptr) in S (descending):
if anchor ≤ K:
block_ptr ← ptr
break
if block_ptr is NULL:
return NOT_FOUND // K smaller than any anchor
// Phase 2: Block Scan - Sequential search within block
block ← READ_BLOCK(block_ptr)
for each record R in block:
if R.key = K:
return R // Found!
if R.key > K:
break // Past where K would be (sorted)
return NOT_FOUND
Complexity Analysis:
- Phase 1 (Index lookup): O(log b) where b = number of blocks
- Phase 2 (Block scan): O(r) where r = records per block
- Total: O(log b + r)
Since r is typically 50-200 records, the block scan is effectively O(1) compared to data growth.
Critics sometimes view the block scan as 'extra work' compared to dense indexes. However, once a block is read into memory, scanning its contents is extremely fast—typically microseconds. The dominant cost is I/O, and sparse indexes minimize index I/O while requiring exactly ONE data block I/O per point query.
Storage Efficiency Analysis
The primary advantage of sparse indexing is storage efficiency. Let's quantify this benefit through careful analysis.
Size Comparison Formula:
Define:
- $n$ = number of records in data file
- $b$ = number of blocks in data file
- $r$ = records per block (blocking factor) = $n/b$
- $e$ = size of one index entry (key + pointer)
Then:
- Dense Index Size: $S_{dense} = n \times e$
- Sparse Index Size: $S_{sparse} = b \times e = (n/r) \times e$
Storage Ratio: $$\frac{S_{sparse}}{S_{dense}} = \frac{b}{n} = \frac{1}{r}$$
If $r = 100$ records per block, the sparse index is 100x smaller than the dense index.
| Records (n) | Block Factor (r) | Dense Entries | Sparse Entries | Size Ratio |
|---|---|---|---|---|
| 1 Million | 100 | 1,000,000 | 10,000 | 1% |
| 10 Million | 100 | 10,000,000 | 100,000 | 1% |
| 100 Million | 100 | 100,000,000 | 1,000,000 | 1% |
| 1 Billion | 100 | 1,000,000,000 | 10,000,000 | 1% |
Practical Storage Example:
Scenario: Customer table with 100 million records
Data File Characteristics:
├── Record size: 200 bytes average
├── Block size: 8 KB
├── Records per block: ~40 (8192 / 200)
├── Total blocks: 2.5 million
└── Data file size: ~20 GB
Index Entry Size:
├── Key (customer_id INT): 4 bytes
├── Pointer: 8 bytes
└── Total entry: 12 bytes
Dense Index:
├── Entries: 100,000,000
├── Raw size: 1.2 GB
└── With B-tree overhead: ~1.4 GB
Sparse Index:
├── Entries: 2,500,000
├── Raw size: 30 MB
└── With overhead: ~36 MB
Storage Savings: 1.4 GB → 36 MB (97.4% reduction)
For this realistic scenario, the sparse index is nearly 40× smaller than the dense equivalent.
Smaller indexes are far more likely to fit entirely in the buffer pool (RAM). A 36 MB sparse index can reside fully in memory on almost any server, while a 1.4 GB dense index may require disk access. This can mean the difference between microsecond and millisecond lookup times.
The Sorted File Constraint
The fundamental limitation of sparse indexes is their absolute requirement for sorted data. This constraint emerges directly from the index's search semantics and has profound architectural implications.
Why Sorting is Required:
Consider what happens if data is NOT sorted:
UNSORTED DATA FILE:
┌─────────────────────────────────────────────────────────────┐
│ Block 0: [E107, "Grace"] [E102, "Bob"] [E105, "Eve"] │
├─────────────────────────────────────────────────────────────┤
│ Block 1: [E101, "Alice"] [E109, "Ivy"] [E103, "Carol"] │
├─────────────────────────────────────────────────────────────┤
│ Block 2: [E108, "Henry"] [E104, "David"] [E106, "Frank"] │
└─────────────────────────────────────────────────────────────┘
Spurios Sparse Index (INVALID):
[E107 → Block 0] ← But E102 and E105 also in Block 0!
[E101 → Block 1] ← But E109 and E103 also in Block 1!
[E108 → Block 2] ← But E104 and E106 also in Block 2!
Searching for E104:
- Index says: E104 < E107 < E108... no valid floor key!
- Block 0's anchor (E107) > E104, so skip Block 0
- Block 1's anchor (E101) ≤ E104 < Block 2's anchor (E108)
- Search Block 1... E104 NOT FOUND (it's in Block 2!)
❌ INCORRECT RESULT
The sparse index's logic assumes all keys between consecutive anchors reside in the first anchor's block. Without sorting, this assumption fails catastrophically.
- •Single Sparse Index Per Table: Data can only be sorted on ONE attribute. Only that attribute can have a sparse index. All other columns require dense indexes.
- •Clustered Index Connection: The sparse-indexable column is inherently the clustering key—the attribute that determines physical data order.
- •Insert Performance Impact: Inserting into a sorted file may require shifting records to maintain order, creating write overhead.
- •Secondary Index Exclusion: Secondary indexes on non-clustering columns cannot be sparse—they must be dense by necessity.
- •Primary Key Affinity: Primary keys are natural candidates for sparse indexes since they often define the clustering order.
In most database architectures, each table can have at most ONE sparse/clustered index (on the sorting column) and potentially MANY dense/non-clustered indexes (on other columns). This asymmetry makes the choice of clustering column architecturally significant.
Maintenance Operations
Sparse index maintenance is generally simpler than dense index maintenance—but with important caveats related to maintaining sorted data order.
Inserting into a Sparse-Indexed Table:
INSERT_SPARSE(table T, record R, sparse_index S):
// Step 1: Find correct block for sorted position
target_block_idx ← FIND_FLOOR_INDEX(S, R.key)
target_block ← T.blocks[target_block_idx]
if target_block HAS SPACE:
// Simple case: insert and maintain order within block
INSERT_SORTED_WITHIN_BLOCK(target_block, R)
// Index unchanged! Anchor key still smallest
else:
// Block full: must split
(block1, block2) ← SPLIT_BLOCK(target_block, R)
// Update index: may need new entry for new block
IF block split created new anchor:
INSERT_INDEX_ENTRY(S, block2.anchor, block2.ptr)
Key Insight:
- Inserting within a block's key range requires NO index update (unless block splits)
- Only block splits trigger index modifications
- This is dramatically fewer index writes than dense indexing
Sparse indexes require FAR fewer modifications than dense indexes. Most record-level changes don't affect the index at all—only block-level structural changes (splits, merges, anchor deletions) trigger index updates. This makes sparse indexes ideal for write-heavy workloads on the clustering column.
Multi-Level Sparse Indexes
Even sparse indexes can grow large for massive datasets. The solution is multi-level indexing—applying the sparse index concept recursively to create a hierarchy.
The Multi-Level Concept:
If a sparse index has too many entries to search efficiently, treat the index itself as a 'data file' and build another sparse index on top of it:
MULTI-LEVEL SPARSE INDEX HIERARCHY:
┌─────────────────────────────────────────────────────────────────────────────────────┐
│ Level 2 (Master Index): [A001 → L1.Block0] [A500 → L1.Block1] [A999 → L1.Block2] │
│ (3 entries) │
└─────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────────────────────────┐
│ Level 1 (Outer Index): │
│ Block 0: [A001→D.B0] [A050→D.B1] [A100→D.B2] [A150→D.B3] ... │
│ Block 1: [A500→D.B10] [A550→D.B11] [A600→D.B12] [A650→D.B13] ... │
│ Block 2: [A999→D.B20] [A1100→D.B21] ... │
│ (many entries per block) │
└─────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────────────────────────┐
│ Level 0 (Data File): │
│ Block 0: [A001, data] [A002, data] [A003, data] ... │
│ Block 1: [A050, data] [A051, data] [A052, data] ... │
│ ... │
│ (actual records) │
└─────────────────────────────────────────────────────────────────────────────────────┘
Height Analysis:
For a data file with $n$ records organized into $b$ data blocks:
- Level 0 (Data): $b$ blocks
- Level 1 (Index): $b / f$ blocks (where $f$ = index entries per block, the fanout)
- Level 2 (Index): $b / f^2$ blocks
- Level $k$: $b / f^k$ blocks
Height $h$ where top level has 1 block: $$h = \lceil \log_f(b) \rceil$$
Example: With $b = 1,000,000$ data blocks and $f = 500$ entries per index block: $$h = \lceil \log_{500}(1,000,000) \rceil = \lceil 2.2 \rceil = 3$$
Three index levels can handle a million blocks—a trillion record table with reasonable block sizes.
Multi-level sparse indexes are essentially the conceptual foundation of B-trees and B+trees. The B+tree leaf level is analogous to the first-level sparse index, with internal nodes forming additional index levels. Understanding multi-level sparse indexes provides intuition for B+tree height and performance characteristics.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.