Multi-Level Index Structures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

Point Query Cost Analysis
==========================
 
Scenario: SELECT * FROM customers WHERE customer_id = 5000000
 
Index structure:
  - 10 million records
  - Fanout: 250 entries per block
  - Tree height: 3 levels
  - Index type: B+-tree (data pointers in leaves only)
 
Search path:
 
Step 1: Read root block (Level 3)
  - 1 I/O operation
  - Find entry where K < 5,000,000 ≤ K'
  - Binary search within block: ~8 comparisons (log₂ 250)
  - CPU time: ~1 microsecond
  - Disk time: 0.1ms (SSD) or 10ms (HDD)
  
Step 2: Read internal block (Level 2)
  - Follow pointer from Step 1
  - 1 I/O operation
  - Binary search: ~8 comparisons
  - Disk time: 0.1ms (SSD) or 10ms (HDD)
  
Step 3: Read leaf block (Level 1)
  - Follow pointer from Step 2
  - 1 I/O operation
  - Binary search: ~8 comparisons
  - Find exact entry for customer_id = 5,000,000
  - Disk time: 0.1ms (SSD) or 10ms (HDD)
  
Step 4: Read data block (Level 0)
  - Follow data pointer from leaf entry
  - 1 I/O operation
  - Retrieve actual customer record
  - Disk time: 0.1ms (SSD) or 10ms (HDD)
 
TOTAL COST:
                   Cold Cache    Warm Cache (upper levels cached)
  I/O operations:      4              2 (Level 3+2 cached)
  SSD latency:      0.4 ms          0.2 ms
  HDD latency:      40 ms           20 ms
  CPU time:         ~4 µs           ~4 µs (negligible)
 
The dominant cost is ALWAYS disk I/O.
CPU time for in-block binary search is <0.01% of total time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

def range_query_cost(
    start_key: int,
    end_key: int,
    total_records: int,
    fanout: int,
    records_per_data_block: int,
    selectivity: float = None  # Fraction of records in range
) -> dict:
    """
    Calculate I/O cost for a range query.
    
    Parameters:
    - start_key, end_key: Range boundaries
    - total_records: Total records in table
    - fanout: Index entries per block
    - records_per_data_block: Data records per block
    - selectivity: Fraction of records matching (if known)
    
    Returns:
    - Dictionary with cost breakdown
    """
    import math
    
    # Tree height
    height = math.ceil(math.log(total_records) / math.log(fanout))
    
    # Calculate selectivity if not provided
    if selectivity is None:
        key_range = end_key - start_key
        total_key_range = total_records  # Assume keys are 1 to n
        selectivity = key_range / total_key_range
    
    # Records in range
    records_in_range = int(total_records * selectivity)
    
    # Leaf blocks to scan
    # Each leaf block has 'fanout' entries
    leaf_blocks_scanned = math.ceil(records_in_range / fanout)
    
    # Data blocks to access
    # Best case: data is clustered, sequential
    # Worst case: each record in different block
    clustered_data_blocks = math.ceil(records_in_range / records_per_data_block)
    unclustered_data_blocks = records_in_range  # One per record
    
    return {
        'tree_traversal_ios': height,
        'leaf_scan_ios': leaf_blocks_scanned,
        'data_access_ios_clustered': clustered_data_blocks,
        'data_access_ios_unclustered': unclustered_data_blocks,
        'total_ios_clustered': height + leaf_blocks_scanned + clustered_data_blocks,
        'total_ios_unclustered': height + leaf_blocks_scanned + unclustered_data_blocks,
        'records_returned': records_in_range,
    }
 
 
# Example: Find orders from Jan 2024 (assume 5% of 1 million orders)
cost = range_query_cost(
    start_key=20240101,
    end_key=20240131,
    total_records=1_000_000,
    fanout=250,
    records_per_data_block=20,
    selectivity=0.05
)
 
print(f"""
Range Query: Orders from January 2024
=====================================
Records in range: {cost['records_returned']:,}
Tree traversal: {cost['tree_traversal_ios']} I/Os
 
Clustered index (orders sorted by date):
  Leaf scan: {cost['leaf_scan_ios']} I/Os
  Data access: {cost['data_access_ios_clustered']} I/Os
  TOTAL: {cost['total_ios_clustered']} I/Os
 
Non-clustered index (orders NOT sorted by date):
  Leaf scan: {cost['leaf_scan_ios']} I/Os
  Data access: {cost['data_access_ios_unclustered']:,} I/Os
  TOTAL: {cost['total_ios_unclustered']:,} I/Os
""")
 
# Output:
# Records in range: 50,000
# Tree traversal: 3 I/Os
# 
# Clustered index: TOTAL: 2,703 I/Os
# Non-clustered index: TOTAL: 50,203 I/Os  (20x worse!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

Buffer Pool Impact Analysis
============================
 
Database: 10 million records, B+-tree index
Block size: 4 KB
Fanout: 250
 
Index structure:
  Level 3 (Root):     1 block = 4 KB
  Level 2:           40 blocks = 160 KB
  Level 1 (Leaves): 40,000 blocks = 160 MB
  Data:            500,000 blocks = 2 GB
 
SCENARIO 1: Tiny buffer pool (1 MB)
-----------------------------------
Can cache: Root + Level 2 + ~200 hot leaf blocks
Hit rate estimate:
  - Root: 100% (always cached)
  - Level 2: 100% (fits entirely)
  - Level 1: ~0.5% (200/40,000 if uniform access)
  - Data: ~0% (essentially no caching)
  
Average I/Os per point query: ~3 (leaf + data + maybe some misses)
 
 
SCENARIO 2: Moderate buffer pool (200 MB)
-----------------------------------------
Can cache: Root + Level 2 + All leaves + ~10,000 hot data blocks
Hit rate estimate:
  - Root: 100%
  - Level 2: 100%
  - Level 1: 100% (all 160 MB cached!)
  - Data: ~2% uniform, or higher with locality
  
Average I/Os per point query: ~1-1.5 (mostly just data access)
 
 
SCENARIO 3: Large buffer pool (500 MB)
--------------------------------------
Can cache: Entire index + 25% of data
Hit rate estimate:
  - All index levels: 100%
  - Data: ~25% uniform, higher with locality
  
Average I/Os per point query: ~0.75 (many fully cached)
 
 
SCENARIO 4: Huge buffer pool (3 GB)
-----------------------------------
Can cache: Everything (index + all data)
Hit rate estimate: 100%
 
Average I/Os per point query: 0 (all in memory)
 
 
KEY INSIGHT: The marginal value of buffer pool memory is non-linear.
  - First 1 MB: Critical (caches upper index levels)
  - 1-200 MB: High value (caches all index leaves)
  - 200 MB - 2 GB: Moderate value (caches data)
  - Beyond data size: No additional value
 
Prioritize buffer pool sizing for:
  1. Upper index levels (mandatory)
  2. Leaf levels of hot indexes
  3. Hot data pages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

-- Access Method Comparison: Concrete Examples
-- Table: orders (10 million rows, 200 bytes each)
-- Total data: ~2 GB (500,000 blocks at 4 KB)
 
-- QUERY 1: Point lookup
-- SELECT * FROM orders WHERE order_id = 5000000
 
-- Access Method        I/O Operations   Time (SSD)   Time (HDD)
-- ------------------- ----------------- ------------ ------------
-- Full Scan            500,000           50 sec       83 min
-- Hash Index           1-2               0.2 ms       20 ms
-- B+-Tree Index        4                 0.4 ms       40 ms
 
 
-- QUERY 2: Range query (5% selectivity)
-- SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31'
 
-- Access Method        I/O Operations   Time (SSD)   Time (HDD)
-- ------------------- ----------------- ------------ ------------
-- Full Scan            500,000           50 sec       83 min
-- Hash Index           N/A (no range!)   Cannot use   Cannot use
-- B+-Tree (clustered)  27,000            2.7 sec      4.5 min
-- B+-Tree (non-clust.) 502,000           50 sec       84 min
 
 
-- QUERY 3: High-selectivity range (90% of table)
-- SELECT * FROM orders WHERE order_date >= '2023-01-01'
 
-- Access Method        I/O Operations   Time (SSD)   Time (HDD)
-- ------------------- ----------------- ------------ ------------
-- Full Scan            500,000           50 sec       83 min
-- B+-Tree (clustered)  450,000           45 sec       75 min
-- B+-Tree (non-clust.) 9,000,000+        15 min+      25 hours+
 
-- For high selectivity, full scan wins over non-clustered index!
-- The optimizer should (and usually does) choose full scan here.
 
 
-- QUERY 4: AND of multiple conditions
-- SELECT * FROM orders WHERE status = 'shipped' AND region = 'west'
 
-- Access Method        I/O Operations (if each selects 20%)
-- ------------------- ------------------------------------------
-- Full Scan            500,000 (but can evaluate both predicates)
-- Single B+-Tree       100,000 (one index) + filter in memory
-- Bitmap Index         ~500 (if low cardinality, bitmap AND is fast)
-- Two B+-Tree indexes  Intersection: ~20,000 (if supported)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

-- Demonstrating index fragmentation impact
 
-- Check fragmentation in SQL Server
SELECT 
    object_name(ips.object_id) as table_name,
    i.name as index_name,
    ips.avg_fragmentation_in_percent,
    ips.page_count,
    ips.avg_page_space_used_in_percent
FROM sys.dm_db_index_physical_stats(
    DB_ID(), NULL, NULL, NULL, 'DETAILED'
) ips
JOIN sys.indexes i ON ips.object_id = i.object_id 
    AND ips.index_id = i.index_id
WHERE ips.avg_fragmentation_in_percent > 10;
 
-- Example output:
-- table_name   index_name      fragmentation%   pages    space_used%
-- ----------- --------------- ---------------- -------- -----------
-- orders      ix_order_date   45.2             125000   62.3
-- customers   pk_customer_id   8.7              5000    91.4
 
-- The orders index is heavily fragmented:
--   - 45% fragmentation means pages are not contiguous
--   - 62% space used means 38% wasted space (from splits/deletes)
--   
-- Impact:
--   - Range scans read 1.6x more blocks (1/0.62) 
--   - Sequential scans become random I/O
--   
-- Solution: Rebuild or reorganize the index
ALTER INDEX ix_order_date ON orders REBUILD;
 
 
-- PostgreSQL equivalent
SELECT 
    schemaname,
    tablename,
    indexname,
    pg_size_pretty(pg_relation_size(indexrelid)) as index_size
FROM pg_stat_user_indexes;
 
-- Check bloat (fragmentation) with pgstattuple extension
SELECT * FROM pgstattuple('orders_pkey');
-- Returns: dead_tuple_percent, free_space, etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

-- Covering Index Example: Eliminating Data Block Access
 
-- Original query
SELECT customer_id, order_date, total_amount
FROM orders
WHERE customer_id = 12345
ORDER BY order_date DESC
LIMIT 10;
 
-- Without covering index:
-- 1. Search B+-tree on customer_id (3-4 I/Os)
-- 2. For each matching row, access data block to get order_date, total_amount
-- 3. If customer has 100 orders: potentially 100 additional I/Os!
 
-- With covering index:
CREATE INDEX ix_orders_covering ON orders 
    (customer_id, order_date DESC) 
    INCLUDE (total_amount);
 
-- Now:
-- 1. Search B+-tree on customer_id (3-4 I/Os)  
-- 2. All needed columns are IN THE INDEX - no data block access needed
-- 3. Range scan within index for limit 10: maybe 1 additional leaf block
 
-- Result: 4-5 I/Os instead of 100+ I/Os
 
-- Trade-off: Index is larger (includes total_amount)
-- But for frequently-executed queries, this is almost always worth it
 
-- EXPLAIN ANALYZE will show "Index Only Scan" when covering works
EXPLAIN ANALYZE
SELECT customer_id, order_date, total_amount
FROM orders  
WHERE customer_id = 12345
ORDER BY order_date DESC
LIMIT 10;
 
-- Good output indicates:
-- "Index Only Scan using ix_orders_covering"
-- "Heap Fetches: 0" (no data block access needed)