DDIA Ch.3 存储与检索 — 复习专题¶

梳理自《Designing Data-Intensive Applications》第 2 版 Ch.3 存储与检索（存储引擎）
定位：历史脉络 → 挑战 → 解法 + 哈希 / B+Tree / LSM + Java MVP；从 DDIA 地图拆出，避免单文件过长。
配对：Ch.10 批处理 · Ch.11 流处理

← 返回 DDIA 框架 | 专题索引 | ↑ 总脑图 查询路径 · L4 存储

组件深潜：ClickHouse OLAP · Flink 状态

6h 第 2 段复习清单（45min）¶

对应 ddia-framework § 第 2 段（1:30–2:15）。
节奏：先全景串讲 15min，再按需下潜哈希 / B+Tree / LSM 各一块。

时段	做什么
0–10 min	§ 全景串讲 + 30 秒版（LSM）
10–20 min	B+Tree 图解精讲或哈希索引二选一
20–35 min	另一族 + 选型对照
35–45 min	写下产出；MVP 代码改天

只读这些块（其余扫标题）：

OLTP vs OLAP — 和数仓直接相关
列存储 — 对照 ClickHouse
LSM / B+Tree — 各读「思想」；B+Tree 先看历史动机
LSM：15–20 分钟（30 秒版 + 三个放大 + 选型表）
跳过：全文搜索、图数据库细节

写下来

ClickHouse 在 DDIA 谱系里 ≈ ___________（列存 / OLTP 行存 / …）

完成 Ch.3 跳读

Ch.3 存储与检索¶

场景	存储思路	本专题组件
OLAP 分析、报表	列存、MergeTree、分区	ClickHouse
批处理中间结果	文件 / 对象存储 / 表	Airflow 落盘、Hive 路径
调度元数据	关系库	Airflow Postgres
实时状态	内存 / RocksDB 状态后端	Flink 状态

索引与查询原理（提纲）

日志结构（LSM）  →  写多读少、顺序写
B 树 / B+ 树     →  读多写少、范围查询
列存 + 稀疏索引  →  分析型聚合（ClickHouse）
倒排索引         →  全文 / 日志检索

数据库只做两件事： 1. 向他插入数据时，它把数据存起来 2. 向他查询数据时，他把数据返回给你

从数据库的视角看，该如何存储数据呢，收到查询请求时，怎样重新找到数据呢

为啥应用开发需要了解数据库内部的存储与检索？因为： - 你要选一款数据库、引擎作为存储组件 - 为了实现可扩展性的期望，你要知道如何评估负载、针对负载如何调优

数据库使用场景两大类： - 事务型 OLTP - 分析型 OLAP

存储引擎两大家族： - 日志结构 - 面向页（B-tree）

存储引擎全景：历史脉络 → 挑战 → 解法（串讲）¶

用法：先读这一节建立一条时间线，再按需下潜哈希、B+Tree、LSM 细节与 MVP。
疑问对照框架 QA（Ch.3 相关条目 Q1–Q5）。

一句话主线：磁盘又慢又贵 → 人类不断换 「数据怎么摆、怎么找」，在 读快 / 写快 / 范围查 / 省磁盘 之间做取舍；没有银弹，只有 负载匹配。

0. 起点：数据库只做两件事¶

INSERT / PUT  →  存起来
SELECT / GET  →  找出来

最朴素实现 = 只追加的日志（log）（见 db_set / db_get）：

	表现
写	O(1) append
读	O(n) 扫全日志，取同一 key 最后一条
瓶颈	数据一大，读崩了

第一个挑战：如何在磁盘上 更快找到 一条 key？

1. 哈希索引：用「路标」换读速度（点查为王）¶


年代/场景	早期 KV、今天 Redis / 缓存 / 内存索引层
挑战	日志读太慢；要按 key 一跳到位
解法	内存 `HashMap<key, 文件偏移>` + 磁盘只追加 value log（Tiny Redis MVP）
得到	点查 O(1) 平均；写仍是 append + 更新索引
新代价	内存吃索引；重启要扫 log 重建；无 key 顺序 → 做不了 `BETWEEN` / `ORDER BY key`
典型	Redis（内存）、Riak Bitcask（盘+log+哈希）

一旦业务要 范围、排序、多条件分析，光有哈希不够 → 需要 有序结构。

2. B+Tree：通用 OLTP 的答案（~1972 起）¶


年代/场景	关系库黄金年代至今：MySQL InnoDB、PostgreSQL
挑战	① 数据量大，不能全表扫；② 要点查 + 范围扫；③ 要原地改一行（余额、库存）；④ 磁盘按块读写，不能随便改 1 字节
解法	B+Tree：非叶子当路标，叶子存行 + 叶子链表；一页 = 一个节点（页怎么理解）；树高 O(log_m n)，常只需 3～4 次 I/O（复杂度）
读写模型	写 = 读路径同步做完：找叶 → 页内改/插 → 满则分裂（B+Tree MVP）
得到	点查/插入 O(log n) 页；范围 O(log n + k)；事务、锁成熟
新代价	更新 = 随机写页（HDD 寻道痛；SSD 仍怕碎写）；极高追加写吞吐不如后面 LSM

「有序」在此：按 主键/索引键 排序，不是默认事件时间（§ 有序指什么）。

3. Log-structured / LSM：写吞吐时代的答案（~1992 思想，~1996 LSM）¶


年代/场景	日志、埋点、消息、分布式 KV；Flink RocksDB 状态
挑战	B+Tree 原地随机写页扛不住每秒海量追加；HDD 随机写极慢，SSD 仍偏好顺序块写
解法	写路径拆开：① 前台只追加（memtable → 顺序 flush 成 SSTable）；② 后台 compaction 批量合并（30 秒版）
读写模型	同 key 多次写 = 多版本；读要 memtable + 多层 SSTable 合并取最新
得到	写入顺序 I/O、高吞吐、吸收写突发
新代价	读放大、写放大、空间放大；compaction 堵住 → 延迟抖、磁盘涨

「有序」在此：按 sort key 排，为了 归并 + 范围扫 + 稀疏索引；树/文件 本身就是索引（见 QA Q3）。

思想对照（和 B+Tree 别混）：

	B+Tree	LSM
一次 UPDATE	同步改叶子页	追加新版本，旧的后台 merge
读最新值	叶子即当前	可能查多层
索引	树 = 索引	有序文件 + 稀疏块

4. 并行演化：同一时代还有这些「解法分支」¶

分支	核心挑战	解法	本专题触点
全内存哈希（Redis）	极低延迟、数据能放进内存	哈希 + 可选持久化；工程难点在缓存治理	Redis 生产
列存 + 分区 merge（ClickHouse）	分析扫描 GB/TB、聚合	列存 + 不可变 part + 后台 merge（有 LSM 味道，实现不同）	ClickHouse · 例子 4
倒排索引	全文 / 日志检索	词项 → 文档列表	ES / OpenSearch（提纲未展开）

5. 时间线一图（复习用）¶

timeline
    title 存储引擎演化（简化）
    section 朴素
        追加日志 : 写快读慢 O(n)
    section 点查
        哈希索引 : HashMap 路标 O(1) 无范围
    section OLTP
        B+Tree : 页式树 O(log n) 原地更新 范围查
    section 写吞吐
        LSM/SSTable : 只追加 + compaction 读/写/空间放大
    section 分析/缓存
        列存 MergeTree : 列存 + part merge
        Redis : 内存哈希 缓存语义

6. 选型：用「挑战」反推「解法」（不是背名字）¶

先问负载，再选引擎（总表）：

你的挑战	更倾向
纯 `key → value` 点查，数据能进内存	Redis / 哈希
点查 + value 在盘、key 量可控	Bitcask 类
读多、范围扫、行级 UPDATE、强事务	B+Tree（InnoDB / PG）
写多读少、海量追加、可接受后台 merge	LSM（RocksDB / Cassandra / HBase）
大范围聚合扫描、报表	列存（ClickHouse）

和你栈的映射：

组件	存储思路
MySQL / Airflow Postgres	B+Tree OLTP
Redis	内存哈希
ClickHouse	列存 + part merge
Flink 状态（RocksDB）	LSM
Kafka 日志段	只追加不可变段（思想近 LSM，实现不同）

7. 三档 MVP 对照（把抽象落地）¶

	哈希（Tiny Redis）	B+Tree（SimpleBPlusTree）	LSM（SimpleLsmTree）
历史位置	路标加速读	OLTP 主路径	写吞吐路径
写	append log	原地改叶，满则分裂	append → flush SSTable
读	O(1) 哈希	O(log n) 树	多层合并
范围	❌	✅ 叶子链	✅（多层时更贵）
代码	§ 哈希 MVP	§ B+Tree MVP	§ LSM MVP

8. 读完本节，你应该能口述¶

为啥从 append log 走到 哈希 → B+Tree → LSM（每次都是 上一代的瓶颈 逼出来的）。
B+Tree 和 LSM 不是谁取代谁，是 随机写页 + 读简单 vs 顺序写 + 后台整理 + 读复杂。
「页」「有序」「O(log n)」 各自指什么（链到正文，别混事件时间 / Hashtable）。
你们计费栈里 Postgres / Redis / ClickHouse / Flink RocksDB 各站在哪条分支上。

下潜阅读顺序（建议）：本节 → 哈希索引 → B+Tree → LSM → QA。

数据库核心：数据结构¶

db_set(){
        echo "$1,$2" >> database
}

db_get(){
        grep "^$1," database | set -e "s/^$1,//" |tail -n 1
}

日志更通用的含义：一个仅支持追加写的记录序列

时间复杂度： - 写O1 - 读On

若要提高读效率，就类似于字典等，添加额外的元数据作为路标不过代价除了占用了额外的存储空间外，降低了写速度，因为每新增一条数据就要更新路标以上就是应用人员需要权衡的点。

哈希索引¶

是的，生产里非常常见，但通常用于 精确 key 查询（point lookup），而不是范围分析。

为啥叫 hash？（复习用）

说法	含义
英文 hash	原意「切碎、搅在一起」→ 比喻把任意长的 key 搅成固定长度的数
hash 函数	`hash(key) → 整数`，同一 key 每次结果相同
哈希表 / 哈希索引	用这个整数当桶下标或路标，直接定位，不用全表扫
中文散列	强调 key 被分散到不同桶里

key "user:10086"
    → hash 函数搅一下 → 例如 7283941
    → 对桶个数取模 → 落在第 17 号桶
    → 在桶里存 (key, value 或 offset)

名字听着抽象，干的事很具体：用「搅出来的数」当地址，换 O(1) 左右的点查。
Java 里 HashMap 的 Hash 就是这个意思；业务代码只写 get/put，hash 在 JDK 内部（见下文 Tiny Redis 追问）。

先给结论：

哈希索引擅长：key = ?（等值查询）
哈希索引不擅长：key BETWEEN a AND b（范围查询）、ORDER BY key（有序扫描）

MVP 伪代码（Tiny Redis：追加日志 + 内存哈希索引）

// TinyRedis.java (pseudocode)
//
// 思路：
// 1) value 只追加写入 append-only log
// 2) 内存里维护 key -> offset 的哈希索引
// 3) GET 先查哈希，再按 offset 读日志

class TinyRedis {
    private final RandomAccessFile log;
    private final Map<String, Long> index = new HashMap<>(); // key -> latestOffset

    TinyRedis(String logPath) throws IOException {
        this.log = new RandomAccessFile(logPath, "rw");
        this.log.seek(this.log.length()); // 初始定位到文件尾（append）
        rebuildIndex();                   // 启动时扫日志重建索引
    }

    String set(String key, String value) throws IOException {
        byte[] record = encode(new Record("SET", key, value));
        long offset = log.length();
        log.seek(offset);
        log.write(record);
        log.getFD().sync();               // MVP 简化：每次写后刷盘
        index.put(key, offset);           // 更新哈希索引
        return "OK";
    }

    String get(String key) throws IOException {
        Long offset = index.get(key);
        if (offset == null) return null;
        log.seek(offset);
        Record rec = decode(readOneLine(log));
        return rec.value;                 // 最新值
    }

    String delete(String key) throws IOException {
        // 逻辑删除：写 tombstone，避免随机改写历史日志
        byte[] record = encode(new Record("DEL", key, null));
        long offset = log.length();
        log.seek(offset);
        log.write(record);
        log.getFD().sync();
        index.remove(key);
        return "OK";
    }

    private void rebuildIndex() throws IOException {
        // 重启恢复：线性扫全日志，最后一次 op 覆盖前面的状态
        log.seek(0);
        while (log.getFilePointer() < log.length()) {
            long offset = log.getFilePointer();
            byte[] line = readOneLine(log);
            Record rec = decode(line);
            if ("SET".equals(rec.op)) {
                index.put(rec.key, offset);
            } else if ("DEL".equals(rec.op)) {
                index.remove(rec.key);
            }
        }
        log.seek(log.length()); // 回到文件尾，继续 append
    }

    // --- 伪函数：省略具体序列化/反序列化细节 ---
    private byte[] encode(Record r) { /* ... */ return null; }
    private Record decode(byte[] b) { /* ... */ return null; }
    private byte[] readOneLine(RandomAccessFile f) { /* ... */ return null; }

    static class Record {
        String op;
        String key;
        String value;
        Record(String op, String key, String value) {
            this.op = op;
            this.key = key;
            this.value = value;
        }
    }
}

追问：HashMap 里只看到 Map，hash 在哪？

你写得对：业务代码里只有 index.put(key, offset) / index.get(key)，没有手写 hash(key)。
hash 在 JDK 的 HashMap 内部，被封装掉了。

你写的：                    JDK 内部（简化）：
index.get("user:10086")  →  h = key.hashCode()
                         →  bucket = h & (table.length - 1)
                         →  在 bucket 链表/树里用 equals 找 key
                         →  返回 value（这里是 Long offset）

所以：

你看到的	实际含义
`HashMap` 这个名字	实现方式就是哈希表
`Map` 接口	对外只说「键值映射」，不关心底层是哈希还是树
`put` / `get`	底层在做 hash + 寻址，不是从头遍历所有 key

若把 hash 摊开写（教学用，不必自己实现），等价逻辑大概是：

// 显式哈希索引（示意，非生产代码）
int bucket = Math.floorMod(key.hashCode(), buckets.length);
// 在 buckets[bucket] 里找/放 (key, offset)

结论：Tiny Redis 的「哈希索引」= 你用 HashMap 当索引；hash 在类名和 JDK 实现里，不在你每一行业务代码里。

复杂度（平均）：

SET: O(1)（追加写 + 哈希更新）
GET: O(1)（哈希查 offset + 一次磁盘定位）
DELETE: O(1)
重启恢复：O(N)（N 为日志记录条数）

这个 MVP 故意没做的生产能力：

崩溃一致性（校验和、WAL fsync 策略）
内存控制（大 key 数下 index 膨胀）
compaction（清理旧版本和 tombstone）
并发控制（锁 / 分片锁）
主从复制与高可用

真实生产例子：

Redis（最典型）
核心键空间就是哈希表（dict）
GET user:123 这类点查接近 O(1)
业务场景：会话缓存、热点配置、限流计数器
Riak Bitcask（DDIA 经典例子）
数据追加写入 value log（磁盘）
内存维护 key -> 文件偏移量 的哈希索引（keydir）
读时先查哈希，再按偏移直接定位值
很多 KV 系统/中间件的「内存层」
即使底层是 LSM/B+Tree，前台的热点索引、对象缓存也常用哈希表
场景：用户画像缓存、幂等键表、去重键表

Redis 生产挑战（线上为何不简单）¶

SET/GET 的接口很简单，但线上难点主要在「系统工程」：

挑战	具体问题	常见后果	常见治理手段
内存容量与成本	Redis 主要吃内存，数据增长快	OOM、频繁淘汰、成本飙升	TTL 分层、冷热分离、压缩、key 规范
热点 key / 倾斜	少数 key QPS 过高	单分片打爆、延迟抖动	本地缓存、多副本读、热点拆分
缓存一致性	DB 更新后缓存何时更新	脏读、旧值回潮	延迟双删、订阅变更流、幂等回填
穿透/击穿/雪崩	缓存 miss 放大到 DB	下游数据库被打挂	布隆过滤、互斥重建、随机过期
持久化与重启恢复	RDB/AOF 策略不当	数据丢失窗口大、重启慢	AOF 策略分级、混合持久化、预热
高可用切换	主从切换与脑裂处理	短暂不可用、数据回退	Sentinel/Cluster、超时参数调优
大 Key 与阻塞命令	单 key 过大，`KEYS`/`HGETALL` 全量扫	事件循环阻塞、延迟飙升	bigkey 扫描治理、`SCAN` 替代全量命令
过期与淘汰策略	TTL 不合理或策略不匹配	命中率差、抖动	allkeys-lru/lfu 按业务选择、TTL 随机化
网络与序列化开销	value 太大、跨可用区	RT 增加、带宽贵	value 拆分、批量 pipeline、就近部署
多租户与运维复杂度	权限、限流、监控不足	相互干扰、事故定位慢	资源隔离、慢日志、SLA/告警体系

可以把 Redis 线上问题总结为一句：

功能是 KV，挑战是「缓存系统生命周期管理」：
写入策略、淘汰策略、一致性策略、故障恢复策略。

如果你做的是计费/对账类系统，最容易踩的是这三类：

一致性错觉：以为缓存和数据库总是同步（实际常有延迟窗口）
过期风暴：同批 key 同时过期，瞬时打穿下游
热点 key：单用户/单租户超高并发把一个分片打满

你这两个追问（非常关键）：

Q1：压测去重时 key 短 TTL 很常见，为什么还会「过期风暴」？¶

你说得对：“key 经常过期”本身不是问题。
真正的问题是：大量 key 在同一时刻过期 + 这些 key 又刚好是高频访问，导致下游被瞬时击穿。

可以把它理解成两个维度：

维度	健康情况	风暴情况
过期时间分布	分散（抖动）	集中（同秒/同分钟）
miss 后代价	低（本地可重建）	高（打 DB / 外部服务）

只有同时满足「过期集中 + miss 代价高」，才会形成风暴。

压测去重典型坑（你这个场景非常常见）：

10万请求在 t=0~10s 打进来
去重 key 全部设置 TTL=60s（整秒）
→ t=60s 左右这批 key 同时过期
→ 下一波请求全部 miss，瞬时打到下游

治理手段（去重场景可直接用）：

TTL 加随机抖动：ttl = base + rand(0, jitter)，避免同秒过期
分桶过期：按 hash(key)%N 把 key 分散到不同过期窗口
分层缓存：本地短缓存 + Redis，削峰
miss 互斥重建：同一个 key 只让一个请求回源
容量保护：下游限流 + 熔断，防止雪崩扩散

一句话：你要避免的是 “同步过期”，不是“过期”本身。

Q2：既然有 Bitcask，为啥还会有 Redis？¶

因为它们的目标函数不一样，属于不同工程取舍，不是互相替代。

维度	Redis	Bitcask（Riak）
核心定位	内存数据结构服务器（超低延迟）	磁盘日志型 KV 存储
延迟	通常更低（内存命中）	通常更高（依赖磁盘/OS cache）
数据模型	丰富结构：String/Hash/List/Set/ZSet/Stream	以 KV 为主，模型较单一
持久化角色	可持久化，但常当缓存/状态层	更偏持久化 KV 存储
典型用途	缓存、计数器、限流、会话、队列	持久 KV、分布式容错存储
运维关注点	内存、过期淘汰、热点、复制切换	compaction、磁盘 IO、恢复时间

更直白一点：

你要的是 亚毫秒级访问 + 丰富原子操作（INCR、ZADD、Lua、Stream）→ 更偏 Redis
你要的是 更便宜的大容量持久 KV，可接受更高延迟 → 更偏 Bitcask 类方案

很多系统会两者并用：

Redis：热点与实时状态层（快）
Bitcask/LSM/KV：持久事实层（稳）

HashMap 索引的局限性（你要记这 8 点）：

局限	说明	典型后果
只支持等值查	无序结构	无法高效做范围查询、排序、前缀扫描
内存开销大	指针、桶、装载因子	key 很多时内存压力显著
扩容/rehash 有成本	桶数量变化要搬迁	延迟抖动（有些实现会渐进式 rehash 缓解）
哈希冲突	多 key 落同桶	极端情况下退化，吞吐下降
依赖哈希函数质量	分布不均会倾斜	热桶、热点 key 问题
持久化恢复成本	纯内存索引重启要重建	启动慢（需扫日志重建索引）
删除与更新复杂	需 tombstone/清理策略	长期运行会产生碎片和膨胀
不适合多维条件	只能按单 key 跳转	`where a=? and b>?` 这类查询要靠别的索引

一句话取舍：

如果业务主要是 key -> value 点查，哈希索引非常强；
一旦需要范围、排序、复合条件分析，就要引入 B+Tree / LSM 有序结构或列存索引。

SSTables 和 LSM-Tree¶

为啥要了解？（不必先成为 LSM 工程师）

目的	说明
读懂 DDIA Ch.3	和 B+Tree 对照：两种主流「磁盘上怎么存」的思路
解释线上现象	写入突然变慢、磁盘涨、compaction 卡住、读放大
选型对话	别人提 RocksDB/Cassandra/HBase 时知道在说什么
串你现有栈	Flink 状态后端、部分 OLAP/日志型存储底层常见 LSM 思想

不需要：手写 LSM、背 compaction 算法证明。
需要：能画 4 步流程 + 说出适用场景和 3 个代价。

30 秒版（复习背这个）

写：先落内存 memtable（有序）→ 满了刷成磁盘 SSTable 文件（只追加、不可改）
读：可能查 memtable + 多层 SSTable，合并视图找最新值
维护：后台 compaction 把多层小文件合并成大文件，回收删除/过期数据
代价：写放大、读放大、空间放大（换写入吞吐和顺序写）

SSTable 是什么：Sorted String Table，磁盘上一段按排序键（sort key）有序、不可变的数据文件。
LSM-Tree 是什么：用 多层 SSTable + memtable + compaction 组成的日志结构存储树。

→ 「有序」按哪个字段？ 见下节（不是默认事件时间 / 插入时间）。

「有序」在 memtable / SSTable 里指什么？¶

「有序」= 按你声明的排序键（primary key / sort key）的字节序升序排列——不是默认按事件时间，也不是默认按插入顺序。

常见混淆	实际
按事件时间有序？	只有 `event_time` 在 key 里（如 `(user_id, event_time)`）才算；否则物理顺序 ≠ 事件时间
按插入时间有序？	一般否；除非 key 设计成含 `inserted_at` 或自增 id 当 key
谁决定按什么排？	建表 / 建 CF / 引擎配置时定的 key；RocksDB 的 user key、Cassandra 的 partition+clustering、ClickHouse 的 `ORDER BY` 各有一套名字
和 Flink event time	那是流计算语义；落盘到 RocksDB 后，除非你 key 带上时间，否则存储层不管 event time

排好序是为了什么？（不止「为了范围查询」）

目的	说明
多路归并	flush、compaction 时合并两个已有序文件，线性扫一遍即可
范围查询	`key >= a AND key < b` 在有序段上顺序读，不必哈希全表
缩小区间再查	文件内稀疏索引（每隔 N 个 key 记一个 offset）+ 可选 Bloom filter，减少读盘

「都要排序了，还要索引干什么？」

这里「索引」别理解成「另一张哈希表」——在 B+Tree / SSTable 里，有序结构本身就是在做索引：

结构	「索引」长什么样
B+Tree	整棵树按 key 有序；非叶子 = 路标，叶子 = 数据（或行指针） + 叶子链表做范围扫
SSTable	整个文件 key 有序 + 文件内稀疏 key→offset 块
哈希索引	只有 key→位置，无顺序 → 擅长点查，不擅长 `BETWEEN` / `ORDER BY key`

所以：排序是为了归并、范围扫、二分缩区间；稀疏索引 / Bloom / B+Tree 内部节点是为了 少读盘、快点查。不是二选一，是 一体设计。

为啥会有 SSTable / LSM-Tree？（历史动机）¶

常见误解：「数据天然顺序读写，所以 LSM 更合理，B+Tree 是历史错误。」
实际：按文件顺序扫描 和 按 key 更新某一磁盘页 是两层事；B+Tree 与 LSM 都是在 迁就不同负载下的磁盘瓶颈，不是谁更「符合物理规律」。

时间线：先有 B+Tree，后有 LSM¶

年代	里程碑	当时主流负载
~1972	B-Tree / B+Tree	通用 DB：点查、范围扫、行级 `UPDATE`
~1992	Log-structured 思想（日志结构文件系统）	写路径改成只追加
~1996	LSM-Tree 论文	写多读少、海量追加的 KV / 日志型

所以不是「先选错了结构」，而是 先有 OLTP 式索引需求，几十年后写吞吐才变成主矛盾。

B+Tree 当年为什么合理¶

1970s–1990s 数据库典型问题：

WHERE id = ? — 点查
WHERE created_at BETWEEN … — 范围查询
UPDATE balance … WHERE account_id = ? — 原地改一行

B+Tree：O(log n) 次磁盘读定位叶子页；叶子链表支持 范围扫；节点对齐 OS/磁盘页（4KB/8KB）。
为 读 + 行级更新 + 事务 设计，不是为「每秒百万条只追加、不改旧行」设计。

「顺序」和「随机」各指什么¶

直觉里的「顺序」	数据库里常发生的
从头到尾读一个文件	`UPDATE … WHERE id=12345` — 只动某一页
日志一行行 append	B+Tree：找到 key 所在页 → 读 → 改 → 写回（页在盘上位置固定）
全表扫描	有索引可不扫全表，但改一行仍是定位到特定页

顺序 I/O：磁头/控制器沿连续地址读写的吞吐高。
随机 I/O（B+Tree 更新路径）：很多 不相邻的页 被分别读改写。

LSM 写入：新值顺序 append 到 memtable / 新 SSTable；旧值留着，后台 compaction 再批量整理。

随机写慢在哪？（HDD vs SSD）¶

机械硬盘（HDD）
磁头要 seek 到磁道。随机写 = 改很多分散的页 → 磁头来回跳 → 大量时间耗在寻道上（比顺序写慢 一个数量级 很常见）。

SSD
无机械寻道，但闪存 按页写、按块擦；大量碎小、分散的原地改 → 控制器 读-改-擦-写、写放大。
大块顺序写 仍更省、吞吐更高 → 「SSD 上随机写仍比顺序写贵」= 差距缩小了，没消失。

后来为什么需要 LSM¶

当负载变成：

日志、埋点、消息：只追加、很少改旧行
监控指标：写远大于读
分布式 KV：磁盘上要撑住海量写入

工程师的思路：

别在磁盘上到处改旧页了，新数据一律顺序追加；
旧数据先留着，后台 批量合并（compaction） 再整理。

SSTable = 每次刷下去的那块「排好序、不会再改」的磁盘文件。
LSM-Tree = 用很多层 SSTable + 内存表，组织成一棵「逻辑上有序、物理上分段」的树。

一句话：银行余额频繁原地改 + 事务 → 仍偏 B+Tree；埋点灌库 → 偏 LSM（代价是读/写/空间放大，见下文）。

他们解决了什么问题？¶

痛点（没有 LSM 时）	LSM 的做法	结果
随机写磁盘太慢	写入先缓冲，顺序 flush 成 SSTable	写入吞吐高
写入流量波动	memtable 吸收突发，后台慢慢 compaction	写路径更平滑
删除/更新不想原地改	写新版本，旧版本标记删除，合并时清理	写路径仍 mostly append
单机磁盘要存大量 KV	多层 SSTable 分层，可 compaction 回收空间	成本低于全内存

没解决、或要付出代价的：

读一条 key 可能要查多层 → 读放大
同一条数据多次重写 → 写放大、空间放大
compaction 堵了 → 写入抖动、磁盘涨

是不是「只能」LSM 来解决？¶

不是。 没有银弹，只有 负载匹配。

方案	更适合	例子
B+Tree（原地/页式更新）	读多、范围查询、行级更新、事务	MySQL InnoDB、PostgreSQL
追加日志 + 哈希索引（Bitcask）	纯 KV 点查、value 可落盘、key 量可控	Riak Bitcask
LSM + SSTable	写多读少、追加型、可接受后台 merge	RocksDB、Cassandra、HBase
列存 + 分区 merge	分析型扫描、聚合	ClickHouse MergeTree
全内存哈希（Redis）	极低延迟、数据能放进内存	缓存、计数器

LSM 擅长的是：磁盘上要高写入吞吐，且多数是追加写。
银行转账改余额、库存扣减这种 频繁原地更新 + 强事务，通常仍是 B+Tree 更舒适。

优劣势 + 具体例子（对照理解）¶

例子 1：App 埋点 —— LSM 很合适 ✅¶

场景：每秒 10 万条事件写入，event_id 为主，按天查询某用户轨迹。

写：不断 append 新事件（几乎不改历史行）
读：按 key / 时间范围查一部分

维度	表现
优势	顺序写磁盘，灌库快；和 Kafka / 日志消费模型契合
劣势	范围查可能扫多层 SSTable；要保证 compaction 跟得上

典型组件：Cassandra 写路径、Flink RocksDB 状态（checkpoint 时大量写）。

例子 2：账户余额 —— B+Tree 往往更合适 ✅¶

场景：同一账户行被高频 UPDATE balance，要求强一致、低延迟读最新余额。

写：反复改同一行（随机写页）
读：总是读「当前余额」这一条

维度	表现
若硬上 LSM	同一 key 多版本堆叠，compaction 前读要合并，事务语义更绕
B+Tree 优势	页内原地更新，范围扫、锁、事务成熟（InnoDB）

结论：不是 LSM 不能做，而是 问题形状更像 B+Tree 主场。

例子 3：Flink 作业状态 —— LSM 常见选型 ✅¶

场景：keyBy(user_id) 后维护大量聚合状态，checkpoint 时要持久化到磁盘。

写：checkpoint 周期性地批量刷盘（突发 + 量大）
读：恢复时按 key 加载状态

为何用 RocksDB（LSM）：顺序写友好，比随机更新整棵 B+Tree 更扛得住 checkpoint 写入峰值。
代价：状态过大时 compaction / 磁盘 IO 成为瓶颈，需要调 RocksDB 参数、SSD、增量 checkpoint。

例子 4：计费日批灌 ClickHouse —— 有 LSM 味道，但不是经典 LSM ⚠️¶

场景：每天上亿行明细 INSERT 进 ODS，再 merge 成 part。

写：批量追加 part（不可变段）
维护：后台 merge part（类似 compaction）

和 LSM 的相似：不可变段 + 后台合并。
不同：列存、按列压缩、查询是分析扫描，不是 KV 点查。
排障时：merge 慢、part 过多 → 和「compaction 堵了」同一类直觉。

例子 5：纯缓存会话 —— Neither，Redis 更合适 ✅¶

场景：session:token TTL 30 分钟，纯点查，丢了可重建。

→ 内存哈希 即可，不必 LSM，也不必 B+Tree 落盘模型。

优劣势总表（复习一张表）¶

	优势	劣势
写入	顺序写、高吞吐、吸收突发	写放大（compaction 重写）
读取	点查可接受（尤其带 Bloom filter）	读放大（多层文件）；范围查成本高于 B+Tree
空间	可 compaction 回收	空间放大（多版本、删除标记暂留）
运维	适合日志型、WAL 型思维	compaction 卡住、磁盘膨胀、延迟抖动
事务	可实现，但不如 B+Tree 成熟统一	实现复杂（多组件协调）

哪些场景会用到这块知识？

场景	和 LSM 的关系	你可能在哪遇到
高吞吐写入	顺序 append，比随机改页快	日志采集、埋点 bulk load、CDC 灌库
KV / 宽列存储	Cassandra、HBase、RocksDB 典型 LSM	基础设施选型、Flink 状态（RocksDB）
时序 / 事件流落盘	按时间分区 + 不可变段	Kafka 日志段思想类似（概念相近，实现不同）
数仓明细追加	MergeTree 名字带 Tree，但是列存 + 合并，不是经典 LSM；仍需懂「不可变 part + 后台 merge」	ClickHouse `parts`、merge 变慢
压测 / 运维排障	compaction 堆积 → 写延迟抖、磁盘满	「昨晚写入变差」类事故

和你栈的对照（别混）

组件	更接近哪种思路
Redis	内存哈希，不是 LSM 主路径
Bitcask	追加日志 + 内存哈希索引，不是多层 SSTable
ClickHouse MergeTree	列存 + 分区 + 后台 part 合并（有 LSM 味道，别当同一实现）
Flink + RocksDB	典型 LSM（状态落盘）

需要画大块时间吗？

深度	建议时间	学什么
够用（推荐你现在）	30–45 分钟	上面 30 秒版 + 三个放大 + 一张「何时选 LSM vs B+Tree」
面试 / 架构讨论	+1 小时	size-tiered vs leveled compaction 区别（名词即可）
引擎开发	多天起	自己实现或改 RocksDB 参数调优手册

今天 DDIA 6h 节奏里：Ch.3 跳读 LSM 15–20 分钟足够，把时间留给 Ch.10/11（批/流）更划算。

何时选 LSM vs B+Tree（一句话）

选 LSM 倾向	选 B+Tree 倾向
写很多、读少量 key、可接受后台 merge	读多、范围查询、更新单条记录
顺序写磁盘、吞吐优先	事务行级更新、索引范围扫

三个「放大」——线上为什么会卡（必记）

放大	含义	体感
写放大	同一条逻辑数据多次刷盘、多次 compaction 重写	写入 QPS 不高但磁盘 IO 很高
读放大	读一次要查 memtable + 多层 SSTable	读延迟不稳定
空间放大	旧版本、删除标记在 compaction 前占空间	磁盘占用大于逻辑数据量

待你自己填 1 行（复习用）

我工作里和 LSM 最相关的组件是：________（例如 Flink RocksDB / ClickHouse parts / 无）

MVP 示例代码（Java）：先 SSTable，再 LSM-Tree¶

教学用伪代码：能跑通思路，不是生产引擎。
对应 DDIA：不可变有序段（SSTable）+ 内存表 + 多层合并（LSM）。

示例 1：SimpleSSTable（单个不可变有序文件）¶

// SimpleSSTable.java (pseudocode)
//
// 文件布局（按键字典序写入，打开时建内存索引 key -> fileOffset）：
// [entry][entry]...
// entry = keyLen(int) | key | valueLen(int) | value

class SimpleSSTable {
    private final RandomAccessFile file;
    private final Map<String, Long> sparseIndex = new HashMap<>(); // key -> offset

    // 从有序数据构建并落盘（构建后不可再改）
    static SimpleSSTable build(Path path, SortedMap<String, String> sorted) throws IOException {
        SimpleSSTable table = new SimpleSSTable(path, "rw");
        for (var e : sorted.entrySet()) {
            long offset = table.file.length();
            table.sparseIndex.put(e.getKey(), offset);
            table.writeEntry(e.getKey(), e.getValue());
        }
        table.file.getFD().sync();
        return table;
    }

    // 打开已有 SSTable
    static SimpleSSTable open(Path path) throws IOException {
        SimpleSSTable table = new SimpleSSTable(path, "r");
        table.rebuildSparseIndex();
        return table;
    }

    String get(String key) throws IOException {
        Long offset = sparseIndex.get(key);
        if (offset == null) return null;
        return readEntryAt(offset).value;
    }

    Iterable<String> keys() {
        return sparseIndex.keySet();
    }

    private void rebuildSparseIndex() throws IOException {
        sparseIndex.clear();
        file.seek(0);
        while (file.getFilePointer() < file.length()) {
            long offset = file.getFilePointer();
            Entry e = readEntryAt(offset);
            sparseIndex.put(e.key, offset);
        }
    }

    private void writeEntry(String key, String value) throws IOException {
        byte[] k = key.getBytes(StandardCharsets.UTF_8);
        byte[] v = value.getBytes(StandardCharsets.UTF_8);
        file.writeInt(k.length);
        file.write(k);
        file.writeInt(v.length);
        file.write(v);
    }

    private Entry readEntryAt(long offset) throws IOException {
        file.seek(offset);
        int kLen = file.readInt();
        byte[] k = file.readNBytes(kLen);
        int vLen = file.readInt();
        byte[] v = file.readNBytes(vLen);
        return new Entry(new String(k, StandardCharsets.UTF_8),
                         new String(v, StandardCharsets.UTF_8));
    }

    static class Entry {
        String key, value;
        Entry(String key, String value) { this.key = key; this.value = value; }
    }
}

SSTable 要点：

构建时 一次性排序写入，之后只读
稀疏索引只存 key -> 文件偏移，value 仍在磁盘
适合 顺序写 + 按 key 点查；范围查询可扫 keys()（MVP 未优化）

示例 2：SimpleLsmTree（memtable + 多层 SSTable + 简易 compaction）¶

// SimpleLsmTree.java (pseudocode)
//
// 写路径：put -> memtable（TreeMap 保序）
//        memtable 满 -> flush 成新的 SSTable，放到 levels[0]
// 读路径：memtable -> level0 -> level1 ...（新数据优先）
// 维护：level0 文件数超过阈值 -> compact 合并成更大 SSTable

class SimpleLsmTree {
    private final Path dir;
    private TreeMap<String, String> memtable = new TreeMap<>();
    private final List<List<SimpleSSTable>> levels = new ArrayList<>();
    private int memtableThreshold = 4;   // MVP：4 条就 flush
    private int l0FileThreshold = 2;     // MVP：L0 两个文件就 compact

    SimpleLsmTree(Path dir) throws IOException {
        this.dir = dir;
        Files.createDirectories(dir);
        levels.add(new ArrayList<>()); // L0
        levels.add(new ArrayList<>()); // L1
    }

    void put(String key, String value) throws IOException {
        memtable.put(key, value);
        if (memtable.size() >= memtableThreshold) {
            flushMemtable();
        }
    }

    String get(String key) throws IOException {
        // 1) 先查 memtable（最新）
        if (memtable.containsKey(key)) {
            return memtable.get(key);
        }
        // 2) 再查各层 SSTable（L0 最新文件在前）
        for (List<SimpleSSTable> level : levels) {
            for (int i = level.size() - 1; i >= 0; i--) {
                String v = level.get(i).get(key);
                if (v != null) return v;
            }
        }
        return null;
    }

    void delete(String key) throws IOException {
        // tombstone：MVP 用特殊标记表示删除
        put(key, "__TOMBSTONE__");
    }

    private void flushMemtable() throws IOException {
        if (memtable.isEmpty()) return;
        Path sstPath = dir.resolve("l0-" + System.nanoTime() + ".sst");
        SimpleSSTable sst = SimpleSSTable.build(sstPath, memtable);
        levels.get(0).add(sst);
        memtable = new TreeMap<>();

        if (levels.get(0).size() >= l0FileThreshold) {
            compactLevel0();
        }
    }

    private void compactLevel0() throws IOException {
        // 合并 L0 所有 SSTable -> 一个新的 L1 SSTable
        TreeMap<String, String> merged = new TreeMap<>();
        for (SimpleSSTable sst : levels.get(0)) {
            for (String k : sst.keys()) {
                merged.put(k, sst.get(k)); // 后写覆盖先写（MVP 简化）
            }
        }
        // 清理 tombstone
        merged.entrySet().removeIf(e -> "__TOMBSTONE__".equals(e.getValue()));

        Path out = dir.resolve("l1-" + System.nanoTime() + ".sst");
        SimpleSSTable compacted = SimpleSSTable.build(out, merged);

        // 删除 L0 旧文件，L1 追加新文件
        for (SimpleSSTable sst : levels.get(0)) {
            Files.deleteIfExists(/* sst.path */ Paths.get("placeholder"));
        }
        levels.get(0).clear();
        levels.get(1).add(compacted);
    }
}

LSM-Tree 要点：

组件	作用
memtable	吸收最新写入（内存有序表）
SSTable	磁盘不可变段
多层 level	L0 小文件多，compaction 后沉到 L1 大文件
读	从新到旧查，先命中最新版本
compaction	合并多文件、去 tombstone、回收空间

和 Tiny Redis / 真实 RocksDB 的对照¶

	Tiny Redis（哈希索引）	Simple B+Tree	Simple SSTable	Simple LSM
索引	HashMap 点查	树即索引（按 key 有序）	有序稀疏索引	memtable + 多层 SSTable
写	追加 log + 改索引	原地改叶子页（满则分裂）	批量 build 一次	先 memtable 再 flush
范围查询	❌	✅（叶子链表）	✅（可扫 key）	✅
典型代价	内存、重建索引	随机写页、分裂	文件不可变	读/写/空间放大

LSM MVP 故意没做：WAL、Bloom filter、并发锁、增量 compaction 策略、崩溃恢复细粒度一致性。

B+Tree / B-Tree 存储引擎（与 LSM 对照）¶

为啥要了解？

目的	说明
读懂 DDIA Ch.3	与 SSTable / LSM 并列的另一半：页式、原地更新
日常 OLTP	MySQL InnoDB、PostgreSQL 默认路径
选型	读多、范围扫、行级 `UPDATE`、强事务 → 常仍是 B+Tree
对照 LSM	搞清「写路径一次做完」vs「写与整理拆开」

不需要：手算 B+Tree 分裂公式。
需要：能画 根→叶 查找 + 说出 和 LSM 各擅长什么。

30 秒版（复习背这个）

结构：多叉平衡树；数据（或行指针）主要在叶子；叶子按 key 串成链表
读：从根沿 key 比较 O(log n) 次落到叶子页 → 读行
写：找到叶子页 → 页内改/插 → 满则分裂（可能随机写多个页）
范围：沿叶子链表顺序扫 key 区间
代价：随机 I/O、页分裂；优势：读最新值简单、事务/锁成熟

B+Tree 是什么（和 B-Tree 的差别记一句即可；图解推导见下节）

B-Tree：非叶子节点也可能存数据。设计者 Bayer & McCreight（1972）。
B+Tree（数据库更常见）：只有叶子存数据/行指针；非叶子只做路标；叶子链表 串起来方便范围扫。→ B-Tree 图解精讲
页（page）：磁盘与内存之间 读写的最小常用单位；B+Tree 里 一个树节点通常 = 一页。详见下节。

B-Tree 图解精讲：叶子节点、推导、谁设计的¶

读完本节应能：画出一棵 3 层 B+Tree、说出 叶子 vs 内部节点、解释 为啥数据库几乎都用 B+Tree 而不是 B-Tree。

0. 谁设计的？什么时候？¶

名称	人物 / 时间	备注
B-Tree	Rudolf Bayer、Edward McCreight，1972	论文 Organization and Maintenance of Large Ordered Indexes；在 Boeing 科研实验室为大型索引设计
B 的含义	常说是 Bayer 或 Balanced；Bayer 本人提过与 Boeing 有关	不必纠结字母，记住 1972、为磁盘大块读写而生即可
B+Tree	B-Tree 的变体；约 1970 年代中后期在数据库实现中普及（Knuth TAOCP 等有系统叙述）	MySQL InnoDB、PostgreSQL、SQLite 的聚簇/索引结构都是 B+Tree（不是经典 B-Tree）
和 DDIA 的关系	Kleppmann 讲存储引擎时以 B+Tree vs LSM 对照	不要求背历史，但要知：这是 50+ 年的工程选择，不是某一家数据库拍脑袋

1. 先建立直觉：三种「树」别混¶

flowchart TB
  subgraph bin["二叉搜索树 BST"]
    b1["每个节点 1 个 key + 左右子树"]
    b2["树高 h ≈ log₂(n)"]
    b3["问题：节点小 → 磁盘上要读很多层"]
  end
  subgraph bt["B-Tree（经典）"]
    t1["每个节点一页，塞很多 key"]
    t2["内部节点和叶子都能存「记录」"]
    t3["树高 h ≈ log_m(n)，m 很大"]
  end
  subgraph bpt["B+Tree（数据库主流）"]
    p1["内部节点：只存 key 当路标"]
    p2["叶子：存全部数据 + 叶子链表"]
    p3["范围查询沿叶子扫"]
  end
  bin -->|"磁盘时代"| bt
  bt -->|"范围扫 + 更大扇出"| bpt

概念	一句话
节点（node）	树上的一个「格子」；在数据库里通常 = 一页（16KB 等）
内部节点（internal / non-leaf）	不在最底层；只有路标 key + 子指针，用来往下找
叶子节点（leaf）	最底层；真正存数据（行本身，或 `(key → 行位置)` 指针）
根（root）	最顶上那个节点；整棵树的入口
扇出 m（fanout）	一个节点里大约能指向多少个儿子；m 越大，树越矮
树高 h（height）	从根到叶子的层数；点查大约读 h 次页

叶子为什么叫「叶」？
和植物一样：养分（你的 行数据）在末梢；树干树枝（内部节点）只负责指路，不负责「结果长在树枝中间」——在 B+Tree 里更是强制如此。

2. 推导：为啥不继续用 BST / 哈希？¶

挑战链（和 §2 B+Tree 历史脉络一致）

数据从 1 万行 → 10 亿行
  → 不能全表扫
  → 要能按 key 排序、BETWEEN（哈希做不到）
  → 磁盘一次读 4KB/16KB 一块，不能「只读 8 字节」还划算
  → 要让一次 I/O 里带尽可能多的 key（多叉）
  → 还要树平衡，最坏情况可控（B-Tree 平衡）
  → 范围查询还要顺 key 扫（B+Tree 叶子链表）

数值推导（树高为什么通常是 3～4）

设：

n = 索引里 key 的个数（例如 10⁹ 行）
m = 每个节点平均扇出（一页 16KB，路标 key 很小，m 常取几百）

叶子层要能放下 n 个 key，需要层数 h 满足：

m^h ≥ n   ⇒   h ≥ log_m(n)

n	m = 100	m = 500
10⁶	h ≥ 3	h ≥ 2
10⁹	h ≥ 5	h ≥ 3～4
10¹²	h ≥ 6	h ≥ 4～5

结论： 不是魔法，是 「一层把 key 空间切成 m 份，叠 h 层」；m 一大，h 就矮，点查只要 h 次磁盘读。

3. 结构图：B-Tree vs B+Tree（同一组 key）¶

假设 key = {5, 12, 20, 25, 30, 40}，极简 2 层示意（真实节点一页能装远多于 6 个 key）。

经典 B-Tree（数据可能在内部节点）

flowchart TB
  root["根节点<br/>key: 25"]
  i1["内部<br/>key: 12"]
  i2["内部<br/>key: 30"]
  L1["叶子 5"]
  L2["叶子 12, 20"]
  L3["叶子 25"]
  L4["叶子 30, 40"]
  root -->|"< 25"| i1
  root -->|">= 25"| i2
  i1 --> L1
  i1 --> L2
  i2 --> L3
  i2 --> L4

注意：有的教材画 内部节点也带记录（例如 key=12 的行就挂在内部），实现杂，数据库很少用纯 B-Tree。

B+Tree（DDIA / InnoDB 心智模型）

flowchart TB
  root2["根（只路标）<br/>keys: [25]"]
  int1["内部<br/>keys: [12]"]
  int2["内部<br/>keys: [30]"]
  leaf1["叶子: 5"]
  leaf2["叶子: 12, 20"]
  leaf3["叶子: 25"]
  leaf4["叶子: 30, 40"]
  root2 --> int1
  root2 --> int2
  int1 --> leaf1
  int1 --> leaf2
  int2 --> leaf3
  int2 --> leaf4
  leaf1 -.->|next 链表| leaf2
  leaf2 -.-> leaf3
  leaf3 -.-> leaf4

对比	B-Tree	B+Tree
数据在哪	内部 + 叶子都可能	只在叶子
内部节点	key + 数据 + 指针	只有 key + 指针（路标）
内部节点的 key	可能「代表」子树范围	常是分隔符（「往左 < k，往右 ≥ k」）
范围查询	要中序遍历树	沿叶子链表顺序扫
扇出	内部节点胖 → m 偏小	内部节点瘦 → 同一页能放更多指针 → 更矮

「叶子链表」解决啥？
找到 key ≥ 12 的叶子后，不必再「爬树找下一个 key」，直接 leaf → leaf.next 扫——对应 SQL WHERE id BETWEEN 12 AND 40。

4. 点查走一遍：`WHERE id = 25`¶

以 B+Tree 为例（InnoDB 聚簇索引同理）：

sequenceDiagram
  participant Q as 查询
  participant R as 根页
  participant I as 内部页
  participant L as 叶子页
  participant D as 行数据
  Q->>R: 读根（1 次 I/O）
  Note over R: 25 在 [12, 30) 之间？<br/>比较 key 选子指针
  Q->>I: 读内部页（第 2 次 I/O）
  Q->>L: 读叶子页（第 3 次 I/O）
  L->>D: 页内二分/扫描找到 id=25 的行

页内发生什么（每层 O(1) 次比较，因页大小固定）

根：    [ · | 12 | · | 25 | · | 30 | · ]  → 选「25 所在区间」的指针
内部：  同上，再缩小区间
叶子：  [ (12,row) (20,row) (25,row) ... ]  → 命中 row

I/O 次数 ≈ 树高 h，不是 O(n) 扫全表。

5. 插入与分裂：为啥会「长个子」？¶

步骤（插入 key=22）

同点查 落到应插入的 叶子页（O(h) 读）。
叶子里 有空位 → 插入，结束（可能 1 次写脏页）。
叶子满了 → 分裂（split）：

flowchart LR
  subgraph before["分裂前：叶满"]
    P["叶子页<br/>12,20,22,25,30"]
  end
  subgraph after["分裂后"]
    P1["左叶<br/>12,20,22"]
    P2["右叶<br/>25,30"]
    PAR["父节点插入分隔 key 25"]
  end
  before --> after

把 分隔 key（通常是 右叶最小 key 或中间 key，实现细节因引擎而异）插入父节点。
父也满 → 继续向上分裂；若根分裂 → 树高 +1（多一层）。

为啥这么设计？

设计	原因
多叉、一页一节点	对齐磁盘块；一次 I/O 带一堆 key，压低 h
平衡（所有叶同深）	最坏查找仍是 O(log n)，不会退化成链表
分裂而不是无限拉长一页	页大小固定（16KB），buffer pool 才能管理；太大则 I/O 浪费
B+Tree 数据只在叶	内部节点更瘦 → 更大 m → 更矮 h；范围扫走链表

代价（和 LSM 对照）
分裂 + 原地改页 → 随机写 多个页；高并发更新时页锁竞争——这是后来 LSM 用追加换整理 的动机，不是 B+Tree 设计失败。

6. 一页里长什么样？（和页（page）衔接）¶

┌────────────────────────────────────── 16KB 页 ──────────────────────────────────────┐
│ 页头：校验和、LSN、前后指针…                                                          │
│ 索引项目录（稀疏/稠密）                                                                │
│ [ key₁ | 子页号₁ ] [ key₂ | 子页号₂ ] …     ← 内部节点：路标 + 指针                  │
│ 或                                                                                   │
│ [ key₁ | row₁ ] [ key₂ | row₂ ] …           ← 叶子：key + 行（聚簇）或 key + 主键指针   │
│ 叶子还有：next_page_id → 下一叶子（范围扫）                                            │
└──────────────────────────────────────────────────────────────────────────────────────┘

聚簇索引（InnoDB）：叶子 = 整行；二级索引 叶子 = (索引列, 主键)，再回表到聚簇叶找行。

7. 自测（能否讲给别人听）¶

叶子节点存什么？ → B+Tree：真实行或指针；内部节点：不存用户行。
为啥 h=3 就够上亿行？ → m 大，m^h ≥ n。
B+Tree 比 B-Tree 多啥？ → 叶子链表 + 数据只在叶。
谁设计的？ → Bayer & McCreight，1972；数据库主流用 B+Tree 变体。
和 LSM 根本分歧？ → B+Tree 同步改旧页；LSM 追加新文件再合并（见优劣势总表）。

页（page）怎么理解？¶

一句话：页 = 数据库按 固定大小的一块（常见 4KB / 8KB / 16KB）从磁盘搬进内存、或写回磁盘；B+Tree 的节点就长在这一块里。

类比	页在干什么
图书馆	不是一次搬一整书架，而是按「一本合订册」借还——册子大小固定，方便编号、搬运
快递	按标准箱装货，车一次运一箱；箱大小和车、叉车对齐
你 MVP 里的 `Page` 类	逻辑上的「一块节点」；真数据库还会把这块序列化到磁盘某个偏移，并放进 buffer pool（页缓存）

和三个概念别混

概念	是什么
页（DB page）	存储引擎定的块，如 InnoDB 16KB 一页
操作系统页（4KB）	内存管理单位；DB 页往往是 OS 页的整数倍
B+Tree 节点	逻辑结构；实现上通常 1 节点 = 1 页，所以文档里常混说「读一页」「读一个节点」

为啥非要「页」，不能一行一行读？

磁盘 / SSD 对 整块读写 最划算；一次 I/O 读 16KB，里面可以塞 很多 key 路标或很多行，摊薄寻道/命令开销。
点查 WHERE id=100：往往 读 3～4 页（根→内部→叶子），不是读「整表」。

读 / 写时发生什么

读：磁盘第 N 页 → 拷进内存 buffer pool → 在页内二分/扫描找 key
写：找到页 → 在内存页里改 → 标脏 → 稍后刷回磁盘同一页号（或分裂成两页）

和 LSM 的「页」

	B+Tree	LSM
主要单位	页（原地改某一页）	SSTable 文件（顺序 append 新块，旧块不改）
更新一行	常改该行所在那一页	写新记录到新 memtable/SSTable

「有序」在 B+Tree 里指什么？

与 SSTable 的有序 同一概念：按 索引键（主键 / 聚簇键） 排序。
PRIMARY KEY (user_id) → 树按 user_id 有序；WHERE user_id BETWEEN … 走叶子链表。
二级索引是 另一棵（或一棵的）B+Tree，叶子存 主键指针，再回表。

读写路径 + 时间复杂度

点查 WHERE pk = ?

根页 → 比较 key，选子指针 → … → 叶子页 → 页内找到行
磁盘读次数 ≈ 树高 h（通常 3～4 层）

更新 UPDATE … WHERE pk = ?

同上找到叶子页 → 在页内原地改（或插入新行、标记旧行）
页满 → 分裂：新页、父节点加指针 → 可能向上传播分裂
对磁盘：常是 改固定几页的随机写（不像 LSM 只 append 新文件）

范围 WHERE pk BETWEEN a AND b

定位到 a 所在叶子 → 沿叶子链表扫到 b

读写都是 O(log n) 吗？log 的底是谁？¶

结论（先背）

操作	相对 key 总数 n	相对磁盘 I/O（页）	说明
点查	O(log n)	O(h) 次，h = 树高	每层下潜一页
插入 / 更新（含分裂）	O(log n)	O(h) 最坏（分裂一路到根）	先找叶子 O(h)，再最多分裂 O(h)
范围扫	O(log n + k)	O(h) + 扫 k 个叶子项	k = 命中行数，不是纯 log n

这里的 n = 索引里 有多少个 key（行/记录数），不是页数。
log n 在教材里常写成 O(log_m n)：m = 扇出（branching factor），一页里能放大约 m 个子指针或 O(m) 个 key。

为啥是 log n？（推导树高 h）

B+Tree 每层把 key 空间 大约切成 m 份（m 由页大小决定，InnoDB 一页 16KB 时常有几百个路标）：

第 0 层（根）     ：1 页，覆盖整棵索引
第 1 层           ：最多 m 页
第 2 层           ：最多 m² 页
…
第 h 层（叶子）   ：最多 m^h 页，存 n 个 key

要能放下 n 个 key，需要：

m^h ≥ n   →   h ≥ log_m(n)

所以 树高 h = O(log_m n)。大 O 里底数 m 当常数时，就写成 O(log n)。

数值直觉（体会为啥生产里 h 很小）：

n（行数）	m≈500 时 h ≈ log₅₀₀(n)
10⁶	≈ 2
10⁹	≈ 3～4
10¹²	≈ 4～5

读一条 key 为啥 O(log n)？

从根开始，最多 h 层；
每层：在 一页内 用 key 比较选一个子指针（页内二分，页大小固定 → 页内 O(log m) = O(1) 常数）；
落到叶子，页内再找到该行。

磁盘 I/O 次数 ≈ h = O(log n)（每层读 1 页）。
CPU 比较次数 ≈ h × log m，m 固定时也是 O(log n)。

写（插入/更新）为啥也是 O(log n)？

查找叶子：同读，O(h) = O(log n) 页；
页内插入或覆盖：页大小固定 → O(1)；
页满分裂：新页 + 把一个 分隔 key 插进父节点；父也满则继续向上，最多到根。

一条路径上 最多分裂 h 次 → 再 O(h) 页写。
合计：O(h) = O(log n) 次页访问（最坏；均摊分析下插入仍是 O(log n) 量级）。

不是 O(log n) 的情况（别背错）

场景	复杂度
`WHERE pk BETWEEN a AND b` 命中 k 行	O(log n + k)，沿叶子链表扫 k 个
全表扫描（不用索引）	O(n)
哈希索引点查	O(1) 平均（但没有 key 顺序）

和 MVP SimpleBPlusTree 的关系

代码里 findLeaf 是 while 下降一层，层数 = h；ORDER 很小时 h 相对大，但 渐近仍是 O(log n)。生产用大页、大扇出，常数项更小（h=3～4）。

解决了什么问题？

痛点	B+Tree 的做法	结果
海量数据仍要点查	树高 O(log n)，每层一页	几次 I/O 定位一行
范围查询	叶子链表按 key 顺序	`BETWEEN`、ORDER BY 主键高效
行级更新、事务	页级锁 / MVCC + 原地或版本链	InnoDB / PG 成熟生态
读「当前最新值」	叶子上一行即最新（无多层版本合并）	读路径直观