数据库范式与存储引擎：从关系型到向量库

同一份订单在 MySQL、Redis、Elasticsearch、Milvus 里长成四副面孔——一份行、一个键值、一份 JSON、一串 1536 维小数。为什么同一件事要落到四个截然不同的库？每种库到底动了什么手脚，让磁盘上的字节能被以完全不同的方式检索？这不是"哪个数据库最好"的问题，而是"什么数据形状、什么查询模式、什么一致性要求，决定了什么存储结构"——七大范式与它们背后的一层通用抽象（页 → 磁盘指针 → 缓冲池 → WAL），是本篇要串通的主线。

场景问题

打个比方（页与磁盘指针）：数据库把数据存到磁盘上，从来不是"一条一条散落"，而是像图书馆——先按楼层号（page id） 分区，每层再按书架槽位（slot / line pointer） 上架；索引记录的是"这本书在 8 楼 42 号槽"，而不是"这本书叫《三国演义》"。查一行就是先按 page id 把整页从磁盘捞到缓冲池、再按 slot 拿到那一行——这就是磁盘指针的具体形态：(page id, offset) 一对。B+ 树的非叶子节点为什么"只存 key + 指针"扇出大？为什么"随机 IO 比顺序 IO 慢两个数量级"？答案都在这层抽象里。类比失效边界：图书馆的书目录是给人翻的，数据库的索引是给 CPU 用的——真实系统里"槽指针"可以在页内自由挪动（页压缩、页分裂时批量重排），只要页外指针（page id） 稳定；一旦页 id 也变（页迁移、B+ 树平衡），二级索引又得跟着更新，这就是 InnoDB 二级索引"叶子存主键而不是行指针"的原因。

打个比方（索引结构选型）：想象你在整理笔记。B+ 树像装订成册的字典——按拼音排好序、每一页有指向下一页的指针，查"张三"能翻到、想找"张 X"也能翻到，但每次新增一个字都要撬开某一页往里塞（页分裂），越写越慢。LSM 树像先在草稿本上追加（MemTable）、写满一本就合订成正式笔记（SSTable），期间只追加从不修改，写起来飞快，但代价是查"张三"得把最近几本草稿到多年前的正式册全翻一遍（读放大）。两种结构一个偏读一个偏写，是所有主流数据库最本质的取舍。类比失效边界：LSM 用 Bloom Filter + 分层 Compaction 大幅压掉读放大，实际生产里 RocksDB / TiKV 的读性能远比"翻十本笔记"要好；B+ 树也用批量插入 + change buffer 缓解页分裂，两者不是水火不容。

数据库面试的高频追问，其实都是同一张图上的不同位置：

实现方案

一、七大范式（横向：数据形状怎么选）

每一类范式都用五要素定位：数据形状 / 典型查询 / 一致性与事务 / 分片方式 / 何时选它。

1. 关系型（RDBMS）

• 数据形状：行式存储 + 关系模式（schema-on-write）——建表时定死字段与类型，之后每行都必须符合 schema。
• 典型查询：SQL 的 SELECT/JOIN/GROUP BY，本质是关系代数（投影 / 选择 / 连接 / 聚合）在字节上的落地。
• 一致性与事务：强 ACID，单机默认可达可串行化（Serializable），InnoDB 默认 RR（可重复读）叠间隔锁堵幻读——这是所有数据库里事务能力最强的一档。
• 分片方式：垂直拆分（按业务模块拆表）、水平分片（按主键 hash / range 拆表）、中间件（Vitess、ShardingSphere）。分片后跨片事务能力大幅退化——所以强 ACID 与水平扩展是关系型的天然矛盾。
• 何时选它：金融/交易/账务/订单——凡是"多字段配合、跨行原子性、外键约束"是硬需求的场景。
• 代表产品：MySQL、PostgreSQL、Oracle、SQL Server。
• 具体实现视角：见 MySQL InnoDB 索引与事务——B+ 树 / 聚簇索引 / MVCC / 隔离级别的深水区。

2. 键值（KV）

• 数据形状：扁平 key → value——value 可以是简单字符串（etcd）也可以是丰富数据结构（Redis 的 String/Hash/List/Set/ZSet/Stream）。
• 典型查询：GET/SET/DEL 为主，部分产品支持范围（有序 KV，如 etcd 前缀扫描）与集合操作（Redis ZRANGE）。
• 一致性与事务：内存优先，可选持久化——Redis RDB/AOF 快照 + 追加日志、etcd Raft 强一致复制。事务范围通常限单 key 或单 slot（Redis MULTI/EXEC + Lua）。
• 分片方式：哈希分片 + 一致性哈希是天然搭档。Redis Cluster 用 16384 slot 把 key 空间预划分好，客户端直连；etcd 走 Raft 强一致复制，不做水平分片（跨集群靠 mirror）。
• 何时选它：缓存、会话、分布式锁、限流计数、Feature Flag、服务发现（etcd/Consul）。扁平 key 让水平扩展与故障隔离都便宜。
• 代表产品：Redis、etcd、Consul、DynamoDB、Memcached。
• 具体实现视角：见 Redis 版本演进 & 分布式——单线程模型 / Cluster / 分布式锁 / 缓存三板斧。

3. 文档型（Document）

• 数据形状：BSON/JSON 文档 + schema-on-read——字段可以随文档不同，同一集合内文档 A 有 phone 字段、文档 B 可以没有。
• 典型查询：MongoDB Query Language（db.orders.find({user_id: 42, status: "paid"})）、Elasticsearch DSL（bool query + filter + aggs）。任意字段可建索引，包括数组、嵌套字段。
• 一致性与事务：单文档天然原子（BSON 是一次写入的整体）；跨文档事务 MongoDB 4.0+ 支持副本集事务、4.2+ 支持分片事务，但性能与关系型仍差一档。
• 分片方式：按 shard key 做范围分片（顺序扫描友好）或哈希分片（打散热点）——shard key 一旦选错，事后重分片代价极高（MongoDB 5.0 前甚至不允许改 shard key）。
• 何时选它：字段稀疏、频繁演进（新增字段不用改表）、聚合层级明显（订单 → 商品数组这类嵌入结构）。产品目录、用户画像、CMS、日志是最常见场景。
• 代表产品：MongoDB（通用文档）、Elasticsearch（全文检索 + 文档 hybrid）、CouchDB、Amazon DocumentDB。
• 常见误解："文档型是无 schema"——错。文档型是把 schema 从写侧挪到读侧，读代码里仍然要处理"这个字段可能不存在"的分支。所谓"灵活"是灵活地把痛点转嫁到应用层。

4. 宽列（Wide-column）

• 数据形状：Row Key + 列族（Column Family）+ 列限定符（Column Qualifier） 三级结构——同一个 Row Key 下的列可以动态增删，一行"宽"到百万列都合法。
• 典型查询：按 Row Key 前缀扫描（顺序读非常快），按列族拉取部分列。不支持复杂 JOIN 与二级索引（HBase 二级索引要靠外部方案，Cassandra 的 SASI/物化视图有代价）。
• 一致性与事务：LSM 树引擎（写优先，与 B+ 树相反的哲学）；Cassandra 可调一致性（W+R>N 仲裁）、HBase 走单行强一致。
• 分片方式：按 Row Key 顺序分区（Region/Range）——天然对范围扫描友好，代价是 Row Key 设计不当（比如时间戳单调递增作前缀）会产生"最热的分区总是最新那个"的热点。
• 何时选它：超大规模写入（每秒百万级）、时序/日志/物联网数据、按主键顺序扫描（时间线、埋点、消息元数据）。
• 代表产品：Apache Cassandra、Apache HBase、Google Bigtable、ScyllaDB（Cassandra 兼容的 C++ 重写）。

5. 时序（Time-series）

• 数据形状：时间戳（timestamp）为主索引 + 标签（tags/labels）作二级索引 + 数值型 field——一个"时间点 + 一组标签 + 一组测量值"是最小写入单元。
• 典型查询：时间范围 + 聚合（rate / sum / avg / quantile / topk），几乎没有点查——用户想看的是"过去 5 分钟 CPU 曲线"，不是"12:34:56 那一秒的 CPU"。
• 一致性与事务：写多读少，批量写入 + 最终一致是主流；不支持事务（时序库压根不需要跨点事务）。
• 压缩优化：这是时序库的立身之本——Gorilla 压缩（Facebook 论文）对时间戳用 Delta-of-Delta（一阶差分相同就只存 0 bit）、对浮点值用 XOR 编码（相邻值 XOR 后前导零 + 尾部零很多），实测 10-30× 压缩比不稀奇。
• Downsampling：老数据自动降采样（一分钟一个点 → 一小时一个点 → 一天一个点），既省存储又加速查询——典型的"数据老化即降精度"策略。
• 分片方式：按时间范围 + 标签 hash 复合分片。
• 代表产品：InfluxDB TSM（专用引擎，商业化最成熟）、Prometheus TSDB（单机为主，配 Thanos/VictoriaMetrics 做水平扩展）、TDengine（国产，专攻 IoT 场景）、TimescaleDB（PostgreSQL 扩展）。

6. 图（Graph）

• 数据形状：节点（Vertex）+ 边（Edge）+ 属性（Property）——节点和边都可以带任意 KV 属性。
• 典型查询：多跳遍历（"我的朋友的朋友"）、最短路径、社群发现、模式匹配。查询语言 Cypher（Neo4j）、Gremlin（Apache TinkerPop）、GQL（ISO 标准）。
• 一致性与事务：Neo4j 单机强 ACID；分布式图库（JanusGraph、NebulaGraph）事务能力较弱。
• 免索引邻接（Index-free Adjacency）——图数据库的立身根本：每个节点直接持有邻居的物理指针（而不是靠"WHERE friend_id = 42"这种索引查找），遍历 N 跳的成本约 O(N × avg_degree)，而不是关系型 JOIN 的 O(N × logM) 那种嵌套查找。这就是"社交关系里 6 度分离查得比 SQL 快百倍"的物理原因。
• 分片方式：图分片是难题——切边容易切孤立、切点容易切热点，多机分布式图库的性能损耗普遍在 50% 以上。
• 何时选它：社交关系、知识图谱、欺诈检测（可疑资金流转路径）、推荐系统的多跳召回。
• 何时不选它：如果本质上是"两张表 JOIN 一下"（比如"用户 → 订单"这种一对多关系），直接 SQL 反而更简单——不要为了用图而用图。
• 代表产品：Neo4j（老牌单机强）、JanusGraph（分布式）、NebulaGraph（国产分布式 C++）、TigerGraph、Amazon Neptune。

7. 向量（Vector）

• 数据形状：高维稠密向量（通常 384 / 768 / 1536 维，来自 embedding 模型）+ 相似度度量（cosine / L2 / inner product）。
• 典型查询：给一个查询向量，找最相似的 top-K 个向量——语义搜索、以图搜图、RAG 检索的召回环节。
• 为什么用 ANN 而非精确 k-NN：维度诅咒——高维空间里"精确最近邻"退化成全表扫描（各种基于树的空间划分在高维失效），必须走近似最近邻（Approximate Nearest Neighbor）——牺牲一点召回率换回 100-1000× 的加速。
• 一致性与事务：几乎没有——向量库大多是"批量写 + 高并发读"的模型。
• 分片方式：按向量 ID 哈希 + 元数据过滤，Milvus/Qdrant 都有原生水平扩展。
• 索引结构：三大家——HNSW（图索引，读快内存大）、IVF（倒排 + 聚类，写快召回略低）、PQ / IVF-PQ（乘积量化压内存），详见下方 向量索引三家 小节。
• 代表产品：Milvus / Qdrant / Weaviate（专用向量库）、pgvector / Elasticsearch dense_vector（关系库/搜索库扩展向量能力）、Pinecone（云托管）。
• 何时选它：RAG（检索增强生成）的召回环节、语义搜索、推荐系统召回、以图搜图、去重与近似查找。

二、存储层通用抽象（纵向：所有引擎共有的一层）

前面七种范式各自选了不同的索引结构，但它们共有的存储层抽象只有一层：页（Page） → 磁盘指针 → 缓冲池 → WAL。

2.1 页与磁盘指针——所有引擎的物理基石

页（Page） 是数据库与磁盘/操作系统交互的最小单位——不是"一行"，而是"一页"。各引擎默认页大小：

页内组织方式（以 InnoDB / PostgreSQL 为例）：

┌────────────────────── Page (16 KB) ──────────────────────┐
│ Header (页元数据: page id, LSN, checksum, ...)          │
├─────────────────────────────────────────────────────────┤
│ Slot Directory (页尾): [slot0 → offset]                 │
│                        [slot1 → offset]     ← 页内槽表  │
│                        [slot2 → offset]                 │
├─────────────────────────────────────────────────────────┤
│ Free Space (未使用空间，写入时向下增长)                │
├─────────────────────────────────────────────────────────┤
│ Row N     (页体: 行记录从页首向下增长)                  │
│ Row 2                                                    │
│ Row 1                                                    │
│ Row 0                                                    │
└─────────────────────────────────────────────────────────┘

磁盘指针 = (page id, offset / slot) 一对——这就是它具体的样子：

• page id：定位到"哪一页"（相当于图书馆的楼层号）。InnoDB 里是 space_id + page_no 32-bit 组合。
• offset / slot：定位到"页内的哪一行"（相当于书架槽位号）。页内可以自由压缩重排，但槽号稳定。

为什么 B+ 树的非叶子节点只存 key + 页指针、扇出能到几百上千？——因为一个 16 KB 的非叶子页塞满了 (key, page_id) 对，每对约 20 字节，一个页能容纳 800+ 分支。树高 ≈ 磁盘 IO 次数：3 层 B+ 树就能索约 2000 万行，这是关系型数据库能靠一次查询 2-4 次 IO 定位任意行的物理根基。

页分裂与页合并：写入超过页容量时，InnoDB 会页分裂（split）——把一页拆成两页，把中间一半数据搬走，代价是产生随机 IO 与二级索引的连锁更新（如果二级索引存的是行指针而非主键，就得全部改一遍——这就是 InnoDB 二级索引"叶子存主键而不是行指针"的选择动机）。相反，删除多了就页合并（merge），维持树高稳定。

2.2 缓冲池与页缓存——"把最热的页留在内存"

页在磁盘上、访问它得先"读到内存里"——这就是 Buffer Pool / Page Cache 的角色：

淘汰策略远比"朴素 LRU"精细，因为朴素 LRU 有扫描污染问题：一次全表扫描把整个缓冲池的热点数据全冲掉了。工业界的对策：

• LRU-K：记录最近 K 次访问，只有访问频繁的才能"晋升"到热区。
• CLOCK / Second Chance：用时钟指针 + 引用位近似 LRU，代价更低。
• InnoDB midpoint LRU：把 LRU 链表分成 5/8 老年代 + 3/8 新生代，新读入的页先进老年代——被再次访问才晋升到新生代，天然抵御一次性扫描。

Dirty Page + Checkpoint：写操作先改内存中的页（脏页）、后台异步刷盘；Checkpoint 定期把"这个时刻以前的脏页都已经刷完了"的水位线推进——一旦崩溃，redo log 从 Checkpoint 位置往后重放即可。

随机 IO 为什么比顺序 IO 慢两个数量级——是所有索引优化的原初动机：

• HDD：磁头寻道（几毫秒）+ 旋转延迟（几毫秒），随机 IO ~100 IOPS，顺序读能到 100+ MB/s。
• SSD：无机械延迟，但 NAND 是页读、块擦除（读 4 KB，擦除 256 KB），随机小写会触发"擦除 + 重写"的写放大，顺序写显著更快。

这就是为什么 B+ 树要设法把"相邻的行"放到"相邻的页"（聚簇索引），LSM 要"顺序追加而非原地更新"——都在把随机 IO 转成顺序 IO。

2.3 WAL 与写入路径——崩溃恢复的根基

Write-Ahead Log 的核心承诺就一句话："日志先落盘，数据页可以之后再刷。" 写路径大致是：

用户写入 ──▶ 内存页变脏 (Buffer Pool 里)
             ├──▶ WAL 追加写 (顺序 IO) ──▶ fsync 到磁盘 ✓  ← 事务此时可返回成功
             └──▶ 后台异步刷脏页 (随机 IO)
                     └──▶ Checkpoint 推进水位线

WAL 的两个红利：

1. 崩溃恢复：崩溃时数据页可能只刷了一半，但 WAL 是顺序追加、边界明确——从 Checkpoint 往后重放 WAL 就能把数据页修复到崩溃前一刻。这是 WAL 的立身之本，不是性能副产品。
2. 随机写变顺序写：数据页的修改是分散的（B+ 树各处随机页），WAL 是单一文件顺序追加——把成百上千次随机写"打包"成一条顺序日志，磁盘友好度天差地别。

Double Write / Full-page Write：如果一个 16 KB 数据页在写到一半时崩溃（partial page write），页内容既不是新的也不是旧的——WAL 记录的是逻辑操作，无法修复"物理上写坏了的页"。对策是 InnoDB 的 doublewrite buffer（先写一个连续 2 MB 区域再写目标页）、PostgreSQL 的 full-page write（每个 checkpoint 后第一次修改整页写入 WAL）。

同一思路的不同名字：MySQL redo log / PostgreSQL WAL / Redis AOF / Cassandra CommitLog / MongoDB WiredTiger journal / RocksDB WAL——都是 Write-Ahead Log。

2.4 读写放大：三维取舍

同样一份用户数据落到磁盘，实际读写字节数往往是逻辑量的几倍——这就是三维放大：

• 写放大（Write Amplification）：一次逻辑写引发多少倍的物理写？B+ 树的写放大来源：页分裂 + doublewrite + WAL；LSM 的写放大来源：Compaction 反复重写同一份数据。
• 读放大（Read Amplification）：一次逻辑读引发多少次物理读？LSM 的读放大来源：查一个 key 可能要扫 MemTable + L0-Ln 每一层 SSTable（靠 Bloom Filter 大幅缓解）；B+ 树的读放大约等于树高 3-4。
• 空间放大（Space Amplification）：磁盘上存的字节数除以逻辑数据大小？LSM 的空间放大来源：删除是插入 tombstone、更新是插入新版本，Compaction 未完成前旧版本还在。

SSD 底层再放大一次：擦除块 256 KB、写入粒度 4 KB——用户逻辑写 4 KB 可能触发 SSD 内部"读整块 → 修改 4 KB → 写到新块 → 擦除旧块"的 64× 硬件写放大。SSD 主控靠 wear leveling + garbage collection 分摊这层放大。

三、索引结构演进链

回到刚才七大范式各自选的索引结构。它们不是杂乱无章，而是沿着"用什么物理结构应对什么查询模式" 一路演进出来的。

3.1 B+ 树 vs LSM 树——最大的一次分叉

LSM 三层结构：

写入 ──▶ MemTable (跳表，可写)
          │  写满 (~64 MB)
          ▼
      Immutable MemTable (只读)
          │  Flush 到磁盘
          ▼
      L0 (与其它 L0 有 key 重叠，需要一起查)
          │  Compaction (Leveled / Size-Tiered)
          ▼
      L1 (每一层内 key 无重叠、大小固定倍数递增)
          │
      L2, L3, ..., Ln (越老越大，通常 10× 递增)

• Compaction 策略：Leveled（RocksDB / LevelDB 默认，每层内 key 无重叠，读放大低、写放大高）vs Size-Tiered（Cassandra 默认，同层多个 SSTable 可 key 重叠，写放大低、读放大高）。只需要知道两家哲学分歧，具体调参属于运维深水区。
• Bloom Filter：每个 SSTable 附带一个概率数据结构——"这个 key 肯定不在里面" 能秒判，"这个 key 可能在里面" 需要真正查。让 LSM 的读放大从"扫所有层"降到"平均 1.x 层"。

一句话辨析：读多写少走 B+ 树、写多读少走 LSM——这是 90% 场景下的第一直觉。

反直觉细节：MongoDB WiredTiger 引擎同时支持 B-tree 与 LSM 双引擎，可以在建集合时选（storageEngine: {wiredTiger: {configString: "type=lsm"}}）——同一家产品可以两种结构都用，不要以为"一家产品对应一个结构"。

3.2 哈希索引与跳表

• 哈希索引：O(1) 等值查找——但不支持范围、排序、最左前缀。Redis 内部用哈希（dict）存 String/Hash/Set 等 KV，靠渐进式 rehash（两张表并存、每次操作搬 1 个 bucket）在 GB 级数据规模下不阻塞主线程。
• 跳表（Skip List）：多层链表 + 概率上升，O(log N) 期望复杂度，实现比红黑树简单一半。Redis ZSet、LevelDB/RocksDB 的 MemTable、Google Chrome 的时间轴都用跳表。

Redis ZSet 为什么用跳表而不用红黑树：

1. 实现简单——跳表几十行代码，红黑树几百行。
2. 天然支持范围扫描——多层链表本来就是有序的，ZRANGE 直接沿最底层链表走。红黑树做范围要中序遍历，写起来麻烦。
3. 并发友好——跳表的读几乎无锁，写只需局部加锁；红黑树的旋转要锁多个节点。
4. 内存可控——跳表节点数量可预测，红黑树的染色重排在最坏情况下要触及 O(log N) 个节点。

3.3 倒排索引——全文检索的物理形态

倒排索引 = 词项字典（Term Dictionary） + 倒排列表（Posting List）：

Term Dictionary          Posting List
──────────────           ────────────────────────────
"苹果" ─────────▶  [doc7, doc42, doc99, doc203, ...]
"手机" ─────────▶  [doc3, doc7, doc42, doc999, ...]
"降价" ─────────▶  [doc42, doc111, ...]

关键优化：

• FST（Finite State Transducer） 压缩词项字典——把"苹果 / 苹果 15 / 苹果醋 / 苹果树"这些前缀相同的词项共享前缀存储，压缩比可达数十倍。Lucene 从 4.0 起用 FST 存词项字典。
• Skip List 加速跳跃——倒排列表本身是排序的 doc id 数组，用 Skip List 支持"查 doc42 是否在这个列表里"从 O(N) 降到 O(√N) 或 O(log N)。
• BM25 打分：TF-IDF 的改良版——加入了文档长度归一化、词频饱和函数，实测效果比 TF-IDF 好一档，是 Elasticsearch 默认打分公式。
• 与稠密向量的 hybrid search——现代搜索是"BM25 关键词打分 + 向量相似度打分 + Rerank"三阶段流水线，倒排负责精确关键词与召回稳定，向量负责语义泛化。

代表产品：Apache Lucene（底层库）、Elasticsearch、OpenSearch、Meilisearch（Rust）、Tantivy（Rust）、Meilisearch 与 Typesense（新一代产品）。

3.4 列式存储与向量化——OLAP 的物理形态

行式 vs 列式：

行式（OLTP）                          列式（OLAP）
─────────────────────────           ─────────────────────────
Row 0: [id=1, name=A, age=20]        id:   [1, 2, 3, 4, ...]
Row 1: [id=2, name=B, age=21]        name: [A, B, C, D, ...]
Row 2: [id=3, name=C, age=22]        age:  [20, 21, 22, 23, ...]

列式为什么在 OLAP 快 10-100×：

• 只读需要的列：SELECT AVG(age) FROM users 只需扫 age 一列，跳过 name 和其它字段。IO 量级差异直接体现在查询延迟。
• 同列同类型天然利于压缩：age 全是小整数，用 varint / delta / dictionary encoding 能压 5-10×。行式里 int 挨着 string 挨着 timestamp，压缩比差得多。
• SIMD 向量化执行：CPU 一条指令同时算 4/8/16 个 int，前提是这些 int 连续排布在内存里——列式天然满足。ClickHouse 的核心竞争力就是"每个算子都用 SIMD 写一遍"。

一句话辨析：点查行式赢、扫描聚合列式赢。

代表产品：Parquet / ORC（列式文件格式，与计算引擎解耦，Spark / Presto / Trino 通用）、ClickHouse / DuckDB / StarRocks / Doris（列式数据库）。

3.5 向量索引 HNSW / IVF / PQ

三大家索引，正好对应"图 / 分区 / 压缩"三种思路。

HNSW（Hierarchical Navigable Small World）——图索引：

Layer 3:       ● ────────────────────── ●          （稀疏层，跳得远）
                 ╲                    ╱
Layer 2:     ● ── ● ────────── ● ── ●              （中间层）
              ╲   ╲            ╱   ╱
Layer 1:   ● ── ● ── ● ── ● ── ● ── ● ── ●          （中密层）
             ╲   ╲   ╲   ╲   ╱   ╱   ╱
Layer 0: ●─●─●─●─●─●─●─●─●─●─●─●─●─●─●─●─●         （全量最密层）

• 每个向量作为图节点，插入时按概率决定"最高在哪层"（越高越稀疏）。查询从顶层开始贪心走最近邻，逐层往下细化。
• 三大调参：M（每个节点的最大邻居数，默认 16-32，越大精度越高内存越大）、efConstruction（建图时候选池大小，越大建得慢但质量高）、efSearch（查询时候选池大小，直接控制"召回率 vs 延迟"）。
• 优点：召回率高、查询快（对数级）。缺点：内存占用大（每个向量存 M 个邻居 ID）、增量插入代价大（要重建局部图）。

IVF（Inverted File Index）——分区索引：

• 用 k-means 把向量空间粗聚类成 nlist 个中心（比如 4096 个），每个向量归属最近的中心。
• 查询时先算 query 到所有中心的距离，只扫最近的 nprobe 个中心里的向量（nprobe 越大召回越高、速度越慢）。
• 优点：内存占用小、建索引快、支持增量。缺点：召回率天花板低于 HNSW（除非 nprobe 很大）。

PQ（Product Quantization）——压缩量化：

• 把 D 维向量切成 M 段（比如 128 维切成 8 段每段 16 维），每段独立做 k-means 量化（比如各 256 个码字，用 1 个 byte 表示）。
• 原始 128 维 × 4 byte = 512 byte 的向量，压成 8 byte——60× 压缩。查询时用码本查表近似算距离。
• 优点：内存暴降。缺点：量化误差导致召回率下降。

组合：生产系统里最常见的是 IVF-PQ（先粗聚类分区、再量化压缩）或 HNSW-PQ（图索引 + 量化）——召回率 / 延迟 / 内存三角权衡的具体切点。

空间索引不是排序索引——B+ 树按 key 排序，倒排按词项分组，向量索引按空间邻近性组织。这个定位差异决定了它无法用来做"给我 age 在 18-30 之间的向量"，得叠一个元数据过滤 filter 才行。

四、一致性、复制与分片

4.1 一致性模型对照

ACID vs BASE 是同一光谱的两端，不是二选一：

• ACID：Atomicity / Consistency / Isolation / Durability——关系型数据库的黄金标准。
• BASE：Basically Available / Soft state / Eventual consistency——NoSQL 阵营为水平扩展做的让步。

CAP 常见误读：

• 严格表述：当且仅当发生网络分区（P）时，必须在"可用性（A）"与"一致性（C）"之间选一个。
• 常见误读："CA 系统"——不存在，因为 P 是网络必然性，不是可选项。
• PACELC 补齐：Partition 时选 A 或 C（PAC），Else 无分区时也要在 Latency 与 Consistency 之间选（ELC）。TiDB 是 PC + EC（一致性优先），DynamoDB 默认是 PA + EL（可用性 + 低延迟优先）。

四层可读性（强到弱）：

隔离级别与异常映射（关系型内部）：

• 读未提交（RU）：脏读可能。
• 读已提交（RC）：脏读禁止，不可重复读可能。
• 可重复读（RR）：不可重复读禁止，幻读可能（InnoDB 靠间隔锁额外堵）。
• 可串行化（SER）：全部禁止，性能代价高。
• 快照隔离（SI）：读走快照，写偏斜（write skew） 可能。

跨库/跨节点事务视角：见 分布式事务。

4.2 复制模型

Leader-Follower（Primary-Replica） 三档复制：

Multi-Leader：跨机房双写、离线协作。冲突处理靠 CRDT（Conflict-free Replicated Data Types）或"最后写者胜（LWW，Last-Write-Wins）"。

Leaderless（Dynamo 风格）：无固定 leader，客户端并发写 N 个副本，W + R > N 保证读写重叠——写 W 个副本成功即返回，读 R 个副本取最新版本。Cassandra、DynamoDB、Riak 是代表。

强一致复制协议：Raft（etcd、Consul、TiKV、CockroachDB、Kafka Raft）与 Paxos（Google Chubby / Spanner）—— 靠 leader 选举 + 日志复制多数派达成"看似全局一致"的效果。

4.3 分片方式

主流落地对照：

• Redis Cluster：预分 16384 slot，slot 到 node 映射靠 gossip。加节点时按 slot 迁移。
• Cassandra：一致性哈希 token ring + 虚拟节点（vnode，每台机器 256 个 token），迁移量最小化。
• MongoDB：range chunk（默认）或 hash chunk，balancer 后台迁移。
• TiDB：Region 是范围分片单位，PD 调度中心动态调整。

为什么这么做

回过头看，前面每一层选择都不是任意的，而是"底层制约 → 结构选型"的因果推理。

• 页 + 缓冲池 + WAL 为什么是通用抽象：因为磁盘 IO（无论 HDD 还是 SSD）都是"以块为单位、随机远慢于顺序"。页把"逻辑上一行"变成"物理上一批"，缓冲池把"最热的一批"留在内存，WAL把"随机的批量写"变成"顺序的单文件追加"——三层组合直接对应磁盘的三个物理约束。谁想跳过任何一层都会付代价（Redis 全跳过磁盘，代价是"内存要够 + 持久化要另做"）。

• B+ 树为什么是关系型的默认选择：因为关系型工作负载是"读写比高、每次读涉及多列（回表 / JOIN）、需要范围扫描（ORDER BY）"——B+ 树的叶子有序链表 + 扇出大树高低同时满足这三个需求，读放大低到只有树高。LSM 在这种负载下会输——写放大太大且读要跨多层。

• LSM 为什么在写密集场景赢：因为工作负载是"每秒百万级写入、单点读频率低、按主键顺序批量查询"——追加合并把随机写变纯顺序写，Bloom Filter 补掉读放大，Compaction 后台异步分摊代价。Cassandra / RocksDB / TiKV 都是这种负载画像。

• 倒排索引为什么是全文检索唯一解：全文搜索的查询模式是"给一堆词，找所有包含这些词的文档"——倒排把这个操作从"扫每个文档看它是否含这些词"（O(N × 文档长度)）变成"扫这些词各自的文档列表求交集"（O(词数 × 平均列表长度)）。这是换维度级的加速。

• 列式为什么在 OLAP 赢：OLAP 查询是"扫超大规模数据、只算聚合、通常只涉及少数列"——列式同时满足"只读需要的列 + 同列压缩率极高 + SIMD 向量化"。三条加速叠乘。

• 向量索引为什么必须近似：维度诅咒是数学上的必然——在 D 维空间里，任意两点的距离比会趋近 1（都"看起来差不多远"），所有基于树的空间划分在 D > 30 就退化到全表扫描。既然精确不可能，就换 ANN，牺牲个位数百分比召回率换 100-1000× 加速。

• 一致性协议为什么绕不开 Raft/Paxos：分布式系统里，"确定所有节点看到相同事件顺序" 是不可能仅靠单向消息实现的——必须有选举（leader）+ 多数派（quorum）+ 日志复制三件套。Raft 是 Paxos 的可教学重写，两者本质等价。这是 FLP 不可能定理在工程上的可用逼近。

为什么别的选择不行

同样的场景，选错范式或索引会付什么代价？

• 为什么不用 KV 存交易账务：KV 缺少跨行原子性（分布式锁能勉强补，但性能与复杂度不匹配）、缺少外键约束（转账要求"扣了 A 加到 B 是一个原子操作"，KV 里做要么 Lua 单机版、要么 2PC 跨槽——不如直接 InnoDB）、缺少范围一致查询（对账要拉一段时间的所有流水，KV 只能靠二级索引另做）。所以 Redis 常做交易账务的缓存层，而不是主存储。

• 为什么不用 MySQL 存高维向量：B+ 树按 key 排序，key 是标量或元组——高维稠密向量没有全序（"是 (0.1, 0.5, 0.3, ...) 大还是 (0.2, 0.4, 0.3, ...) 大"没有意义）。硬要往 MySQL 塞就只能整个向量列扫全表算相似度，等于放弃索引。pgvector 是补救方案——它给 PostgreSQL 加了 IVFFlat / HNSW 扩展，让 PG 具备向量能力。不改内核就想用关系型库存向量，做不成。

• 为什么不用 LSM 做金融流水查询：金融流水查询画像是"读多写少 + 精确点查 + 强一致 + 跨表 JOIN"——LSM 读放大代价直接命中痛点（每次查一条流水要扫多层 SSTable），Compaction 期间延迟抖动也不能接受。这是 B+ 树的主场。

• 为什么不用图库存 100M 用户 × 10 订单：这本质上是"用户 → 订单"一对多关系，SQL 一个 JOIN 就搞定——用图库反而要维护"节点 + 边 + 属性"三种存储、加两跳遍历的模型转换成本。只在关系跳数 > 3 或需要动态模式匹配时，图库才真正赢。反面：知识图谱做多跳推理是图库的主场，SQL 做 5-hop JOIN 会写成噩梦。

• 为什么不用文档型做多表 JOIN：MongoDB 的 $lookup 是"应用层 JOIN 的语法糖"——性能远差于关系型的 hash join / nested loop join，且不支持复杂优化器。多表 JOIN 是关系型的看家本领，别硬拿文档型顶。

• 为什么不用时序库存业务事实表：时序库的 schema 假设"时间戳 + 标签 + 数值"——业务事实表里的字符串字段、大 JSON、复杂 WHERE 条件都不友好。反过来，业务库拿来存监控指标也不好——每秒百万级写入直接把 MySQL 打挂。范式是双向的护城河。

沉淀结论

四张辨析对照表

表 1：七大范式速查

表 2：B+ 树 vs LSM 树

表 3：KV vs 文档 vs 关系型

表 4：向量索引三家 HNSW vs IVF vs PQ

面试快速反应表

记忆口诀

• 磁盘指针 = 页号 + 页内偏移：所有引擎共有的物理定位方式，B+ 树非叶子节点存的就是它。
• 页 → 缓冲池 → WAL：三层通用抽象，对应磁盘的"块 IO / 冷热分层 / 顺序写"三个物理约束。
• 读多 B+ 树、写多 LSM 树：一句话选索引，覆盖 90% 场景。
• 范式先看数据形状再看查询模式：不是选产品，是选"数据形状 × 查询模式"组合。
• 向量索引是空间索引不是排序索引：HNSW/IVF/PQ 组织的是"空间邻近性"，不能拿来做范围查询。
• CAP 是分区时选 A/C，PACELC 补充"平时也在 L/C 之间选"。
• 一致性哈希把 O(N) 迁移降到 O(N/M)：这是它相对普通哈希唯一的立身之本。
• WAL 是崩溃恢复根基，随机写变顺序写是副产品：先记住主目的。
• 文档型不是无 schema，是把 schema 从写侧挪到读侧：灵活的代价是应用层复杂度。
• 图库只在关系跳数 > 3 时赢：JOIN 能搞定的就别用图。

进一步阅读

• 《Designing Data-Intensive Applications》Martin Kleppmann——Ch 3（存储与检索）、Ch 5（复制）、Ch 6（分片）、Ch 7（事务）、Ch 9（一致性）几乎覆盖本篇所有主题。
• The Log-Structured Merge-Tree (LSM-Tree)——Patrick O'Neil 1996 年原始论文。
• Gorilla: A Fast, Scalable, In-Memory Time Series Database——Facebook 时序压缩经典论文，10× 压缩比的来源。
• Efficient and Robust Approximate Nearest Neighbor Search using HNSW——HNSW 原始论文。
• Amazon Dynamo: A Highly Available Key-value Store——Leaderless 复制与最终一致的开山之作。
• Bigtable: A Distributed Storage System for Structured Data——Google 宽列数据库原始论文。