📚 课程目录第4章存储引擎与索引结构

4. 存储引擎与索引结构

考核权重：★★★★★（大厂内核岗高频核心章节）
核心能力：结构理解 + 读写放大分析 + 场景选型

本章导学：面试官常借“索引结构”考察候选人对存储引擎本质的理解。B+树解决点查和范围扫描，LSM-Tree优化写入，倒排索引服务文本搜索。必须掌握三大结构的数据组织方式、读写放大因子、磁盘IO模型、并发控制策略。本章帮你建立回答框架，避开“只会背书不懂权衡”的坑。

🎯 面试问答 1：B+树索引结构

面试问题：请详细描述B+树的组织结构，并说明它在数据库存储引擎中有哪些核心优势？

    考察点：① 对平衡多路搜索树底层实现的理解（节点、扇出、叶子链表）；② 磁盘IO优化原理；③ 范围查询效率的论证；④ 写放大与并发控制意识。
  

回答框架：
1️⃣ 结构定义 → 2️⃣ 关键特性（有序性/高扇出/叶子链表） → 3️⃣ 磁盘IO模型（一次节点 = 一页） → 4️⃣ 优势总结（点查/范围扫描稳定） → 5️⃣ 局限性（写放大/热点问题）。

简短示例回答：
“B+树是一种平衡多路搜索树，内部节点仅存键，叶子节点存键值对并形成双向链表。高扇出（约3-4层）保证每次查询只需3-4次磁盘IO。支持高效范围扫描，直接沿叶子链表遍历，这是LSM-Tree难以匹敌的。但写操作需修改B+树结构，产生写放大；InnoDB通过Change Buffer缓解。”

⚠️ 可能追问	① B+树节点大小为什么通常是4KB/16KB？② 如何防止B+树退化成链表？③ MySQL InnoDB 的 Adaptive Hash Index 如何加速？
💡 避坑提醒	不要只说“B树”。B+树内部节点不存数据，叶子节点有链表；面试官期望你对比B树和B+树。另外注意区分索引组织表（IOT）与堆表。

🎯 面试问答 2：LSM-Tree 与 B+树对比

面试问题：对比LSM-Tree和B+树，说明各自适用场景，并分析读写放大问题。

    考察点：① LSM-Tree分层结构（MemTable→Immutable→SSTable）理解；② Compaction策略（Leveled vs Size-tiered）；③ 三种放大因子量化能力；④ 场景权衡思维。
  

回答框架：
1️⃣ 核心差异（磁盘随机写 vs 顺序写） → 2️⃣ LSM-Tree写放大/读放大/空间放大解释 → 3️⃣ B+树写放大原因（页分裂/重平衡） → 4️⃣ 选型依据：写密集型选LSM-Tree，读密集型选B+树 → 5️⃣ 工程取舍（例：LevelDB vs InnoDB）。

简短示例回答：
“LSM-Tree将随机写转化为顺序写，写吞吐可提升10x以上，但Compaction导致读放大（需查多层SSTable）和写放大（数据重复合并）。B+树写放大较小（约2-3倍），但随机写性能差。典型场景：RocksDB用于日志写入，InnoDB用于OLTP点查。”

⚠️ 可能追问	① 设计一个LSM-Tree的Compaction策略减少写放大？② 什么是“读放大系数”，怎么算？③ 如何实现LSM-Tree的并发控制？
💡 避坑提醒	别把写放大和读放大搞混。写放大是指实际写入磁盘的数据量/用户数据量；读放大指一次查询需要检查的SSTable数量。回答时最好画出层级图，展示不同level的SSTable。

🎯 面试问答 3：倒排索引原理与存储引擎协同

面试问题：倒排索引如何实现全文检索？在数据库内核中如何与底层存储引擎协同工作？

    考察点：① 倒排索引正向/反向映射概念；② 词项词典与倒排列表存储结构；③ 分词、归并、TF-IDF评分；④ 增量更新、段合并（类似LSM）。
  

回答框架：
1️⃣ 原理：文档→词项→倒排列表（文档ID+位置） → 2️⃣ 数据结构：词典（跳表/哈希/FST） + 倒排列表（压缩位图） → 3️⃣ 协同方式：倒排元数据存于B+树主键中，底层行存储由B+树/LSM-Tree承载 → 4️⃣ 全文查询流程：分词→查词典→归并倒排列表→回表查原始行。

简短示例回答：
“倒排索引以词项为键，文档ID列表为值。例如‘数据库’→[doc1, doc3]。在InnoDB中，倒排索引可存储在辅助B+树中，词项作为索引键，倒排列表作为行数据。全文查询先查倒排索引得文档ID集合，再通过主键回表获取完整行。增量更新类似LSM，先用内存段，合并时合并倒排列表。”

⚠️ 可能追问	① 倒排列表用差量编码压缩（Varint/Roaring Bitmaps）？② 多词查询的布尔操作如何优化？③ 中文分词怎么处理？词典太大如何内存高效存储？
💡 避坑提醒	不要混淆全文搜索引擎和数据库倒排索引。Elasticsearch是独立索引层，而数据库通常将倒排索引作为特殊索引类型（如MySQL FULLTEXT），底层仍依赖存储引擎。回答时要强调“协同”而不是“替代”。

🏗 项目案例：时序数据库存储引擎（LSM-Tree + 倒排索引）

项目名称	TSTimeDB – 自研时序数据库存储引擎
业务背景	物联网平台每秒写入200万时间点，要求写入延迟 <1ms，同时支持按标签（tag）的高通量检索。
规模指标	单集群存40亿时间序列，每天新增15TB数据，读P99 <10ms，写吞吐50MB/s/节点。
技术栈	C++17、RocksDB（LSM-Tree）、自定义倒排索引（FST词典 + Roaring Bitmap）、Protobuf序列化。
核心难点	高基数标签下倒排索引膨胀问题（数百万标签值→倒排列表内存放不下） LSM-Tree Compaction过程中标签索引一致性维护时序数据天然有序性如何利用来减少写放大
面试高频追问	“你如何解决倒排索引的内存开销？” → 使用FST压缩词典 + Roaring Bitmap按需加载。 “Compaction时倒排索引怎么保持在线可用？” → 采用段级快照隔离，旧段读旧版本，合并后原子替换。 “LSM-Tree层数怎么设置？读写放大系数多少？” → 根据写量调level，目标读放大3-5，写放大控制在10以内。 “为什么不用B+树做时序？” → 时序写入量大且随机写多，LSM顺序写更优；时序范围查询可通过时间分片优化。
可迁移回答话术	“面对高写入+标签检索场景，我选择LSM-Tree作为主存储，配合自定义倒排索引支持灵活查询。核心权衡是：写入吞吐优先，通过合理设置Compaction策略（leveled+size-tired混合）控制读放大；倒排索引采用内存+磁盘两级缓存，FST压缩词典后内存占用降低80%。最终线上P99读延迟稳定在8ms以内。”

📌 本章复习要点
• B+树：难点在页分裂与并发控制，面试中常与跳表对比，答出“磁盘IO预读”加分。
• LSM-Tree：必须能手绘写放大 = (level-1)×T公式，引例LevelDB默写放大10倍。
• 倒排索引：讲清词项→文档列表的映射，并关联存储引擎的回表机制。
• 项目回答遵循STAR - 量化指标 - 权衡三段式，避免空谈技术。