Search Efficiency

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.

Let's establish the theoretical time complexity for search operations on each index type, distinguishing between in-memory and disk-based scenarios.

Notation:

• $n$ = number of records
• $b$ = number of data blocks = $n / b_f$
• $b_f$ = blocking factor (records per block)
• $i_f$ = index fanout (entries per index block)

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)

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.

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)       │
└─────────────────────────────────────────────────────────────────────┘

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:

Key Insight:

• Sparse indexes REQUIRE clustering (sorted data)
• Dense indexes CAN be either clustered or non-clustered
• Non-clustered indexes MUST be dense

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.

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)

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

Why Sparse Indexes Have Lower Write Overhead:

1. Fewer Index Entries: With 100 records per block, only 1 in 100 inserts affects the index (when blocks split).

2. Smaller Index Structure: Fewer entries mean smaller B-tree, fewer potential splits, less I/O.

3. Batch Amortization: Many inserts into the same block are 'free' from the index perspective—only the data block is modified.

4. 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.

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.

When Optimizers Prefer Each Approach:

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.