1
// InnoDB 页结构简化示意
2
typedef struct page_t {
3
    page_header_t  header;       // 页头信息
4
    page_dir_t     dir;          // 页目录（槽位）
5
    record_t       records[];    // 用户记录（从低地址向高地址增长）
6
    free_space_t   free;         // 空闲空间
7
} page_t;
8

9
typedef struct page_header_t {
10
    uint32_t       page_id;      // 页编号
11
    uint16_t       n_records;    // 记录数
12
    uint16_t       first_free;   // 第一条空闲记录偏移
13
    page_type_t    type;         // 页类型（索引页/数据页/LOB页等）
14
} page_header_t;

1
# 操作系统 Page Cache 的问题
2
# 1. 淘汰策略不可控：OS 使用通用 LRU，不知道哪些页对数据库更重要
3
# 2. 预读策略不匹配：OS 的预读是通用的，数据库知道自己的访问模式
4
# 3. 刷脏策略不可控：OS 可能突然刷大量脏页，造成 I/O 尖刺
5
# 4. 重复缓存：如果 DB 自己也缓存，同一页可能被缓存两次（浪费内存）
6

7
# 数据库 Buffer Pool 的优势
8
class BufferPoolAdvantage:
9
    """数据库自管 Buffer Pool 的核心优势"""
10

11
    def controlled_eviction(self):
12
        """可控的淘汰策略"""
13
        # 数据库知道哪些是索引页（热点）、哪些是数据页
14
        # 可以实现 LRU-K、Clock 等更适合数据库的策略
15
        pass
16

17
    def smart_prefetch(self):
18
        """智能预读"""
19
        # 索引范围扫描时，数据库知道接下来要读哪些页
20
        # 可以提前异步加载，而不是等 OS 的顺序检测
21
        pass
22

23
    def group_flush(self):
24
        """分组刷脏"""
25
        # 将相邻页的脏数据合并为一次顺序写
26
        # 避免操作系统随机刷脏造成的 I/O 尖刺
27
        pass

1
class BPlusTreeNode:
2
    """B+ 树节点简化实现"""
3
    def __init__(self, order, is_leaf=False):
4
        self.keys = []
5
        self.children = []  # 内部节点：子节点指针；叶子节点：数据
6
        self.is_leaf = is_leaf
7
        self.order = order      # 阶数
8
        self.next_leaf = None   # 叶子节点链表指针
9

10
    def insert(self, key, value):
11
        if self.is_leaf:
12
            return self._insert_leaf(key, value)
13
        else:
14
            # 找到合适的子节点，递归插入
15
            idx = self._find_child(key)
16
            result = self.children[idx].insert(key, value)
17
            if result:  # 子节点分裂，需要提升中间键
18
                mid_key, new_node = result
19
                self._promote(mid_key, new_node)
20
                if len(self.keys) >= self.order:
21
                    return self._split()
22
        return None
23

24
    def _insert_leaf(self, key, value):
25
        """叶子节点插入，溢出时分裂"""
26
        idx = self._find_position(key)
27
        self.keys.insert(idx, key)
28
        self.children.insert(idx, value)
29

30
        if len(self.keys) >= self.order:
31
            return self._split_leaf()
32
        return None
33

34
    def _split_leaf(self):
35
        """叶子节点分裂：左半留下，右半新建，中间键提升"""
36
        mid = len(self.keys) // 2
37
        new_node = BPlusTreeNode(self.order, is_leaf=True)
38
        new_node.keys = self.keys[mid:]
39
        new_node.children = self.children[mid:]
40
        new_node.next_leaf = self.next_leaf
41
        self.keys = self.keys[:mid]
42
        self.children = self.children[:mid]
43
        self.next_leaf = new_node
44
        # 返回提升的键和新节点
45
        return (new_node.keys[0], new_node)

1
// SSTable 文件结构简化
2
typedef struct sstable_t {
3
    data_block_t   blocks[];      // 数据块（按 key 有序）
4
    index_block_t  index;         // 索引块（每个数据块的 min_key）
5
    filter_block_t filter;        // 布隆过滤器块
6
    footer_t       footer;        // 尾部：指向 index 和 filter 的偏移
7
} sstable_t;
8

9
typedef struct data_block_t {
10
    entry_t  entries[];           // key-value 条目
11
    uint32_t restarts[];          // 重启点（前缀压缩的断点）
12
    uint32_t num_restarts;        // 重启点数量
13
} data_block_t;

1
L0: [SST1] [SST2] [SST3] [SST4]    ← 4 个相似大小的 SSTable
2
         ↓ 合并
3
L1: [SST_big]                        ← 1 个合并后的大 SSTable

1
L0: [SST1] [SST2]                    ← 允许范围重叠
2
L1: [SST_a] [SST_b] [SST_c]         ← key 范围不重叠，总大小 ≤ 10MB
3
L2: [SST_1] ... [SST_10]             ← 总大小 ≤ 100MB
4
L3: [SST_1] ... [SST_100]            ← 总大小 ≤ 1000MB
5
    每层大小是上层的 10 倍

1
# RocksDB 中查看 Compaction 统计
2
# 通过 rocksdb.compaction.stats 指标
3
# Level  Files  Size(MB)  Read(MB)  Write(MB)  Write Amp
4
# --------------------------------------------------------
5

6
#   L1     12      10.1       8.2      18.3       2.2
7
#   L2     45     100.5      18.3     118.8       6.5
8
#   L3    210    1002.0     118.8    1120.8       9.4
9
# --------------------------------------------------------

1
import mmh3  # MurmurHash3
2

3
class BloomFilter:
4
    """布隆过滤器简化实现"""
5
    def __init__(self, capacity, error_rate=0.01):
6
        # 计算需要的位数和哈希函数数量
7
        self.size = self._optimal_size(capacity, error_rate)
8
        self.num_hashes = self._optimal_hashes(self.size, capacity)
9
        self.bit_array = [False] * self.size
10

11
    def add(self, key):
12
        for i in range(self.num_hashes):
13
            idx = mmh3.hash(str(key), i) % self.size
14
            self.bit_array[idx] = True
15

16
    def might_contain(self, key):
17
        """可能存在（有假阳性）或一定不存在（无假阴性）"""
18
        for i in range(self.num_hashes):
19
            idx = mmh3.hash(str(key), i) % self.size
20
            if not self.bit_array[idx]:
21
                return False  # 一定不存在
22
        return True  # 可能存在（1% 假阳性率）
23

24
    @staticmethod
25
    def _optimal_size(n, p):
26
        """计算最优位数组大小：m = -(n * ln(p)) / (ln2)^2"""
27
        import math
28
        return int(-(n * math.log(p)) / (math.log(2) ** 2))
29

30
    @staticmethod
31
    def _optimal_hashes(m, n):
32
        """计算最优哈希函数数量：k = (m/n) * ln2"""
33
        import math
34
        return int((m / n) * math.log(2))

1
# B+ 树写放大估算
2
def btree_write_amplification(page_size=16*1024, record_size=100):
3
    """B+ 树修改一条记录需要重写整个页"""
4
    return page_size / record_size  # ≈ 163 倍
5

6
# LSM 树 Leveled Compaction 写放大估算
7
def lsm_write_amplification(num_levels=7, size_ratio=10):
8
    """每层都会重写数据，写放大 ≈ 层数 × 大小比率"""
9
    return num_levels * size_ratio  # ≈ 10-30 倍（实际更复杂）
10

11
# 实际测量
12
print(f"B+ 树写放大: {btree_write_amplification():.0f}x")
13
print(f"LSM 树写放大: {lsm_write_amplification():.0f}x (估算)")
14
# 输出:
15
# B+ 树写放大: 163x
16
# LSM 树写放大: 70x (估算)

1
// InnoDB 改良 LRU 结构简化
2
typedef struct buf_pool_t {
3
    // LRU 链表分为两段
4
    ut_list_base_t  LRU;           // 完整 LRU 链表
5
    ulint           LRU_old_ratio; // Old 区比例（默认 3/8）
6

7
    // 关键指针
8
    buf_block_t*    LRU_old;       // Old 区的起始位置
9
    buf_block_t*    LRU_new;       // Young 区的起始位置（MRU 端）
10

11
    // 统计信息
12
    ulint           n_pages_read;  // 读入页数
13
    ulint           n_pages_written; // 写出页数
14
    ulint           n_pages_made_young; // 从 Old 晋升到 Young 的次数
15
} buf_pool_t;
16

17
// 页访问时的晋升逻辑
18
void buf_page_accessed(buf_block_t* block) {
19
    if (block->in_old_zone) {
20
        // 在 Old 区中，被访问后是否晋升？
21
        // 需要满足"停留时间"条件，防止全表扫描污染 Young 区
22
        if (block->old_time > BUF_LRU_OLD_MIN_AGE) {
23
            buf_LRU_make_young(block);  // 移到 Young 区 MRU 端
24
        }
25
    } else {
26
        // 在 Young 区，移到 MRU 端
27
        buf_LRU_make_young(block);
28
    }
29
}

1
-- 查看当前 Buffer Pool 状态
2
SHOW ENGINE INNODB STATUS\G
3

4
-- 关键指标：
5
-- Buffer pool size: 8192 pages (128MB)
6
-- Free buffers: 1024
7
-- Database pages: 7000
8
-- Old database pages: 2625
9
-- Modified db pages: 500  ← 脏页数量
10
-- Pages made young: 15000
11
-- Pages not made young: 3000
12

13
-- 调整刷脏速度（SSD 推荐）
14
SET GLOBAL innodb_io_capacity = 10000;
15
SET GLOBAL innodb_io_capacity_max = 20000;

1
# my.cnf 中 Buffer Pool 关键参数
2

3
# Buffer Pool 大小（建议物理内存的 50-70%）
4
innodb_buffer_pool_size = 8G
5

6
# Buffer Pool 实例数（多实例减少锁竞争）
7
# 每个 instance 至少 1GB，总大小 / 1G ≈ 实例数
8
innodb_buffer_pool_instances = 8
9

10
# Old 区比例（默认 37%，即 3/8）
11
innodb_old_blocks_pct = 37
12

13
# Old 区停留时间（默认 1000ms）
14
# 全表扫描的页在 Old 区至少停留 1 秒才可能晋升到 Young 区
15
innodb_old_blocks_time = 1000
16

17
# 刷脏策略
18
innodb_io_capacity = 10000
19
innodb_io_capacity_max = 20000
20
innodb_max_dirty_pages_pct = 75.0
21
innodb_max_dirty_pages_pct_lwm = 10.0

1
-- InnoDB 中 Redo Log 的查看
2
SHOW VARIABLES LIKE 'innodb_log_file%';
3
-- innodb_log_file_size: 1GB    ← 单个日志文件大小
4
-- innodb_log_files_in_group: 2 ← 日志文件数量
5

6
-- Redo Log 空间 = 1GB × 2 = 2GB
7
-- 如果写入密集，可能需要增大
8

9
-- 查看日志写入频率
10
SHOW ENGINE INNODB STATUS\G
11
-- Log sequence number: 1234567890  ← 当前 LSN
12
-- Log flushed up to:    1234567800  ← 已刷盘的 LSN
13
-- Pages flushed up to:  1234567000  ← 数据页刷到的 LSN
14
-- Last checkpoint at:   1234565000  ← 检查点 LSN

1
sqlite3 /tmp/test.db << 'SQL'
2
CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT, email TEXT);
3
INSERT INTO users VALUES (1, 'Alice', 'alice@example.com');
4
INSERT INTO users VALUES (2, 'Bob', 'bob@example.com');
5
INSERT INTO users VALUES (3, 'Charlie', 'charlie@example.com');
6
INSERT INTO users VALUES (4, 'Dave', 'dave@example.com');
7
INSERT INTO users VALUES (5, 'Eve', 'eve@example.com');
8
SELECT * FROM users;
9
SQL

1
1|Alice|alice@example.com
2
2|Bob|bob@example.com
3
3|Charlie|charlie@example.com
4
4|Dave|dave@example.com
5
5|Eve|eve@example.com

1
sqlite3 /tmp/test.db "PRAGMA page_size;"
2
# 4096
3

4
sqlite3 /tmp/test.db "PRAGMA page_count;"
5
# 2
6

7
sqlite3 /tmp/test.db "PRAGMA journal_mode;"
8
# delete

1
sqlite3 /tmp/test.db "PRAGMA journal_mode=WAL;"
2
# wal
3

4
ls -la /tmp/test.db*
5
# -rw-r--r-- 1 root root 8192 May  8 11:12 /tmp/test.db

1
sqlite3 /tmp/test.db "SELECT name, rootpage FROM sqlite_master WHERE type='table';"

1
users|2