Node Size Selection

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

def calculate_fanout(page_size_bytes, key_size, pointer_size, overhead=64):
    """
    Calculate B+-tree fanout for given page and key sizes.
    
    Parameters:
    - page_size_bytes: Total page size
    - key_size: Size of each key in bytes
    - pointer_size: Size of each pointer in bytes
    - overhead: Page header, checksums, etc.
    """
    usable_space = page_size_bytes - overhead
    entries = usable_space // (key_size + pointer_size)
    return entries  # fanout = entries for internal nodes
 
# Compare fanout across page sizes for 8-byte keys
print("Fanout by Page Size (8-byte key, 8-byte pointer)")
print("=" * 50)
for page_kb in [4, 8, 16, 32, 64]:
    fanout = calculate_fanout(page_kb * 1024, 8, 8)
    print(f"{page_kb:2d} KB page → Fanout: {fanout:4d}")
 
# Output:
#  4 KB page → Fanout:  248
#  8 KB page → Fanout:  504
# 16 KB page → Fanout: 1016
# 32 KB page → Fanout: 2040
# 64 KB page → Fanout: 4088
 
# Calculate height for 1 billion records
import math
 
def calculate_height(fanout, record_count):
    return math.ceil(math.log(record_count, fanout)) + 1
 
print("
Tree Height for 1 Billion Records")
print("=" * 50)
for page_kb in [4, 8, 16, 32, 64]:
    fanout = calculate_fanout(page_kb * 1024, 8, 8)
    height = calculate_height(fanout, 1_000_000_000)
    print(f"{page_kb:2d} KB page → Height: {height}")

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

def compare_lookup_performance(record_count, key_size=8):
    """
    Compare B+-tree lookup performance: HDD vs SSD, various page sizes.
    """
    import math
    
    results = []
    
    for page_kb in [4, 8, 16, 32]:
        for storage_type in ['HDD', 'SSD']:
            # Calculate tree structure
            pointer_size = 8
            overhead = 64
            usable = page_kb * 1024 - overhead
            fanout = usable // (key_size + pointer_size)
            height = math.ceil(math.log(record_count, fanout)) + 1
            
            # I/O times (milliseconds)
            if storage_type == 'HDD':
                seek_latency = 8.0  # ms
                transfer_rate = 0.01  # ms per KB
            else:  # SSD
                seek_latency = 0.1  # ms
                transfer_rate = 0.002  # ms per KB
            
            io_time = seek_latency + page_kb * transfer_rate
            total_lookup_time = height * io_time
            
            results.append({
                'page_kb': page_kb,
                'storage': storage_type,
                'fanout': fanout,
                'height': height,
                'io_time_ms': io_time,
                'lookup_ms': total_lookup_time
            })
    
    return results
 
# Analyze for 1 billion records
results = compare_lookup_performance(1_000_000_000)
 
print("B+-Tree Lookup Performance (1B Records)")
print("=" * 65)
print(f"{'Page':<8} {'Storage':<8} {'Fanout':<8} {'Height':<8} {'I/O (ms)':<12} {'Lookup (ms)':<12}")
print("-" * 65)
for r in results:
    print(f"{r['page_kb']:<8} {r['storage']:<8} {r['fanout']:<8} {r['height']:<8} "
          f"{r['io_time_ms']:<12.3f} {r['lookup_ms']:<12.2f}")

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

def analyze_cache_efficiency(total_records, hot_record_pct, 
                                buffer_pool_mb, records_per_page):
    """
    Analyze cache efficiency for different access patterns.
    
    Assuming hot records are uniformly distributed across pages.
    """
    hot_records = int(total_records * hot_record_pct / 100)
    
    # Worst case: hot records spread across all pages
    # Each page has (hot_record_pct)% hot records
    
    # To cache all hot records, we might need to cache more pages
    # if hot records don't fill pages completely
    
    pages_with_hot_data = total_records // records_per_page
    hot_per_page = records_per_page * hot_record_pct / 100
    
    # Memory to cache all pages with hot data
    memory_for_all_hot_pages_mb = (pages_with_hot_data * records_per_page * 100) / (1024 * 1024)
    
    # Efficiency: what fraction of cached data is actually hot?
    cache_efficiency = hot_record_pct / 100  # theoretical maximum
    
    # With limited buffer pool, how much hot data can we cache?
    buffer_pages = buffer_pool_mb * 1024 * 1024 // (records_per_page * 100)  # assuming 100 bytes/record
    pages_cached = min(buffer_pages, pages_with_hot_data)
    hot_records_cached = pages_cached * hot_per_page
    hot_cache_ratio = hot_records_cached / hot_records if hot_records > 0 else 0
    
    return {
        'hot_records': hot_records,
        'cache_efficiency': cache_efficiency,
        'hot_cache_ratio': hot_cache_ratio,
        'pages_cached': pages_cached
    }
 
# Example: 1 billion records, 10% hot, 8GB buffer pool
for rpp in [50, 100, 200, 400]:  # records per page
    page_kb = rpp * 100 / 1024  # 100 bytes per record
    result = analyze_cache_efficiency(
        total_records=1_000_000_000,
        hot_record_pct=10,
        buffer_pool_mb=8192,
        records_per_page=rpp
    )
    print(f"~{page_kb:.0f}KB page ({rpp} rec/page): "
          f"Can cache {result['hot_cache_ratio']*100:.1f}% of hot data")

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

-- PostgreSQL: Create index with specific fill factor
CREATE INDEX idx_orders_customer 
ON orders (customer_id)
WITH (fillfactor = 90);  -- Leave 10% free space
 
-- SQL Server: Specify fill factor
CREATE INDEX idx_orders_customer
ON orders (customer_id)
WITH (FILLFACTOR = 90);
 
-- MySQL InnoDB: Control through MERGE_THRESHOLD
-- Pages split when > MERGE_THRESHOLD% full (default 50%)
ALTER TABLE orders 
COMMENT = 'MERGE_THRESHOLD=45';  -- Split earlier, more space
 
-- Oracle: PCTFREE controls space left for updates
CREATE INDEX idx_orders_customer 
ON orders (customer_id)
PCTFREE 10;  -- Reserve 10% for row expansion
 
-- Monitor fill factor / space usage
-- PostgreSQL
SELECT 
    relname,
    pg_size_pretty(pg_relation_size(oid)) as size,
    (pg_stat_get_dead_tuples(oid) * 100.0 / 
     NULLIF(pg_stat_get_live_tuples(oid) + pg_stat_get_dead_tuples(oid), 0)
    ) as dead_tuple_pct
FROM pg_class 
WHERE relkind = 'i' AND relname LIKE 'idx_%';