┌──────────────────────────────┐
│        SQL Interface         │
├──────────────────────────────┤
│       Query Processor        │
│  (Parser → Optimizer → Plan) │
├──────────────────────────────┤
│      Execution Engine        │
│  (Iterator Model / Volcano)  │
├──────────────────────────────┤
│       Storage Engine         │
│  (B+Tree / LSM / Columnar)   │
├──────────────────────────────┤
│     Buffer Pool / Cache      │
├──────────────────────────────┤
│       Disk I/O Layer         │
│    (File System / Direct I/O)│
└──────────────────────────────┘

随机读 4KB:  ~10ms    → 0.4 KB/ms
顺序读 1MB:  ~15ms    → 66.7 KB/ms

性能差距: ~167x (按每字节成本计算)

HDD:    随机读 ~10ms,  顺序读 ~15MB/s
SSD:    随机读 ~100μs, 顺序读 ~500MB/s
内存:   随机读 ~100ns, 顺序读 ~10GB/s

HDD → SSD:  随机读提升 100x
SSD → 内存: 随机读提升 1000x

页大小对比:
InnoDB:      16KB (默认), 支持 4KB/8KB/32KB/64KB
PostgreSQL:  8KB (编译时确定)
MySQL/MyISAM: 1KB (默认)
SQLite:      1KB-64KB (默认 4KB)
Oracle:      2KB-32KB (默认 8KB)

┌─────────────────────────────────────┐
│            Page Header              │  ← 页的元信息（页号、LSN、空闲空间指针等）
├─────────────────────────────────────┤
│            Free Space               │  ← 空闲空间
├─────────────────────────────────────┤
│              ↓ Growth               │
│                                     │
│              ↑ Growth               │
├─────────────────────────────────────┤
│           Slot Directory            │  ← 槽目录（指向记录的指针数组）
├─────────────────────────────────────┤
│            Page Footer              │  ← 校验和、LSN 等
└─────────────────────────────────────┘

读取路径:
1. 检查缓冲池 → 命中 → 直接返回（~100ns）
2. 缓冲池未命中 → 从磁盘读取页 → 放入缓冲池 → 返回（~100μs-10ms）

写入路径（Write-Through）:
1. 修改缓冲池中的页（标记为 dirty）
2. 后台线程定期将 dirty 页刷回磁盘

写入路径（Write-Back）:
1. 修改缓冲池中的页（标记为 dirty）
2. 先写 WAL 日志
3. 后台线程定期将 dirty 页刷回磁盘

场景: 缓冲池大小 100 页，热点数据 10 页
全表扫描 1000 页 → 热点数据全部被淘汰 → 后续查询性能暴跌

解决方案:
1. Adaptive LRU: 区分扫描和正常访问
2. LRU-K: 考虑访问频率而不仅是最近访问时间
3. 双缓冲池策略（InnoDB 的方案）

InnoDB 的解决方案:
1. 将 LRU 链表分成多个分区（partition）
2. 每个分区有独立的 LRU 链表和锁
3. 使用 chunk 为单位进行淘汰，减少锁竞争

WAL 的核心规则:
1. 修改数据页前，必须先写 redo log
2. redo log 必须持久化到磁盘（fsync），事务才能提交
3. 数据页可以延迟写入磁盘（异步刷盘）

为什么这样设计?
- 顺序写日志比随机写数据页快得多
- 崩溃恢复时，通过重放 redo log 恢复未刷盘的数据
- 允许数据页延迟刷盘，提高写入吞吐量

Redo Log Record:
┌─────────────────────────────┐
│ LSN (Log Sequence Number)   │  ← 全局递增的日志序列号
├─────────────────────────────┤
│ Transaction ID              │  ← 事务标识
├─────────────────────────────┤
│ Page ID                     │  ← 被修改的页
├─────────────────────────────┤
│ Offset within Page          │  ← 页内偏移
├─────────────────────────────┤
│ Before Image (可选)          │  ← 修改前的数据（用于 undo）
├─────────────────────────────┤
│ After Image                 │  ← 修改后的数据（用于 redo）
├─────────────────────────────┤
│ Checksum                    │  ← 校验和
└─────────────────────────────┘

检查点的作用:
1. 将所有已修改的脏页刷回磁盘
2. 在日志中记录检查点位置
3. 崩溃恢复时，只需要从最近的检查点开始重放

检查点策略:
- 尖锐检查点（Sharp Checkpoint）: 停止所有事务，刷完所有脏页
  → 简单但会导致长时间停顿
- 模糊检查点（Fuzzy Checkpoint）: 不停止事务，记录检查点时的状态
  → 恢复时需要额外的 undo 操作
- InnoDB 采用模糊检查点 + 异步刷脏策略

B+ 树存储引擎的读写特征:
写入: 找到目标页 → 修改页内记录 → 可能触发页分裂
读取: 从根到叶遍历 B+ 树 → 每层一次 I/O（缓冲池可缓存中间节点）
典型深度: 3-4 层可索引数十亿条记录

列式存储的读写特征:
写入: 按列组织数据 → 批量压缩 → 顺序追加到文件末尾
读取: 只读取查询需要的列 → 利用压缩减少 I/O → 向量化执行
压缩率: 通常可达 3x-10x（同列数据类型相同，压缩效率高）

LSM 树的写入路径:
1. 写入 MemTable（内存中的有序结构）
2. MemTable 满后冻结为 Immutable MemTable
3. 后台线程将 Immutable MemTable 刷写为 SSTable（磁盘上的有序文件）
4. 多个 SSTable 通过 Compaction 合并，消除过期数据

写入效率: 顺序追加，接近磁盘带宽上限
读取代价: 可能需要查找多个 SSTable（通过 Bloom Filter 优化）

-- 查看 InnoDB 缓冲池统计信息
SELECT
    (innodb_buffer_pool_read_requests - innodb_buffer_pool_reads) 
    / innodb_buffer_pool_read_requests * 100 AS buffer_hit_ratio,
    innodb_buffer_pool_read_requests AS total_requests,
    innodb_buffer_pool_reads AS disk_reads,
    innodb_buffer_pool_pages_total AS total_pages,
    innodb_buffer_pool_pages_data AS data_pages,
    innodb_buffer_pool_pages_free AS free_pages
FROM information_schema.global_status
WHERE variable_name IN (
    'innodb_buffer_pool_read_requests',
    'innodb_buffer_pool_reads',
    'innodb_buffer_pool_pages_total',
    'innodb_buffer_pool_pages_data',
    'innodb_buffer_pool_pages_free'
);

-- 典型的输出分析:
-- buffer_hit_ratio: 99.5% → 良好（>99% 为正常）
-- buffer_hit_ratio: 85% → 需要增大缓冲池
-- buffer_hit_ratio: <50% → 缓冲池严重不足或存在全表扫描

-- 查看 InnoDB redo log 状态
SHOW ENGINE INNODB STATUS;

-- 关注以下输出:
-- Log sequence number: 当前 LSN
-- Log flushed up to: 已刷盘的 LSN
-- Last checkpoint at: 最近检查点的 LSN

-- 计算 redo log 的写入速率
-- 间隔 10 秒采样两次:
SELECT 
    (lsn2 - lsn1) / 10 AS bytes_per_second
FROM (
    SELECT 
        -- 第一次采样 LSN
        12345678 AS lsn1,
        -- 第二次采样 LSN
        13456789 AS lsn2
) t;

-- 输出: 1111111 bytes/sec ≈ 1.1 MB/s
-- 这意味着每秒产生约 1.1MB 的 redo log

import os
import time
import struct

def benchmark_page_size(page_size, total_data_size, read_pattern='random'):
    """模拟不同页大小对随机读性能的影响"""
    # 创建测试文件
    data = os.urandom(total_data_size)
    filename = f"test_{page_size}.dat"
    with open(filename, 'wb') as f:
        f.write(data)
    
    # 计算页数量
    num_pages = total_data_size // page_size
    
    start = time.time()
    with open(filename, 'rb') as f:
        if read_pattern == 'random':
            import random
            for _ in range(1000):
                page_no = random.randint(0, num_pages - 1)
                f.seek(page_no * page_size)
                f.read(page_size)
        elif read_pattern == 'sequential':
            for i in range(min(1000, num_pages)):
                f.seek(i * page_size)
                f.read(page_size)
    
    elapsed = time.time() - start
    os.remove(filename)
    return elapsed

# 测试结果（示意）:
# Page Size  | Random Read (1000 ops) | Sequential Read (1000 ops)
# 4KB        | 2.3s                   | 0.8s
# 8KB        | 2.5s                   | 0.9s
# 16KB       | 2.8s                   | 1.0s
# 32KB       | 3.2s                   | 1.1s

# 分析:
# - 页越大，每次 I/O 传输的数据越多，但随机读的开销也越大
# - 对于 OLTP 场景（大量随机读），较小的页（8KB-16KB）更合适
# - 对于 OLAP 场景（大量顺序扫描），较大的页（32KB-64KB）更合适