Space Trade-off

The choice between dense and sparse indexing fundamentally trades storage space for search simplicity. Dense indexes provide direct record access at the cost of larger size; sparse indexes achieve dramatic space savings by requiring an additional block-scan step.

This page develops a quantitative framework for analyzing this trade-off. By understanding the mathematical relationships between record count, block size, entry size, and index dimensions, you'll be able to make informed decisions about index design and accurately predict storage requirements.

Let's establish the mathematical foundation for index size analysis. We'll define precise notation and derive the core formulas.

Variable Definitions:

Dense Index Size:

A dense index contains exactly $n$ entries (one per record):

$$S_{dense} = n \times E \text{ bytes}$$

Number of index blocks:

$$b_{dense} = \lceil n / i_f \rceil$$

Sparse Index Size:

A sparse index contains exactly $b$ entries (one per data block):

$$S_{sparse} = b \times E = \lceil n / b_f \rceil \times E \text{ bytes}$$

Number of index blocks:

$$b_{sparse} = \lceil b / i_f \rceil = \left\lceil \frac{n}{b_f \times i_f} \right\rceil$$

Let's apply these formulas to a realistic e-commerce scenario to see the concrete implications.

Scenario: Order History Table

Table: orders
├── order_id (BIGINT):       8 bytes    ← Primary Key
├── customer_id (BIGINT):    8 bytes
├── order_date (TIMESTAMP):  8 bytes
├── status (VARCHAR(20)):   21 bytes
├── total_amount (DECIMAL): 16 bytes
├── shipping_address:       100 bytes (avg)
├── billing_address:        100 bytes (avg)
├── metadata (JSON):        200 bytes (avg)
├── Row overhead:            20 bytes
└── TOTAL RECORD SIZE:      481 bytes ≈ 500 bytes

Configuration:
├── Record count (n):        50,000,000 (50 million orders)
├── Block size (B):          8,192 bytes (8 KB)
├── Key size (K):            8 bytes (BIGINT order_id)
├── Pointer size (P):        8 bytes
└── Entry size (E):          16 bytes

Calculations:

Step 1: Data File Metrics

Blocking factor: b_f = ⌊8192 / 500⌋ = 16 records/block
Data blocks: b = ⌈50,000,000 / 16⌉ = 3,125,000 blocks
Data file size: 3,125,000 × 8 KB = 25 GB

Step 2: Dense Index Size

Dense entries: n = 50,000,000
Dense index size: 50,000,000 × 16 bytes = 800 MB
Index blocking factor: i_f = ⌊8192 / 16⌋ = 512 entries/block
Dense index blocks: ⌈50,000,000 / 512⌉ = 97,657 blocks

Step 3: Sparse Index Size

Sparse entries: b = 3,125,000
Sparse index size: 3,125,000 × 16 bytes = 50 MB
Sparse index blocks: ⌈3,125,000 / 512⌉ = 6,104 blocks

The blocking factor ($b_f$ = records per block) is the key determinant of sparse index efficiency. Let's analyze how record size and block size interact to affect this crucial ratio.

Blocking Factor Formula:

$$b_f = \left\lfloor \frac{B}{R} \right\rfloor$$

where:

• $B$ = block size
• $R$ = record size

Space Compression Ratio:

$$\text{Compression} = \frac{\text{Dense Size}}{\text{Sparse Size}} = b_f = \left\lfloor \frac{B}{R} \right\rfloor$$

Higher blocking factors yield greater sparse index advantages.

Analysis Insights:

1. Small Records Favor Sparse: With 50-byte records and 8KB blocks, sparse indexes are 163× smaller than dense. The space savings are dramatic.

2. Large Records Diminish Advantage: With 2000-byte records and 4KB blocks, only 2 records fit per block, making sparse indexes only 2× smaller. The advantage becomes marginal.

3. Block Size Scaling: Larger blocks increase blocking factor linearly, amplifying sparse index advantages proportionally.

4. Threshold Consideration: When $b_f < 10$, the sparse index advantage may not justify the two-phase search overhead in some workloads.

While the dense-to-sparse ratio depends only on blocking factor, the absolute size of both indexes scales with key size. This has significant practical implications.

Key Observations:

1. String UUIDs Cost 4× Integer Keys: A table using string UUIDs (36 bytes) instead of integers (4 bytes) sees its dense index grow from 120 MB to 440 MB—a 3.7× increase.

2. Index Fanout Degrades: Larger keys mean fewer entries per index block. With 44-byte entries in 8KB blocks, fanout drops to 186 (vs 682 for 12-byte entries). This increases B-tree height.

3. Composite Keys Compound: Multi-column keys add sizes together. A composite key on (customer_id, order_id, product_id) with three BIGINTs creates 24-byte keys.

4. Sparse Still Proportional: Despite larger absolute sizes, the sparse-to-dense ratio remains constant at 1:80 (for 80 records/block). Sparse indexing benefits persist across key sizes.

Real index structures like B-trees are multi-level. Understanding the total storage across all levels provides a complete picture of index overhead.

Multi-Level Size Formula:

For a multi-level sparse index with fanout $f$ (entries per index block):

$$\text{Total Index Blocks} = \sum_{i=1}^{h} \left\lceil \frac{b}{f^i} \right\rceil$$

This is a geometric series. For large $f$, approximation:

$$\text{Total Blocks} \approx \frac{b}{f-1}$$

Example Calculation:

Scenario:
├── Data blocks (b):         1,000,000
├── Index fanout (f):        500 entries/block
└── Block size:              8 KB

Level 1: ⌈1,000,000 / 500⌉     = 2,000 blocks
Level 2: ⌈2,000 / 500⌉         = 4 blocks  
Level 3: ⌈4 / 500⌉             = 1 block (root)

Total index blocks:            2,005 blocks
Total index size:              2,005 × 8 KB ≈ 16 MB

Overhead ratio: 16 MB / (1M × 8 KB) = 16 MB / 8 GB = 0.2%

Dense vs Sparse Multi-Level Comparison:

Same 1M block scenario:

SPARSE (indexing blocks):
├── Base entries:        1,000,000
├── Level 1 entries:     2,000
├── Level 2 entries:     4
├── Total entries:       1,002,004
└── Total size:          ~16 MB

DENSE (indexing records with b_f = 100):
├── Base entries:        100,000,000 (n = b × b_f)
├── Level 1 entries:     200,000
├── Level 2 entries:     400
├── Level 3 entries:     1
├── Total entries:       100,200,401
└── Total size:          ~1.6 GB

Ratio: 1.6 GB / 16 MB = 100:1

The 100:1 ratio matches the blocking factor ($b_f = 100$), confirming multi-level overhead is proportionally distributed.

Index size directly impacts memory utilization. When indexes exceed available buffer pool memory, performance degrades dramatically. This section analyzes the memory implications of the dense/sparse choice.

The Memory Threshold Effect:

Performance Curve:

  Response        │
  Time (ms)       │
                  │
       50 ────────│─────────────────╮
                  │                 │
       40 ────────│                 │
                  │                 │
       30 ────────│                 │
                  │                 │
       20 ────────│                 ╰─────────────────
                  │   ┌───────────────┐
       10 ────────│───│ Index fits in │
                  │   │    memory     │
        0 ────────┼───┴───────────────┴───────────────
                  │         │               │
             Index Size   Buffer      Memory
                          Pool        Threshold

When the index fits in memory: sub-millisecond lookups. When it doesn't: disk I/O adds 5-20ms per access.

Analysis:

At 500M records, the dense index (8 GB) exceeds the 4 GB buffer pool. Index operations now require disk I/O, increasing latency 100-1000×.

The sparse index (100 MB) fits comfortably, maintaining in-memory performance even at 10 billion records.

Working Set Consideration:

Not all index entries are accessed equally. An index has a 'hot' working set of frequently accessed entries. If this working set fits in memory, performance remains acceptable even with a larger total index:

Working Set Size ≈ (Hot Key Fraction) × (Index Size)

Example:
├── 500M records, dense index = 8 GB
├── 1% of keys are frequently accessed
├── Working set = 80 MB (fits!)
└── Acceptable performance for hot queries

Beyond storage size, we must analyze the I/O cost of searches. Sparse indexes trade smaller size for additional search steps. Let's quantify this trade-off.

I/O Cost Models:

Dense Index Point Query:

I/O = (Index Height) + 1 (data block)
    = ⌈log_f(n)⌉ + 1

Where f = index fanout (entries per block)

Sparse Index Point Query:

I/O = (Index Height) + 1 (data block) + 0 (no extra scan if in-memory)
    = ⌈log_f(b)⌉ + 1

Where b = number of data blocks = n / b_f

Since $b = n / b_f$:

Dense:  ⌈log_f(n)⌉ + 1
Sparse: ⌈log_f(n/b_f)⌉ + 1 = ⌈log_f(n) - log_f(b_f)⌉ + 1

The difference is approximately $log_f(b_f)$, which is typically less than 1 for reasonable fanouts and blocking factors.

Key Insight:

The I/O difference between dense and sparse indexes is typically at most 1 block read for the index traversal, plus the in-block scan time (microseconds in memory).

Given that:

• One random disk I/O ≈ 5-10 ms (HDD) or 0.1-0.5 ms (SSD)
• In-memory block scan ≈ 1-10 μs

The 'extra cost' of sparse indexes is negligible—often invisible in latency measurements.

The Real Trade-off:

The true benefit of sparse indexes isn't saving one index I/O—it's keeping the entire index in memory when a dense index would spill to disk. This can mean the difference between:

• Sparse: 0.1 ms (all in-memory)
• Dense: 10-50 ms (disk I/O required)