1
// InnoDB 16KB 页面结构（简化）
2
struct Page {
3
    // 页头（38 字节）
4
    struct PageHeader {
5
        uint32_t  page_id;          // 页编号
6
        uint16_t  n_dir_slots;      // 目录槽数
7
        uint16_t  heap_top;         // 堆顶指针
8
        uint16_t  n_heap;           // 堆中记录数
9
        uint16_t  first_free;       // 第一条空闲记录
10
        uint16_t  garbage;          // 已删除记录空间
11
        page_type_t type;           // 页类型
12
    } header;
13

14
    // 系统记录（INFIMUM + SUPREMUM）
15
    Record  infimum;                // 最小记录
16
    Record  supremum;               // 最大记录
17

18
    // 用户记录（从低地址向高地址增长）
19
    Record  records[];              // 用户记录
20

21
    // 空闲空间
22
    byte    free_space[];           // 可用空间
23

24
    // 页目录（从高地址向低地址增长）
25
    Slot    dir_slots[];            // 目录槽（二分查找用）
26
};
27

28
// 记录头（5 字节）
29
struct RecordHeader {
30
    uint8_t   n_owned;             // 该槽拥有的记录数
31
    uint16_t  heap_no;             // 堆中序号
32
    uint8_t   record_type;         // 记录类型
33
    uint16_t  next;                // 下一条记录偏移（链表）
34
};

1
# InnoDB B+ 树扇出计算
2
def calculate_fanout(page_size=16384, key_size=8, ptr_size=6,
3
                     record_size=100):
4
    """计算 B+ 树的扇出"""
5

6
    # 内部节点：只存储键 + 子节点指针
7
    # 非叶子页可用空间 ≈ page_size - 页头 - 目录
8
    internal_usable = page_size - 100  # 约 16284 字节
9
    internal_entry_size = key_size + ptr_size  # 14 字节
10
    fanout = internal_usable // internal_entry_size
11
    print(f"内部节点扇出: ~{fanout} 个子节点")
12

13
    # 叶子节点：存储完整记录
14
    leaf_usable = page_size - 100
15
    records_per_leaf = leaf_usable // record_size
16
    print(f"叶子节点记录数: ~{records_per_leaf} 条")
17

18
    # 树高度计算
19
    for height in range(1, 6):
20
        capacity = fanout ** (height - 1) * records_per_leaf
21
        print(f"高度 {height}: 可存储 {capacity:,} 条记录")
22

23
    return fanout
24

25
calculate_fanout()
26
# 内部节点扇出: ~1163 个子节点
27
# 叶子节点记录数: ~162 条
28
# 高度 1: 162 条记录
29
# 高度 2: 188,406 条记录
30
# 高度 3: 219,144,378 条记录（2.19 亿）
31
# 高度 4: 254,876,866,014 条记录

1
// B+ 树页面分裂算法（简化）
2
void btree_split_page(Page *page, Key new_key, Value new_value) {
3
    // 1. 分配新页面
4
    Page *new_page = allocate_page();
5

6
    // 2. 确定分裂点（中间位置）
7
    int mid = page->n_records / 2;
8
    Key mid_key = page->records[mid].key;
9

10
    // 3. 将上半部分移到新页面
11
    for (int i = mid; i < page->n_records; i++) {
12
        new_page->records[i - mid] = page->records[i];
13
    }
14
    new_page->n_records = page->n_records - mid;
15
    page->n_records = mid;
16

17
    // 4. 插入新记录到正确的页面
18
    if (new_key < mid_key) {
19
        insert_into_page(page, new_key, new_value);
20
    } else {
21
        insert_into_page(new_page, new_key, new_value);
22
    }
23

24
    // 5. 更新父节点
25
    insert_into_parent(page->parent, mid_key, new_page);
26

27
    // 6. 更新叶子链表
28
    new_page->next = page->next;
29
    page->next = new_page;
30
    new_page->prev = page;
31
}

1
# 页面合并条件
2
def should_merge(page, min_records=2):
3
    """判断是否需要合并"""
4
    # 页面记录数低于最小值
5
    if page.n_records < min_records:
6
        # 尝试与兄弟页面合并
7
        sibling = page.prev or page.next
8
        if sibling and (page.n_records + sibling.n_records) <= max_records:
9
            return True
10
        # 否则尝试从兄弟页面借记录（ redistribution）
11
        elif sibling and sibling.n_records > min_records + 1:
12
            redistribute(page, sibling)
13
            return False
14
    return False

1
// InnoDB rw-lock 实现（简化）
2
struct rw_lock_t {
3
    os_event_t  event;          // 等待事件
4
    volatile ulint lock_word;   // 锁字
5
    // lock_word > 0: 读锁数量
6
    // lock_word == 0: 写锁
7
    // lock_word == -1: 独占写锁
8
    volatile ulint waiters;     // 等待者标志
9
    UT_LIST_BASE_NODE_T(rw_lock_t) list; // 全局锁列表
10
};
11

12
// 获取读锁（共享锁）
13
void rw_lock_s_lock(rw_lock_t *lock) {
14
    // 自旋尝试
15
    for (int i = 0; i < spin_rounds; i++) {
16
        if (atomic_compare_and_swap(&lock->lock_word,
17
                                     expected, expected - 1)) {
18
            return;  // 成功获取读锁
19
        }
20
        cpu_relax();  // CPU 暂停
21
    }
22
    // 自旋失败，进入等待
23
    os_event_wait(lock->event);
24
}
25

26
// 获取写锁（排他锁）
27
void rw_lock_x_lock(rw_lock_t *lock) {
28
    // 自旋尝试
29
    for (int i = 0; i < spin_rounds; i++) {
30
        if (atomic_compare_and_swap(&lock->lock_word, 0, -1)) {
31
            return;  // 成功获取写锁
32
        }
33
        cpu_relax();
34
    }
35
    // 自旋失败，进入等待
36
    os_event_wait(lock->event);
37
}

1
# 前缀压缩示例
2
# 假设子节点 1 的最大键是 "apple_100"
3
# 子节点 2 的最小键是 "banana_200"
4
# 父节点中只需要存储 "b" 即可区分
5

6
keys_without_compression = ["apple_100", "banana_200", "cherry_300"]
7
keys_with_compression = ["a", "b", "c"]  # 只需首字母即可路由
8

9
# InnoDB 的键压缩
10
# 对于 (a, b, c) 联合索引，如果 a 相同，只存储 b, c 的差异部分

1
// B+ 树批量加载算法
2
void btree_bulk_load(Key *sorted_keys, Value *sorted_values, int n) {
3
    // 1. 从左到右依次填满叶子页面
4
    Page *current_leaf = allocate_page();
5
    for (int i = 0; i < n; i++) {
6
        if (!page_has_space(current_leaf, sorted_keys[i])) {
7
            // 当前页面已满，分配新页面
8
            Page *new_leaf = allocate_page();
9
            current_leaf->next = new_leaf;
10
            new_leaf->prev = current_leaf;
11
            current_leaf = new_leaf;
12
        }
13
        append_record(current_leaf, sorted_keys[i], sorted_values[i]);
14
    }
15

16
    // 2. 自底向上构建内部节点
17
    // 叶子页面的第一个键作为父节点的路由键
18
    build_internal_levels();
19

20
    // 优势：
21
    // - 页面利用率接近 100%（无分裂开销）
22
    // - 顺序写入，I/O 效率最高
23
    // - 无并发冲突
24
}

1
# B+ 树的读写放大分析
2
def btree_amplification(n_records, page_size=16384, record_size=100):
3
    """分析 B+ 树的读写放大"""
4
    fanout = page_size // (8 + 6)  # ~1163
5
    records_per_leaf = page_size // record_size  # ~162
6

7
    # 树高度
8
    height = 1
9
    capacity = records_per_leaf
10
    while capacity < n_records:
11
        height += 1
12
        capacity *= fanout
13

14
    # 读放大：点查需要读取 height 个页面
15
    read_amp = height
16
    print(f"树高度: {height}")
17
    print(f"读放大（点查）: {read_amp}x")
18

19
    # 写放大：插入一条记录需要
20
    # - 写入 WAL（1 次）
21
    # - 读取目标页面（1 次）
22
    # - 修改并写回目标页面（1 次）
23
    # 如果触发分裂，还需要写入新页面和父页面
24
    write_amp_normal = 3  # WAL + 读 + 写
25
    write_amp_split = write_amp_normal + 2  # + 新页面 + 父页面
26
    print(f"写放大（无分裂）: {write_amp_normal}x")
27
    print(f"写放大（有分裂）: {write_amp_split}x")
28

29
    # 空间放大：页面平均利用率
30
    space_amp = 1 / 0.69  # 平均 69% 利用率
31
    print(f"空间放大: {space_amp:.2f}x")
32

33
btree_amplification(100_000_000)
34
# 树高度: 3
35
# 读放大（点查）: 3x
36
# 写放大（无分裂）: 3x
37
# 写放大（有分裂）: 5x
38
# 空间放大: 1.45x

1
-- 查看索引树的高度
2
SELECT
3
    table_name,
4
    index_name,
5
    stat_value AS pages,
6
    stat_description
7
FROM mysql.innodb_index_stats
8
WHERE database_name = 'testdb'
9
    AND stat_name = 'n_leaf_pages'
10
ORDER BY table_name, index_name;
11

12
-- 查看索引统计
13
ANALYZE TABLE storage_test;
14
SHOW INDEX FROM storage_test;
15

16
-- 观察页面分裂
17
-- 创建自增主键表 vs 随机主键表
18
CREATE TABLE auto_inc (id INT AUTO_INCREMENT PRIMARY KEY, data VARCHAR(100));
19
CREATE TABLE random_pk (id CHAR(36) PRIMARY KEY, data VARCHAR(100));
20

21
-- 插入 10 万条记录后比较
22
SELECT table_name, data_length, index_length
23
FROM information_schema.tables
24
WHERE table_schema = 'testdb';

1
-- 查看索引大小和页面数
2
SELECT
3
    relname AS index_name,
4
    relpages,
5
    reltuples,
6
    pg_size_pretty(pg_relation_size(oid)) AS size
7
FROM pg_class
8
WHERE relkind = 'i' AND relname LIKE '%storage_test%';
9

10
-- 使用 pageinspect 扩展观察页面
11
CREATE EXTENSION IF NOT EXISTS pageinspect;
12

13
-- 查看索引的元页面
14
SELECT * FROM bt_metap('storage_test_pkey');
15

16
-- 查看索引的叶子页面
17
SELECT * FROM bt_page_items('storage_test_pkey', 1) LIMIT 10;