B+-Tree Variants and Optimizations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

TRADITIONAL B+-TREE: Binary search within large nodes
┌─────────────────────────────────────────────────────────────┐
│  Node with 200 keys (8KB)                                   │
│  Binary search: access positions 100, 50, 25, 12, 6, 3 ...  │
│  Each access likely misses cache (positions far apart)      │
└─────────────────────────────────────────────────────────────┘
 
CACHE-CONSCIOUS (CSS-Tree): Nodes sized to cache lines
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ 7 keys/node │ → │ 7 keys/node │ → │ 7 keys/node │
│ (64 bytes)  │   │ (64 bytes)  │   │ (64 bytes)  │
└─────────────┘   └─────────────┘   └─────────────┘
        ↓                 ↓                 ↓
   child nodes       child nodes       child nodes
 
Each node fits in single cache line:
- Load once, search entire node (7 comparisons)
- Sequential memory access within node = prefetch friendly
- More levels, but each level is ~5× faster

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

STANDARD BFS LAYOUT (poor cache behavior):
Memory: [root] [level 1 nodes...] [level 2 nodes...] [level 3...]
 
Traversal from root to leaf: memory accesses spread across entire array
- Each step jumps far in memory
- Poor spatial locality
 
VAN EMDE BOAS LAYOUT (recursive, cache-efficient):
Split tree at middle level, layout recursively:
 
        ┌───────────┐
        │   root    │
        │  subtree  │
        │ (top half)│
        └───────────┘
       /      |      ┌─────────┐ ┌─────────┐ ┌─────────┐
│ bottom  │ │ bottom  │ │ bottom  │
│subtree 1│ │subtree 2│ │subtree 3│
└─────────┘ └─────────┘ └─────────┘
 
Memory: [top] [bottom1] [bottom2] [bottom3] (recursively applied)
 
Key property: Path from root to any leaf touches O(log N / log B) 
contiguous memory regions of size B (cache block size)
- Optimal for any cache size!
- No cache parameters needed in algorithm

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

// Traditional binary search: log(n) iterations, 1 comparison each
int binary_search(int* keys, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (keys[mid] == target) return mid;
        else if (keys[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
 
// SIMD linear search: n/8 iterations, 8 comparisons each (AVX2)
int simd_search(int* keys, int n, int target) {
    __m256i target_vec = _mm256_set1_epi32(target);  // 8 copies of target
    
    for (int i = 0; i < n; i += 8) {
        __m256i keys_vec = _mm256_loadu_si256((__m256i*)&keys[i]);
        __m256i cmp = _mm256_cmpeq_epi32(keys_vec, target_vec);
        int mask = _mm256_movemask_ps(_mm256_castsi256_ps(cmp));
        if (mask != 0) {
            return i + __builtin_ctz(mask);  // Find first match
        }
    }
    return -1;
}
 
// For node with 64 keys:
// Binary search: 6 comparisons, 6 cache misses possible
// SIMD search:   8 iterations, sequential access, prefetch-friendly

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

PROBLEM: Random secondary index updates
 
When inserting a row:
1. Update clustered index (sequential for auto-increment PK) ✓ Fast
2. Update secondary index on column A (random location) ✗ Slow  
3. Update secondary index on column B (random location) ✗ Slow
 
SOLUTION: InnoDB Change Buffer
 
┌─────────────────────────────────────────────────────────────┐
│                    Buffer Pool                               │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   ┌─────────────┐     ┌─────────────────────────────────┐  │
│   │  Index Page │     │       Change Buffer Tree        │  │
│   │   (if in    │ OR  │  - Stores pending changes        │  │
│   │   memory)   │     │  - Organized by (space, page)   │  │
│   └─────────────┘     └─────────────────────────────────┘  │
│                                                             │
└─────────────────────────────────────────────────────────────┘
 
When secondary index page NOT in buffer pool:
- Don't read page from disk
- Record change in Change Buffer
- Continue processing (fast!)
 
Later (merge):
- When page is read for other reasons, merge pending changes
- Or background merge thread applies batched changes
- Multiple changes to same page = fewer I/Os

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

B+-TREE WRITE PATH:
Write → Find leaf (random I/O) → Modify in place → WAL
 
LSM-TREE WRITE PATH:
Write → MemTable (in-memory) → (full) → Flush to disk as SSTable
                                              ↓
                               Background compaction merges SSTables
 
┌─────────────────────────────────────────────────────────────┐
│  MemTable (memory)    - Recent writes, sorted             │
├─────────────────────────────────────────────────────────────┤
│  L0 SSTables (disk)   - Recent flushed, may overlap       │
├─────────────────────────────────────────────────────────────┤
│  L1 SSTables (disk)   - Compacted, non-overlapping        │
├─────────────────────────────────────────────────────────────┤
│  L2 SSTables (disk)   - Larger, non-overlapping           │
├─────────────────────────────────────────────────────────────┤
│  ...more levels...                                         │
└─────────────────────────────────────────────────────────────┘
 
Read: Check MemTable → L0 → L1 → ... → find first occurrence

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

# TRADITIONAL LOCK COUPLING (Pessimistic):
function search_pessimistic(root, key):
    lock(root)
    current = root
    
    while not current.is_leaf:
        child = find_child(current, key)
        lock(child)           # Lock child before...
        unlock(current)       # ...unlocking parent
        current = child
    
    # Search in locked leaf
    result = search_leaf(current, key)
    unlock(current)
    return result
 
# Problem: Lock contention at upper levels (all searches go through root)
 
# OPTIMISTIC LOCK COUPLING:
function search_optimistic(root, key):
    current = root
    version = current.get_version()  # Read version counter
    
    while not current.is_leaf:
        child = find_child(current, key)
        
        # Re-check version before moving down
        if current.version_changed(version):
            restart()  # Node was modified, start over
        
        current = child
        version = current.get_version()
    
    # Validate leaf and read
    lock(current)
    if current.version_changed(version):
        unlock(current)
        restart()
    
    result = search_leaf(current, key)
    unlock(current)
    return result
 
# Benefit: No locks during tree traversal, only at leaf

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

TRADITIONAL B+-TREE PROBLEM ON SSD:
- Random writes cause write amplification
- SSD must erase entire block (e.g., 512KB) to rewrite one page (e.g., 4KB)
- Internal SSD garbage collection creates further amplification
 
FD-TREE SOLUTION:
Uses logarithmic structure like LSM, but with B-tree organization
 
┌──────────────────────────────────────────────────────────┐
│  Head Tree (small, memory-resident)                      │
│  - Handles all insertions                                │
│  - Provides fast point queries for recent data           │
└──────────────────────────────────────────────────────────┘
                    ↓ (when full)
┌──────────────────────────────────────────────────────────┐
│  Level 1 B+-tree (on SSD)                                │
│  - Sequentially written during merge                     │
│  - No random writes to this level                        │
└──────────────────────────────────────────────────────────┘
                    ↓ (when full)
┌──────────────────────────────────────────────────────────┐
│  Level 2 B+-tree (on SSD, larger)                        │
│  - Merged from Level 1                                   │
└──────────────────────────────────────────────────────────┘
 
Benefits:
- Converts random writes to sequential (flash-friendly)
- Maintains B+-tree range scan efficiency
- Logarithmic merging limits total write amplification

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

DELTA ENCODING (great for sorted numeric keys):
Original keys:    [1000000, 1000007, 1000015, 1000018, 1000042]
Delta encoded:    [1000000, +7, +8, +3, +24]
                  Base value + deltas (variable-length integers)
 
Savings: 5 × 4 bytes = 20 bytes → 4 + 4 × 1 byte = 8 bytes (60% reduction)
 
DICTIONARY ENCODING (great for categorical data):
Original keys:    ["completed", "pending", "processing", "completed", ...]
Dictionary:       {0: "completed", 1: "pending", 2: "processing"}
Encoded:          [0, 1, 2, 0, ...]
 
Savings: 50-90% for low-cardinality columns
 
KEY NORMALIZATION (for collation-independent comparison):
Original:         "Müller", "Mueller", "MÜLLER"
Normalized:       UCA collation weight sequences
Benefit: Binary comparison instead of expensive collation functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

INNODB ADAPTIVE HASH INDEX (AHI):
 
Standard B+-tree lookup:
  Key → Root → Internal → Internal → Leaf → Binary search
  ~4 I/Os for deep tree
 
AHI Acceleration:
  Hash(key) → Direct pointer to leaf position
  O(1) when hash index hit
 
Automatic behavior:
1. InnoDB monitors access patterns per B+-tree page
2. Pages accessed frequently with same predicate pattern get hashed
3. Hash index built in background, used automatically
4. If patterns change, old hash entries aged out
 
Configuration:
  innodb_adaptive_hash_index = ON (default)
  innodb_adaptive_hash_index_parts = 8 (partitions for concurrency)
 
Monitoring:
  SHOW ENGINE INNODB STATUS;
  -- Shows: hash searches/s, non-hash searches/s