Tree Structure

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

Multi-Level Index → Tree Structure Mapping
============================================
 
MULTI-LEVEL INDEX VIEW:           TREE VIEW:
                                  
Level 3 (Root):     [Block]       Root Node: [1 block = 1 node]
         ↓                               │
Level 2:    [Block] [Block] ...     Internal Nodes: [118 blocks = 118 nodes]
              ↓       ↓                  │
Level 1:  [B][B][B] [B][B][B] ...   Leaf Nodes: [34,247 blocks = 34,247 nodes]
            ↓                            │
Level 0:     DATA RECORDS               DATA RECORDS
 
 
TREE TERMINOLOGY APPLIED:
 
Height (h)  = Number of levels = 3 (L3 → L2 → L1)
             Note: Height counts edges or levels depending on definition
             
Fanout (f)  = Max children per node = 292 (entries per block)
 
Degree (d)  = Typically: min children per internal node
             For B-trees: d = ⌈f/2⌉ (ensures at least half-full)
             
Root        = Single node at top; accessed first in every query
 
Internal    = Nodes between root and leaves; contain keys + child pointers
Nodes       
             Entry format: (key, child_pointer)
             
Leaf        = Bottom-level nodes; contain keys + data pointers
Nodes       
             Entry format: (key, data_pointer) OR (key, data_value)
 
Balance     = All paths from root to any leaf have the same length
             This is CRITICAL for predictable performance

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

Internal Node Structure
========================
 
Standard format (n keys, n+1 pointers):
 
┌─────────────────────────────────────────────────────────────────────┐
│  P₀  │ K₁ │ P₁ │ K₂ │ P₂ │ K₃ │ P₃ │ ... │ K_{n} │ P_{n} │ unused │
└─────────────────────────────────────────────────────────────────────┘
 
Where:
  K₁ < K₂ < K₃ < ... < K_{n}  (keys in sorted order)
  
Pointer meaning:
  P₀ points to subtree with all keys < K₁
  P₁ points to subtree with keys where K₁ ≤ key < K₂
  P₂ points to subtree with keys where K₂ ≤ key < K₃
  ...
  P_{n} points to subtree with all keys ≥ K_{n}
 
 
EXAMPLE: Internal node with 4 keys (5 pointers)
 
┌──────────────────────────────────────────────────────────────┐
│ P₀ │ 100 │ P₁ │ 200 │ P₂ │ 300 │ P₃ │ 400 │ P₄ │  unused   │
└──────────────────────────────────────────────────────────────┘
  │          │          │          │          │
  ↓          ↓          ↓          ↓          ↓
keys      keys       keys       keys       keys
< 100   100-199    200-299    300-399     ≥ 400
 
 
Memory layout (assuming 4-byte keys, 6-byte pointers):
  - Each (pointer, key) pair: 6 + 4 = 10 bytes
  - First pointer alone: 6 bytes
  - 4 keys, 5 pointers: 6 + (4 × 10) = 46 bytes for entries
  - Block size 4096 bytes → up to ~400 entries possible
  - Actual capacity depends on header/metadata overhead
 
 
Leaf Node Structure (different from internal!)
==============================================
 
Leaf nodes store actual data pointers (or data values):
 
┌────────────────────────────────────────────────────────────────────────┐
│ K₁ │ DP₁ │ K₂ │ DP₂ │ K₃ │ DP₃ │ ... │ K_{n} │ DP_{n} │ next │ unused │
└────────────────────────────────────────────────────────────────────────┘
 
Where:
  K₁, K₂, ... K_{n} = key values (sorted)
  DP₁, DP₂, ... DP_{n} = data pointers (to actual records)
  next = pointer to next leaf node (for range scans) - B+-tree feature
 
Key differences from internal nodes:
  1. No "between keys" semantics - each key has exactly one data pointer
  2. May include sibling pointers for efficient range queries
  3. In B+-tree: ALL data pointers are in leaves, none in internal nodes

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

Balance vs. Imbalance: A Concrete Example
==========================================
 
Inserting keys 1, 2, 3, 4, 5, 6, 7 in order:
 
UNBALANCED BST (simple binary search tree):
                    1
                     ╲
                      2
                       ╲
                        3
                         ╲
                          4
                           ╲
                            5
                             ╲
                              6
                               ╲
                                7
 
Height: 7 (equals number of nodes - worst case!)
Search for key 7: 7 comparisons, 7 node accesses
This is O(n), not O(log n)!
 
 
BALANCED TREE (e.g., B-tree, AVL, Red-Black):
 
              4
           ╱     ╲
          2       6
         ╱ ╲     ╱ ╲
        1   3   5   7
 
Height: 3 (logarithmic in number of nodes)
Search for ANY key: ≤3 comparisons, ≤3 node accesses
This is O(log n), regardless of insertion order
 
 
FOR DATABASE INDEXES (with fanout f ≈ 300):
 
Same 7 keys in a B-tree-style node:
        ┌───────────────────────────────────┐
        │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ... │
        └───────────────────────────────────┘
 
All 7 keys fit in a single node!
Height: 1 (root is also a leaf)
Search for any key: 1 node access
 
This is why high fanout is so powerful:
  - 7 keys → 1 level (single block)
  - 7,000 keys → 2 levels  
  - 7,000,000 keys → 3 levels
  - 7,000,000,000 keys → 4 levels
 
ALL of these are balanced, and the height grows very slowly.

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

Binary Tree vs. B-Tree: Quantitative Analysis
==============================================
 
Dataset: 10,000,000 records
Key size: 8 bytes
Pointer size: 6 bytes
Block size: 4,096 bytes
 
BINARY TREE (AVL/Red-Black):
---------------------------
Node content: 1 key + 2 child pointers = 8 + 6 + 6 = 20 bytes
Block utilization: 20 / 4096 = 0.5% (wasting 99.5% of block!)
 
Since we read whole blocks anyway, ONE BLOCK could hold:
  4096 / 20 = 204 nodes
  
But binary tree structure means we visit each node in sequence,
not all nodes in a block together.
 
Height of balanced binary tree with 10M nodes:
  log₂(10,000,000) = 23.25 → 24 levels
 
With tree nodes scattered across blocks:
  Worst case: 24 block reads per search
  (Each level might be in a different block)
 
Even if nodes are clustered:
  - Navigating the tree still requires following pointers
  - Each pointer might go to a different block
  - Expected I/O: ~20 block reads
 
 
B-TREE (fanout ≈ 300):
---------------------
Node content: ~300 keys + ~301 pointers = 300×8 + 301×6 = 4,206 bytes
Block utilization: ~100% (node sized to match block)
 
Height of B-tree with 10M keys:
  log₃₀₀(10,000,000) = 2.83 → 3 levels
 
Block reads per search: exactly 3 (one per level)
 
 
COMPARISON SUMMARY:
                    Binary Tree    B-Tree     Ratio
                    -----------    ------     -----
Height              24             3          8x
I/O per search      ~20            3          6.7x
Block utilization   0.5%           ~100%      200x
Cache friendliness  Very poor      Excellent  
 
The B-tree is designed for block-based storage.
The binary tree is designed for pointer-based (RAM) storage.
Using binary trees on disk is a fundamental mismatch.

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

class BTreeNode:
    """
    Representation of a B-tree node with invariant enforcement.
    
    Order (m): Maximum number of children per node
    For a B-tree of order m:
      - Each internal node has at most m children
      - Each internal node (except root) has at least ⌈m/2⌉ children
      - Root has at least 2 children (if not a leaf)
      - Each node has at most m-1 keys
      - Each node (except root) has at least ⌈m/2⌉-1 keys
      - All leaves are at the same depth
    """
    
    def __init__(self, order: int, is_leaf: bool = False):
        self.order = order          # Maximum children
        self.is_leaf = is_leaf      # Is this a leaf node?
        self.keys = []              # Search keys (sorted)
        self.children = []          # Child pointers (one more than keys)
        self.data_pointers = []     # For leaves: pointers to actual data
    
    @property
    def min_keys(self) -> int:
        """Minimum keys required (except root)."""
        return (self.order + 1) // 2 - 1  # ⌈m/2⌉ - 1
    
    @property
    def max_keys(self) -> int:
        """Maximum keys allowed."""
        return self.order - 1
    
    @property
    def is_underfull(self) -> bool:
        """Node has fewer than minimum keys."""
        return len(self.keys) < self.min_keys
    
    @property
    def is_full(self) -> bool:
        """Node is at maximum capacity."""
        return len(self.keys) >= self.max_keys
    
    @property
    def can_donate(self) -> bool:
        """Node has more than minimum keys (can donate to sibling)."""
        return len(self.keys) > self.min_keys
    
    def validate(self) -> bool:
        """Check that all node invariants hold."""
        # Keys must be sorted
        if self.keys != sorted(self.keys):
            return False
        
        # Key count within bounds (ignoring root exception)
        if len(self.keys) > self.max_keys:
            return False
        
        # Internal nodes: children = keys + 1
        if not self.is_leaf:
            if len(self.children) != len(self.keys) + 1:
                return False
        
        # All keys unique (for primary indexes)
        if len(self.keys) != len(set(self.keys)):
            return False
        
        return True
 
 
def validate_btree(root: BTreeNode) -> tuple[bool, str]:
    """
    Validate entire B-tree structure.
    Returns (is_valid, error_message).
    """
    def check_depth(node: BTreeNode, current_depth: int) -> int:
        """Return depth of first leaf found, or -1 if inconsistent."""
        if node.is_leaf:
            return current_depth
        
        depths = [check_depth(child, current_depth + 1) 
                  for child in node.children]
        
        if len(set(depths)) > 1 or -1 in depths:
            return -1  # Inconsistent depths
        return depths[0]
    
    leaf_depth = check_depth(root, 0)
    if leaf_depth == -1:
        return (False, "Leaves at different depths - not balanced!")
    
    return (True, f"Valid B-tree with height {leaf_depth}")

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

-- Calculating B+-tree height for various data sizes
-- Practical formula with realistic assumptions
 
WITH params AS (
    SELECT 
        4096 AS block_size_bytes,
        8 AS key_size_bytes,
        8 AS pointer_size_bytes,  -- 6-8 bytes for block pointer
        0.70 AS typical_fill_factor  -- Nodes typically 70% full
),
calculated AS (
    SELECT 
        FLOOR((block_size_bytes - 100) / (key_size_bytes + pointer_size_bytes)) 
            AS max_fanout,
        FLOOR((block_size_bytes - 100) / (key_size_bytes + pointer_size_bytes) 
            * typical_fill_factor) 
            AS typical_fanout
    FROM params
),
data_sizes AS (
    SELECT 1000 AS records, '1 thousand' as label UNION ALL
    SELECT 1000000, '1 million' UNION ALL
    SELECT 1000000000, '1 billion' UNION ALL
    SELECT 1000000000000, '1 trillion'
)
SELECT 
    d.label,
    d.records,
    c.typical_fanout AS fanout,
    CEILING(LOG(d.records) / LOG(c.typical_fanout)) AS tree_height,
    CEILING(LOG(d.records) / LOG(c.typical_fanout)) + 1 AS total_ios_per_search
FROM data_sizes d
CROSS JOIN calculated c;
 
-- Results with typical fanout ~180-200:
-- Records       Fanout  Height  Total I/Os (with data)
-- 1 thousand    180     2       3
-- 1 million     180     3       4
-- 1 billion     180     4       5
-- 1 trillion    180     5       6
 
/*
KEY INSIGHT: 
Even for a TRILLION records, search requires only 6 block reads!
 
This is the magic of high-fanout balanced trees:
  - Tree height grows as log_f(n)
  - With f ≈ 200, each level adds factor of 200 to capacity
  - Physical limits (disk space) are reached before height becomes problematic
*/