Loading learning content...
While the previous page quantified storage differences, choosing between dense and sparse indexes ultimately depends on search performance. Storage is consumed once; searches happen millions of times.
This page dissects search efficiency from multiple angles: theoretical time complexity, practical I/O patterns, query type performance (point vs range), and real-world factors that influence which index structure delivers superior performance for specific workloads.
By the end of this page, you will understand the precise time complexity of search operations on dense and sparse indexes, analyze performance across different query types, recognize when in-memory vs I/O-bound behavior dominates, and predict which index structure optimizes specific workload patterns.
Let's establish the theoretical time complexity for search operations on each index type, distinguishing between in-memory and disk-based scenarios.
Notation:
Dense Index Point Query:
In-Memory:
├── Binary search over n entries
├── Comparisons: O(log n)
├── Data fetch: O(1) direct pointer
└── Total: O(log n)
Disk-Based (with B-tree structure):
├── Tree height: h = ⌈log_{i_f}(n)⌉
├── I/O operations: h index blocks + 1 data block
├── Total I/O: O(log_{i_f} n) + O(1) = O(log n)
└── Actual I/O: typically 3-5 reads for billion-record tables
Sparse Index Point Query:
In-Memory:
├── Binary search over b entries: O(log b)
├── Block scan for record: O(b_f) in-memory
├── Total: O(log b + b_f) = O(log n + b_f)
└── Practically: O(log n) since b_f is constant
Disk-Based:
├── Tree height over blocks: h = ⌈log_{i_f}(b)⌉
├── I/O: h index blocks + 1 data block (scanned in memory)
├── Total I/O: O(log_{i_f} b) + O(1)
├── Since b = n/b_f: O(log_{i_f}(n/b_f)) = O(log n - log b_f)
└── Actual I/O: typically 2-4 reads (1 less than dense)
| Operation | Dense Index | Sparse Index | Difference |
|---|---|---|---|
| Point Query (memory) | O(log n) | O(log b + b_f) | Negligible |
| Point Query (disk) | O(log n) I/Os | O(log b) + 1 I/Os | ~1 fewer I/O |
| Range Query (k results) | O(log n + k) | O(log b + k) | Same for large k |
| Index Scan (full) | O(n) | O(b) | b_f × faster |
Both index types have O(log n) point query complexity. The practical difference is constant factors: sparse indexes have ~1 fewer I/O per query but add an in-memory block scan (~1-10 μs). With SSDs at 0.1-0.5 ms per I/O, the sparse index 'wins' unless fully memory-resident.
Point queries (SELECT * FROM table WHERE key = ?) are the most common index use case. Let's analyze the complete execution path for each index type.
Dense Index Execution Path:
Query: SELECT * FROM employees WHERE employee_id = 12345
Step 1: Root Node Access
├── Load root block from index (maybe cached)
├── Binary search: 12345 falls in child range [10000-20000]
├── Time: ~0.1 μs if cached, ~100 μs if disk
└── Navigate to Level 2
Step 2: Intermediate Node
├── Load intermediate block
├── Binary search: 12345 falls in child range [12000-13000]
├── Time: ~0.1 μs if cached, ~100 μs if disk
└── Navigate to Level 3 (leaf)
Step 3: Leaf Node
├── Load leaf block
├── Binary search: find entry (12345, ptr)
├── Time: ~0.1 μs if cached, ~100 μs if disk
└── Extract record pointer
Step 4: Data Access
├── Follow pointer to data block
├── Read record directly at slot position
├── Time: ~0.1 μs if cached, ~100 μs if disk
└── Return record
TOTAL (all cached): ~0.5 μs
TOTAL (all disk): ~400 μs
TOTAL (index cached, data on disk): ~100 μs
For tables where the dense index doesn't fit in memory but the sparse index does, sparse indexes deliver 10-100× better average query latency. The in-memory block scan (microseconds) is trivial compared to avoided disk I/O (milliseconds).
Range queries (SELECT * FROM table WHERE key BETWEEN x AND y) exhibit different performance characteristics based on data organization and index type.
Range Query Execution Patterns:
Query: SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31'
Assumes: 10M records total, 100K matching records
DENSE INDEX (data unsorted on order_date):
┌─────────────────────────────────────────────────────────────────────┐
│ Index Traversal: │
│ ├── Find first matching entry: O(log n) = ~4 I/Os │
│ └── Sequential scan of matching index entries: 100K entries │
│ │
│ Data Access: │
│ ├── Each index entry points to different data block │
│ ├── RANDOM I/O: potentially 100K separate block reads │
│ ├── With ~100 records/block, ~1000 unique blocks needed │
│ └── But accessed in random order (worst case) │
│ │
│ Result: ~1000 random I/Os = 5-10 seconds on HDD │
└─────────────────────────────────────────────────────────────────────┘
SPARSE INDEX (data sorted on order_date):
┌─────────────────────────────────────────────────────────────────────┐
│ Index Traversal: │
│ ├── Find first matching block: O(log b) = ~3 I/Os │
│ └── Index entries for range: 100K/100 = 1000 block entries │
│ │
│ Data Access: │
│ ├── Blocks are SEQUENTIAL in data file │
│ ├── SEQUENTIAL I/O: 1000 contiguous block reads │
│ └── Prefetching and read-ahead optimize throughput │
│ │
│ Result: ~1000 sequential I/Os = 0.5-1 seconds (10-20x faster) │
└─────────────────────────────────────────────────────────────────────┘
| Aspect | Dense on Unsorted | Sparse on Sorted | Advantage |
|---|---|---|---|
| Index traversal | O(log n + k) | O(log b + k/b_f) | Sparse (fewer entries) |
| I/O pattern | Random | Sequential | Sparse (10-100× faster I/O) |
| Read-ahead benefit | None | Full prefetch | Sparse |
| Cache utilization | Poor (random) | Excellent (spatial) | Sparse |
| Latency (1K blocks) | 5-10 sec (HDD) | 0.5-1 sec (HDD) | Sparse (10×) |
The performance difference isn't inherent to 'dense vs sparse'—it's about the relationship between index order and data order. Dense indexes on sorted data also get sequential I/O. However, since only ONE column can determine physical order, only the clustered (often sparse) index benefits from sequential access for range queries.
The crucial performance factor isn't dense vs sparse per se—it's whether the index has a clustering relationship with the data. Let's clarify this relationship.
Terminology Clarification:
| Term | Meaning | Index Density | Data Relationship |
|---|---|---|---|
| Dense Index | One entry per record | Dense | Either |
| Sparse Index | One entry per block | Sparse | Must be clustered |
| Clustered Index | Index order = data order | Usually sparse | Clustered (by definition) |
| Non-clustered Index | Index order ≠ data order | Must be dense | Non-clustered |
Key Insight:
The 'Tipping Point' for Non-Clustered Range Scans:
At some selectivity threshold, it becomes faster to scan the entire table than to use a non-clustered index:
Non-clustered index cost (per record): ~1 random I/O (if not clustered)
Table scan cost (per record): 1/(records per block) sequential I/O
Break-even when:
1 random I/O = (1/b_f) × b sequential I/Os
With: random I/O = 10× sequential throughput, b_f = 100
Break-even at: 1 = (1/100) × 10 × selectivity_ratio
selectivity_ratio = 10%
Rule of Thumb: Non-clustered indexes become inefficient when returning more than 5-15% of the table. Optimizers often switch to table scans at this threshold.
If the index contains all columns needed by the query (a 'covering index'), data file access is eliminated entirely. This makes non-clustered index range scans viable even at higher selectivity—since all access is sequential through the index itself.
When indexes fit entirely in memory, the performance equation changes dramatically. Disk I/O disappears, and CPU efficiency dominates.
In-Memory Search Comparison:
Scenario: 10M records, 256GB RAM (everything fits)
DENSE INDEX IN MEMORY:
├── Index size: 160 MB (fully cached)
├── Binary search: log₂(10,000,000) ≈ 23.25 comparisons
├── Direct pointer to record slot
├── Record access: 1 array lookup
└── Total time: ~0.3-0.5 μs
SPARSE INDEX IN MEMORY:
├── Index size: 2 MB (fully cached)
├── Binary search: log₂(100,000 blocks) ≈ 16.6 comparisons
├── Block identification: 1 lookup
├── Record scan: ~50 comparisons (half of 100 records/block)
└── Total time: ~0.5-1.0 μs
Difference: Dense is ~0.2-0.5 μs faster per query
Cache Line Efficiency:
CPU cache line: 64 bytes
Dense index entry: 16 bytes → 4 entries per cache line
Sparse index entry: 16 bytes → 4 entries per cache line
Binary search cache misses:
├── Each comparison may miss cache: ~100 cycles penalty
├── Dense: ~23 comparisons → up to 23 cache misses
├── Sparse: ~17 comparisons + ~50 in-block → may batch better
In-block scan advantage:
├── Block is contiguous in memory
├── Sequential access: CPU prefetcher effective
├── 100 records × 500 bytes = 50 KB scanned
├── Sequential scan: ~100 cycles per comparison
└── Highly cache-efficient (temporal locality)
| Metric | Dense Index | Sparse Index | Winner |
|---|---|---|---|
| Point query latency | 0.3-0.5 μs | 0.5-1.0 μs | Dense (2×) |
| Memory footprint | ~160 MB | ~2 MB | Sparse (80×) |
| L3 cache fit (30MB) | No | Yes | Sparse |
| Cache miss rate | Higher | Lower | Sparse |
| Queries per second | ~2-3M | ~1-2M | Dense (~1.5×) |
Dense indexes are faster when both indexes fit in L3 cache. But sparse indexes are more likely to fit in L3, making them faster for 'medium' data sizes. At very large scales, neither fits—and disk I/O dominates, where sparse wins due to smaller footprint.
Search efficiency is only half the picture. Index maintenance during writes significantly impacts overall system performance, especially for write-heavy workloads.
Insertion Cost Comparison:
DENSE INDEX INSERTION:
├── Find insertion point: O(log n) [same as search]
├── Create new index entry: O(1)
├── Insert into B-tree leaf: O(1) amortized
│ └── May trigger node split: O(log n) worst case
├── Write data record: O(1)
└── Total: O(log n) + potential split cascade
Every record insertion modifies the index.
---
SPARSE INDEX INSERTION:
├── Find correct block: O(log b) [fewer entries to search]
├── Insert into data block: O(1) if space available
│ ├── In-block position: sorted insert
│ └── Shift existing records: O(b_f) in-memory
├── IF block full:
│ ├── Split block: O(b_f)
│ └── Add new index entry: O(log b)
│ └── May trigger index node split: O(log b)
├── IF block not full:
│ └── NO INDEX MODIFICATION NEEDED
└── Total: O(log b + b_f) typical, O(log b) index writes amortized
| Metric | Dense Index | Sparse Index | Ratio |
|---|---|---|---|
| Index writes per record insert | 1 (always) | ~0.01 (1%) | 100:1 |
| B-tree splits per 1M inserts | ~2,000 | ~20 | 100:1 |
| Write I/O amplification | ~3-5× | ~1.5-2× | ~2:1 |
| Append-optimized throughput | ~50K/sec | ~200K/sec | 4:1 |
Why Sparse Indexes Have Lower Write Overhead:
Fewer Index Entries: With 100 records per block, only 1 in 100 inserts affects the index (when blocks split).
Smaller Index Structure: Fewer entries mean smaller B-tree, fewer potential splits, less I/O.
Batch Amortization: Many inserts into the same block are 'free' from the index perspective—only the data block is modified.
Sequential Insert Optimization: Appending to sorted data (e.g., auto-increment IDs, timestamps) causes splits only at the 'end' of the index, avoiding random writes.
For time-series and log data (always appended in timestamp order), sparse indexes on the timestamp column achieve near-zero index maintenance. New records always go to the last block, and index updates only occur during block splits—approximately once every b_f records.
Database query optimizers must decide when to use indexes and which index to choose. Understanding optimizer logic helps you design effective indexes.
Optimizer Cost Model (Simplified):
Cost(table_scan) =
block_count × seq_io_cost +
record_count × cpu_tuple_cost
Cost(index_scan_dense) =
log(n) × random_io_cost + // index traversal
selectivity × n × random_io_cost + // data block reads
selectivity × n × cpu_tuple_cost // tuple processing
Cost(index_scan_clustered) =
log(b) × random_io_cost + // index traversal
selectivity × b × seq_io_cost + // sequential data reads
selectivity × n × cpu_tuple_cost // tuple processing
Optimizer chooses plan with LOWEST estimated cost.
| Parameter | Value | Meaning |
|---|---|---|
| seq_page_cost | 1.0 | Sequential I/O cost unit |
| random_page_cost | 4.0 | Random I/O (4× sequential) |
| cpu_tuple_cost | 0.01 | Processing one row |
| cpu_index_tuple_cost | 0.005 | Processing one index entry |
| cpu_operator_cost | 0.0025 | Evaluating an operator |
When Optimizers Prefer Each Approach:
| Selectivity | Clustered Index | Non-Clustered Index | Table Scan |
|---|---|---|---|
| < 1% | ✓ Preferred | ✓ Preferred | ✗ |
| 1-5% | ✓ Preferred | ✓ Often used | ✗ |
| 5-15% | ✓ Preferred | ⚠ Depends | ⚠ May be chosen |
| 15-30% | ✓ Preferred | ✗ Too expensive | ⚠ May be chosen |
30% | ⚠ Depends | ✗ Too expensive | ✓ Preferred |
Key Insight: Clustered/sparse indexes remain attractive at much higher selectivity because sequential I/O amortizes the access cost. Non-clustered dense indexes quickly become worse than table scans.
Sometimes optimizer statistics are stale and index hints are needed. In PostgreSQL, use enable_seqscan = off temporarily. In MySQL, use FORCE INDEX. But first, ensure statistics are current (ANALYZE TABLE) and the optimizer isn't making a better choice than you think.
Theory informs design; benchmarks validate it. Here are representative performance numbers from real database deployments.
| Operation | Clustered/Sparse | Secondary/Dense | Ratio |
|---|---|---|---|
| Point lookup (hot) | 0.2 ms | 0.3 ms | 1.5× |
| Point lookup (cold) | 2 ms | 8 ms | 4× |
| Range (100 rows) | 1 ms | 15 ms | 15× |
| Range (10K rows) | 50 ms | 800 ms | 16× |
| Insert (single) | 0.5 ms | 0.8 ms | 1.6× |
| Bulk insert (10K) | 200 ms | 800 ms | 4× |
Analysis of Results:
Hot Path (cached): Differences are small since I/O is eliminated. Dense indexes slightly faster due to direct pointer access.
Cold Path (uncached): Sparse/clustered indexes show significant advantage (4×) due to smaller index size and better cache utilization.
Range Queries: Dramatic advantage for clustered indexes (15-16×) due to sequential vs random I/O.
Write Operations: Clustered indexes faster for both single and bulk inserts due to lower write amplification.
Environment Notes:
These benchmarks represent one configuration. Results vary significantly based on: hardware (HDD vs SSD vs NVMe), memory (buffer pool size), workload (read/write ratio), data distribution (hot spots vs uniform), and database engine implementation. Always benchmark your specific scenario.
We've comprehensively analyzed search efficiency for dense and sparse indexes across multiple dimensions. Let's consolidate the key insights:
Looking Ahead:
With both storage and performance trade-offs thoroughly analyzed, we're prepared for the final synthesis: making the right choice between dense and sparse indexes for specific scenarios. The next page provides decision frameworks and best practices for real-world index design.
You now have a comprehensive understanding of search efficiency—the time complexity, I/O patterns, memory effects, and practical performance characteristics that differentiate dense and sparse indexes. Next, we'll synthesize this knowledge into actionable design guidelines.