DDIA · 存储引擎与索引

💡 一句话理解

存储引擎回答一个问题: 字节放哪、怎么找到它。LSM-Tree像记账本 — 收银时只往最后一页流水账上追加 (顺序写飞快), 打烊后再慢慢誊清合并 (compaction); 查账要翻好几本账 (读放大), 但前面贴了Bloom filter便签"这本肯定没有"就整本跳过。B-Tree像图书馆卡片柜 — 每格固定大小、原地改卡片, 找书顺着目录 4 层必达, 但每次改都要拿笔涂改还可能换格子 (页分裂)。剩下的都是"给谁快": 行存给"取一行", 列存给"算一列", 倒排给"搜词", 向量给"像不像"。

🧠 必知必会 必考 & 必会

hash index 段

内存 hash 表存 key→文件偏移, 数据追加进日志段; 最简 KV 引擎 (Bitcask 式), 但不支持范围查询。

index = {}                      # key → 文件偏移
index["user:42"] = offset      # 追加后记位置
# get: seek(offset) 一次读 — 快!
# 但 WHERE age > 18? hash 无能为力

SSTable / memtable / LSM

写入先进内存有序结构 (memtable/跳表), 满几 MB 刷成按键排序不可变段 (SSTable); 读时 memtable→新段→旧段 取最新。

mem = {}                        # memtable
mem["user:42"] = data          # 满了 → flush SSTable
# read(key): memtable → bloom → L0→L2 段
# 同 key 多版本 → 取"最新段"的值

compaction 两策略

size-tiered: 小段并大段, 写优但费空间、读可能扫多段; leveled: 逐层按 key range 下推, 读优省空间但合并更频繁。

# tiered: L0:[1MB,1MB,1MB] → 合并成 3MB 段
# leveled: L1 键范围 [a~m] 与 L2 [a~f] 重叠 → 下推
# 同 key 留最新, 清 tombstone, 回收空间

Bloom filter

概率结构只回答"一定不存在": 用于读路径跳过不含该 key 的段。10 bits/key ≈ 1% 误报, 每加 5 bits 误报除以 10。

# m=10 bits/key, k=7 hash → 误报 ~1%
# bloom 说"没有" → 100% 没有, 直接跳段
# bloom 说"有"   → 可能误报, 真去段里查

tombstone

删除 = 写一个墓碑标记: 读到它语义是"不存在"; 物理空间在 compaction 时才回收 — 删 100GB 不是瞬间的事。

put(key, "TOMBSTONE")          # 删除 = 写标记
get(key)                       # 读到墓碑 → 不存在
# compaction 遇到墓碑且无旧值 → 物理清除

B-Tree 结构

固定大小页 (4/8/16 KiB) 是磁盘 I/O 单位, 页号即磁盘指针; 内页子页数叫分支因子 (约数百), 4 层 × 500 × 4KiB ≈ 250TB。

# 点查路径: root → inner → leaf = 3~4 页
# 常驻缓存后 = 内存级点查
# 范围查询: 叶子层顺序扫 — 天生友好

WAL 与 fsync

先顺序写日志并 fsync, 再改页 — 崩溃恢复与复制的基石。fsync 是"持久性开关": 不刷盘, 断电即丢。

# 写事务 = append WAL (fsync) + 改内存页
# 崩溃 → 重放 WAL 恢复到一致点
# 复制: follower 重放同一份 WAL

三种放大

写放大: 1 次逻辑写造成几次物理写 (LSM 高); 读放大: 一次读要碰几个段/页 (LSM 段数, B-Tree 4 层); 空间放大: 实际占用超数据的比例 (LSM 段并存)。

# LSM: 写 1GB 数据物理写 5~20GB (WA=5~20)
# B-Tree: 改一行 = 写 1 页 + WAL (WA≈2)
# 空间: LSM 段并存可到 1.5~2×

聚簇 / 堆 / 二级索引

聚簇: 整行存进主键索引叶子 (InnoDB); 堆文件: 行无序存, 索引存行指针 (PG)。二级索引: 非主键列 → 行定位; 值不唯一, 有回表成本。

CREATE INDEX idx_email ON users(email);
-- InnoDB 二级索引叶 = 主键值 → 回表拿整行
-- PG 二级索引叶 = ctid 行指针   → 回表拿整行

覆盖 / 复合索引

覆盖索引把答案列也放进索引, 免回表; 复合索引 (last, first) 像电话簿 — 只支持最左前缀, 顺序错了就废。

-- 覆盖: 答案全在索引里, 不碰表
CREATE INDEX idx ON orders(user_id, amount);
SELECT user_id, sum(amount) FROM orders
GROUP BY user_id;              -- Index Only Scan

列存与 RLE

按列连续存放、行序对齐: 只读查询涉及的列; 同列取值重复 → bitmap 编码 + 游程压缩, AND/OR 位运算即查询。

# brand 列: [N,N,N,S,S,N,N] → 位图 ×2 → RLE
Nike:  [1,1,1,0,0,1,1]  → 3×1, 2×0, 2×1
# WHERE brand='N' AND qty>10 → 位图 AND

倒排与 trigram

倒排: 词项 → 文档列表 (postings list), 全文检索核心; trigram 把每 3 字符滑窗建倒排, 支持任意子串/正则 (PG pg_trgm)。

# 文档 d1:"数据库系统" d2:"文件系统"
"系统" → [d1, d2]   # postings list
"数据" → [d1]
# 查"数据 系统" = 交集 AND → [d1]

向量嵌入与 IVF/HNSW

文本/图像编码为高维向量, 语义近 = 向量近 (cosine); flat 暴力精确, IVF 质心分区探近邻, HNSW 多层图导航 — 近似换速度。

q = embed("怎么优化慢查询")   # [0.12, -0.9, ...]×768
sim = cosine(q, doc_vec)
# HNSW: 从顶层图贪心下降 → 近邻几跳可达
# 召回 95% + 速度 ×1000 = ANN 的交易

🏭 生产实战 real world

# Python: RocksDB(LSM) 写路径示意
db.put("evt:2026-09-26:dev:8842:1937", payload)  # 追加, 顺序写
db.put("evt:2026-09-26:dev:8842:1938", payload)

# 读取按前缀扫 (range): iterator(prefix) 走有序段
for k, v in db.iteritems(prefix="evt:2026-09-26:dev:8842:"):
    emit(v)

# 调参: memtable 256MB + leveled compaction
# 写吞吐: 机械盘上 ≈ 顺序写极限, 随机更新无惩罚

-- InnoDB(聚簇 B-Tree): 点查 4 次页读, 热数据全在 buffer pool
SELECT balance FROM accounts WHERE id = 10086;
# 执行计划: const, rows=1 — 延迟 P99 稳定 < 1ms

-- LSM 引擎跑同负载的问题:
#   热点 key 反复覆盖 → 段里多版本 → compaction 跟不上
#   读延迟随段数量波动, P99 抖

# 症状: flush 队列堆积, stall (写入被卡) 频发
# 看板: compaction_pending > 20, write_amplification > 25

# 1) memtable 加大, 减少 flush 频率
write_buffer_size = 256MB          # 64MB → 256MB
# 2) leveled + 限速, 把合并 IO 挪出高峰
rate_limit = 200MB/s               # 平滑后台 IO
# 3) 写入侧批量合并: 100 条/批, 放大直接 ÷10

def bloom_fp(bits_per_key, k=7):
    m_n = bits_per_key
    return (1 - (1 - 1/m_n)**k) ** k

for bits in (5, 10, 15):
    print(bits, round(bloom_fp(bits)*100, 2), "%")
# 5 → 7.5%   10 → 0.82%   15 → 0.06%
# 10 亿 key × 10 bits ≈ 1.2GB 内存 — 换掉 90% 的无效段读

-- 错: 跳过最左列, 全表扫
EXPLAIN SELECT * FROM orders WHERE status = 'paid';
-- type=ALL, rows=1024000   ← 没用上索引

-- 对: 带上最左列, 索引范围扫描
EXPLAIN SELECT * FROM orders
WHERE store_id = 7 AND status = 'paid';
-- type=ref, key=idx_store_status, rows=340

-- 建覆盖索引: 查询列全部进索引
CREATE INDEX idx_listing ON products(category, price, stock);

EXPLAIN SELECT id, price, stock FROM products
WHERE category = 'keyboard' ORDER BY price;
-- Extra: Using index ← Index Only Scan, 0 次回表

-- 代价自查: 索引列越多, 写放大与空间越大 — 别把整表塞进索引

# PostgreSQL: synchronous_commit 组提交
# 错: 每事务独立 fsync (commit_delay=0, 低并发下最贵)

# 对: 组提交 — 多个事务攒着一起刷一次盘
commit_delay = 1000      # μs, 等 1ms 攒同伴
commit_siblings = 5      # 活跃事务 ≥5 才启用
# 效果: 200 TPS → 2600 TPS, 持久性语义不变

# 红线: synchronous_commit=off 只能用于可丢会话数据

import pyarrow.parquet as pq
# 行存 10TB → 列存: status 列 99% 是 'paid'
# RLE: 'paid'×999, 'refund'×1 → 编码后几乎为 0

pq.write_table(table, "orders.parquet",
               compression="zstd", use_dictionary=True)

-- 查询只碰 2 列: 10TB 全扫 → 200GB 列段扫描
SELECT status, count(*) FROM orders GROUP BY status;

-- pgvector: 建表 + HNSW 索引
CREATE TABLE docs (id bigint, body text,
                   vec vector(768));
CREATE INDEX ON docs USING hnsw (vec vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

-- 查询: cosine 距离 top 10
SELECT id, body FROM docs
ORDER BY vec <=> $1::vector LIMIT 10;
-- ef_search=64: 召回 96%, 5ms — flat 是 300ms 全扫

-- 三字词滑窗: "mechanical" → mec, ech, cha, han, ...
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_name_trgm ON products
  USING gin (title gin_trgm_ops);

SELECT title FROM products
WHERE title % 'klboard';     % 相似度运算符
-- LIKE '%board%' 也能走 GIN — 而不是全表扫

⚠️ 编码注意与常见坑 pitfalls

# 错: 余额查询放 Cassandra (Dynamo 系 LSM)
# 对: 读稳优先 → InnoDB/PG (B-Tree)

# 错: 无限速灌 50 万写/s
# 对: stall 指标告警 + 后台 IO 限速

# 错: DELETE 5000 万行就收工
# 对: 删除窗口 + 随后 gc_grace 过期压实

# 错: bloom.contains(k) → 直接返回缓存 miss
# 对: bloom 拦截"必无", 其余走正常读

# 错: page_size=64KiB "提升 IO 效率"
# 对: 点查密集 4~8KiB, 顺序扫描可大页

# 错: for log: append; fsync()
# 对: 攒 10ms 一次 fsync (呼应 IO 页组提交)

# 错: fsync=off / wal_level=minimal 混生产
# 对: WAL 全开, 压力走批量与限速

# 错: 20 个索引, 写入 5×放大
# 对: pg_stat_user_indexes 清 idx_scan=0

# 错: WHERE store_id=? 用 idx(status, store_id)
# 对: idx(store_id, status) + store_id 等值在前

# 错: WHERE DATE(created)=today
# 对: 范围改写 / CREATE INDEX ON f(created)

# 错: INCLUDE 12 列的大索引
# 对: 热点查询逐个评估覆盖收益

# 错: v4 UUID 做 InnoDB 主键
# 对: uuidv7 / 雪花 ID (时间前缀, 顺序插入)

# 错: 订单只写 Redis
# 对: Redis 缓存 + 库为 SoR, 或开启 AOF everysec

# 错: 订单交易库选 ClickHouse
# 对: TP 用行存, T+0 同步给列存分析

# 错: user_id 列 bitmap 编码
# 对: status/city 低基数列才 bitmap

# 错: 上线即用, 不测召回
# 对: recall@10 > 0.95 才算达标

# 错: OpenAI embedding + L2 距离
# 对: vector_cosine_ops / 归一化后内积

# 错: hash index 上跑 BETWEEN
# 对: range 列建 B-Tree 索引

# 错: 全库 4096 维 float32
# 对: 768 维 + product quantization

# 错: 用 HBase 做报表聚合扫描
# 对: 宽列存 KV 点查, 分析导出到列存