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
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

def insert_into_btree(root: BTreeNode, key, data_pointer) -> BTreeNode:
    """
    Insert a key-pointer pair into a B+-tree.
    Returns the (possibly new) root node.
    
    This implementation uses a recursive descent with split propagation.
    Real databases often use iterative approaches with parent pointers.
    """
    
    def insert_recursive(node: BTreeNode, key, data_pointer):
        """
        Returns: (new_key, new_child) if split occurred, else (None, None)
        new_key: The separator key to insert in parent
        new_child: Pointer to the new sibling node created by split
        """
        
        if node.is_leaf:
            # Insert into leaf node
            insert_position = find_insert_position(node.keys, key)
            node.keys.insert(insert_position, key)
            node.data_pointers.insert(insert_position, data_pointer)
            
            if len(node.keys) > node.max_keys:
                # Overflow! Must split this leaf
                return split_leaf(node)
            else:
                return (None, None)  # No split needed
        
        else:
            # Internal node: find child and recurse
            child_index = find_child_index(node.keys, key)
            child = node.children[child_index]
            
            # Recursive insert into appropriate subtree
            (promoted_key, new_child) = insert_recursive(child, key, data_pointer)
            
            if promoted_key is not None:
                # A split occurred below - must insert separator here
                node.keys.insert(child_index, promoted_key)
                node.children.insert(child_index + 1, new_child)
                
                if len(node.keys) > node.max_keys:
                    # This internal node also overflows - split it too
                    return split_internal(node)
            
            return (None, None)
    
    # Start insertion from root
    (promoted_key, new_child) = insert_recursive(root, key, data_pointer)
    
    if promoted_key is not None:
        # Root was split - create new root
        new_root = BTreeNode(order=root.order, is_leaf=False)
        new_root.keys = [promoted_key]
        new_root.children = [root, new_child]
        return new_root
    
    return root  # Root unchanged
 
 
def split_leaf(node: BTreeNode):
    """
    Split an overflowing leaf node into two nodes.
    Returns: (separator_key, new_sibling)
    """
    mid = len(node.keys) // 2
    
    # Create new sibling with upper half of entries
    sibling = BTreeNode(order=node.order, is_leaf=True)
    sibling.keys = node.keys[mid:]
    sibling.data_pointers = node.data_pointers[mid:]
    
    # Original node keeps lower half
    node.keys = node.keys[:mid]
    node.data_pointers = node.data_pointers[:mid]
    
    # Maintain leaf sibling chain (for B+-tree)
    sibling.next_leaf = node.next_leaf
    node.next_leaf = sibling
    
    # Separator key: first key of new sibling (copied up)
    separator = sibling.keys[0]
    
    return (separator, sibling)
 
 
def split_internal(node: BTreeNode):
    """
    Split an overflowing internal node.
    Returns: (separator_key, new_sibling)
    
    Key difference from leaf split: separator is pushed up, not copied.
    """
    mid = len(node.keys) // 2
    
    # The middle key is pushed up to parent (not kept in either child)
    separator = node.keys[mid]
    
    # Create new sibling with upper half
    sibling = BTreeNode(order=node.order, is_leaf=False)
    sibling.keys = node.keys[mid + 1:]  # Skip the separator
    sibling.children = node.children[mid + 1:]
    
    # Original keeps lower half
    node.keys = node.keys[:mid]
    node.children = node.children[:mid + 1]
    
    return (separator, sibling)

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

Node Split Example
==================
 
Before insertion of key 35:
 
    Parent Node: [20 | 40 | 60]
                  /    |     \
                 v     v      v
        [10,15] [25,30,32,38] [45,50]
                 ^^^^^^^^
                 Target leaf (already full with 4 keys)
 
 
After inserting 35 (causes overflow → split):
 
Step 1: Insert 35 in sorted position
    [25, 30, 32, 35, 38]  ← 5 entries, overflow!
 
Step 2: Split leaf at midpoint
    [25, 30]  |  [32, 35, 38]
       ↑              ↑
    Original      New sibling
 
Step 3: Promote separator (32) to parent
    Parent Node: [20 | 32 | 40 | 60]
                  /    |    |     \
                 v     v    v      v
        [10,15] [25,30] [32,35,38] [45,50]
                 
Note: 
- Separator 32 is COPIED to parent (in B+-tree)
- Separator 32 remains in leaf (data pointer needed)
- Parent now has 4 keys (if max is 4, parent would also split)

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

Expected Insertion I/O Cost Calculation
========================================
 
Assumptions:
  - Tree height: h = 3
  - Fanout: f = 250
  - Node fill factor after splits: ~70% (empirical average)
 
Split probability at each level:
  P(leaf split) ≈ 1/f (one split per f insertions on average)
               ≈ 1/250 ≈ 0.4% per insertion
               
  But nodes aren't always full. With 70% fill factor:
  P(leaf split) ≈ 30% (room for ~75 more keys per leaf)
  
  Wait, this seems contradictory. Let's think more carefully:
  
  After many random insertions, nodes average ~69% full (ln(2) ≈ 0.693).
  Each node can hold f keys.
  Average keys per leaf: 0.69 × f ≈ 173 (for f=250)
  
  P(leaf split | insertion into this leaf):
    Depends on current fullness. On average, over long term:
    P(split) ≈ 1 / (keys per leaf) ≈ 1/173 ≈ 0.6%
    
  More accurately, considering that splits create two ~50% full nodes:
    Average split rate: ~ 1 / (0.5 × f) = 1/125 ≈ 0.8% per insertion
    
  P(parent split | leaf split) ≈ same logic ≈ 0.8%
  P(root split | parent split) ≈ 0.8%
  
 
Expected I/O Cost:
  E[I/O] = P(no split) × 4 + P(leaf split only) × 6 + P(cascade) × (6+)
  
  With p = 0.008 (0.8% split rate):
  E[I/O] ≈ (1-p) × 4 + p × (1-p) × 6 + p² × 8 + ...
         ≈ 0.992 × 4 + 0.00794 × 6 + 0.000064 × 8
         ≈ 3.968 + 0.048 + 0.0005
         ≈ 4.02 I/Os per insertion
 
RESULT: Expected insertion cost is only slightly above search cost!
  - Search: 3-4 I/Os (read only)
  - Insert: ~4 I/Os (mostly no split, occasional split overhead averages out)
 
This is remarkably efficient. The B-tree design minimizes overhead.

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

Deletion Example: Handling Underflow
=====================================
 
Tree parameters: Minimum 2 keys per leaf (max 4)
 
Initial state:
    Parent: [30 | 50]
            /   |    \
           v    v     v
    [10,20] [35,40] [55,60,70,80]
              ↑
    Delete key 40 from this leaf
 
 
Step 1: Delete 40
    [35] ← Only 1 key remaining, minimum is 2 → UNDERFLOW!
 
 
Step 2: Check siblings for redistribution
 
Option A: Borrow from right sibling (has 4 keys, can donate)
    Before: [35] and [55,60,70,80]
    After:  [35,55] and [60,70,80]
    Parent separator changes: 50 → 60
    
    Result:
        Parent: [30 | 60]
                /   |    \
               v    v     v
        [10,20] [35,55] [60,70,80]
    
    I/O: 1 read (sibling) + 3 writes (leaf, sibling, parent) = 4 I/Os
 
 
Option B: Borrow from left sibling (has 2 keys, can donate 1)
    Before: [10,20] and [35]
    After:  [10] and [20,35]
    Parent separator changes: 30 → 20
    
    But wait: [10] now has only 1 key → left sibling underflows!
    Would need to borrow from ITS sibling, or merge.
    
    In this case, borrowing from right is better (more keys available).
 
 
What if sibling can't donate?
============================
 
Scenario: Delete from [35,40] when right sibling has only [55,60]
 
After deleting 40: [35] ← underflow
Right sibling [55,60] has exactly minimum, can't donate
 
Must MERGE:
    [35] + [55,60] + separator(50) → [35,50,55,60]
    
    Before merge:
        Parent: [30 | 50]
                /   |    \
               v    v     v
        [10,20] [35] [55,60]
    
    After merge:
        Parent: [30]
                /    \
               v      v
        [10,20] [35,50,55,60]
    
    I/O: 1 read + 3 writes (leaf gone, sibling modified, parent modified)
 
Note: Parent lost a key. If parent underflows, cascade merge upward.
If root ends up with 0 keys, tree height decreases by 1.

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

-- Update Operation Examples
 
-- Table: customers with clustered index on customer_id
-- Non-clustered index on (last_name, first_name)
 
-- SCENARIO 1: Non-key update on non-indexed column
UPDATE customers 
SET email = 'new@email.com' 
WHERE customer_id = 12345;
 
-- Index impact: NONE
-- Clustered index used to find row (3-4 I/Os)
-- Only data page modified
-- last_name index: unchanged
-- Total: 4 I/Os (same as point query + 1 write)
 
 
-- SCENARIO 2: Non-key update on indexed column (not key)
-- Assume covering index: (customer_id) INCLUDE (status)
UPDATE customers 
SET status = 'active' 
WHERE customer_id = 12345;
 
-- Index impact: Update index entry to change status value
-- Find entry: 3-4 I/Os
-- Modify leaf entry in place: 1 write
-- Total: 4-5 I/Os
 
 
-- SCENARIO 3: Key update (changing primary key - rare!)
UPDATE customers 
SET customer_id = 99999 
WHERE customer_id = 12345;
 
-- Index impact: MAJOR
-- 1. Delete old entry for customer_id = 12345
--    - Search: 3 I/Os
--    - Delete from leaf: 1 write
--    - Potential underflow handling: 0-4 more I/Os
-- 
-- 2. Insert new entry for customer_id = 99999
--    - Search: 3 I/Os  
--    - Insert into leaf: 1 write
--    - Potential split handling: 0-4 more I/Os
--
-- 3. Data record must also move (clustered index)
--    
-- Total: 8-20+ I/Os
 
-- This is why primary keys should be immutable!
 
 
-- SCENARIO 4: Update on secondary index key
UPDATE customers 
SET last_name = 'Smith' 
WHERE customer_id = 12345;
 
-- Secondary index on (last_name, first_name) affected:
-- 1. Delete old entry for (old_last_name, first_name)
-- 2. Insert new entry for ('Smith', first_name)
-- 
-- Clustered index (customer_id): just data update, no key change
-- 
-- Total: ~8-12 I/Os (search + delete + insert + data update)
 
-- Every indexed column update costs more than non-indexed updates!

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

Bulk Load Performance Comparison
=================================
 
Scenario: Load 10 million records into table with B+-tree index
Record size: 200 bytes
Index entry: 14 bytes
Block size: 4 KB
 
METHOD 1: Row-by-row INSERT with index maintenance
-------------------------------------------------
Per-row cost: ~4-6 I/Os (search + insert + occasional split)
Total I/Os: 10,000,000 × 5 = 50,000,000 I/Os
SSD time: 50M × 0.1ms = 5,000 seconds = 83 minutes
HDD time: 50M × 10ms = 500,000 seconds = 139 hours (!)
 
Problem: Completely impractical for HDD, slow even for SSD.
 
 
METHOD 2: Sorted bulk load (bottom-up construction)
--------------------------------------------------
Step 1: Sort data by index key
  - External sort: O(n log n) comparisons
  - I/O: ~2-4 passes over data = 2-4 × (10M × 200 bytes / 4KB)
  - I/O: ~2 million block reads/writes
 
Step 2: Build leaf level
  - Write full leaf blocks sequentially
  - 10M entries / 250 per leaf = 40,000 leaf blocks
  - I/O: 40,000 sequential writes
 
Step 3: Build internal levels
  - Level 2: 40,000 / 250 = 160 blocks
  - Level 3: 160 / 250 = 1 block (root)
  - I/O: ~200 writes
 
Total I/Os: ~2,000,000 + 40,200 = ~2,040,000 I/Os
SSD time: 2M × 0.1ms = 200 seconds = 3.3 minutes
HDD time: 2M × 0.1ms (sequential!) = ~200 seconds = 3.3 minutes
 
SPEEDUP: 25x faster than row-by-row!
 
 
METHOD 3: Drop index, load, rebuild
-----------------------------------
Step 1: Drop index
  - Instant
 
Step 2: Load data (no index maintenance)
  - Simple append to heap: 10M × 200 bytes = 2 GB
  - Sequential writes: 500,000 block writes
  - I/O: 500,000 writes
 
Step 3: Rebuild index (same as sorted bulk load)
  - But data not sorted! Must sort first.
  - Index build: ~2,040,000 I/Os (same as Method 2)
 
Total: ~2,540,000 I/Os
Slightly slower than Method 2, but simpler to implement.
 
CONCLUSION: 
For large loads, NEVER do row-by-row with index maintenance.
Either bulk load with sorted data, or drop/rebuild indexes.

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

-- Index Maintenance Operations
 
-- SQL Server: Check fragmentation
SELECT 
    OBJECT_NAME(i.object_id) AS TableName,
    i.name AS IndexName,
    ips.avg_fragmentation_in_percent AS Fragmentation,
    ips.avg_page_space_used_in_percent AS PageDensity
FROM sys.indexes i
JOIN sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'LIMITED') ips
    ON i.object_id = ips.object_id AND i.index_id = ips.index_id
WHERE ips.avg_fragmentation_in_percent > 10
ORDER BY Fragmentation DESC;
 
 
-- SQL Server: Reorganize (light maintenance, online)
ALTER INDEX ix_customer_name ON customers REORGANIZE;
-- Defragments leaf level, compacts pages
-- Low overhead, can run during business hours
 
 
-- SQL Server: Rebuild (heavy maintenance, may block)
ALTER INDEX ix_customer_name ON customers REBUILD;
-- Drops and recreates entire index
-- Full defragmentation, resets fill factor
-- Can block queries (unless ONLINE option used)
 
 
-- PostgreSQL: Check bloat
SELECT 
    schemaname, tablename, indexname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes;
 
-- PostgreSQL: Reindex (equivalent to rebuild)
REINDEX INDEX ix_customer_name;
-- Or for all indexes on a table:
REINDEX TABLE customers;
 
 
-- MySQL/InnoDB: Analyze to update statistics
ANALYZE TABLE customers;
 
-- MySQL: Optimize to rebuild and defragment
OPTIMIZE TABLE customers;
-- Recreates table and indexes, expensive but thorough
 
 
/*
Maintenance Schedule Guidelines:
================================
- Daily: Update statistics for tables with heavy DML
- Weekly: Reorganize indexes with 10-30% fragmentation  
- Monthly: Rebuild indexes with >30% fragmentation
- After bulk loads: Always rebuild/reorganize affected indexes
 
Automation:
- Use maintenance plans (SQL Server)
- Use pg_repack extension (PostgreSQL) for online rebuilds
- Schedule during low-activity windows
- Monitor index health with regular fragmentation checks
*/