📚 课程目录第3章数据结构与算法在数据库内核中的应用

第3章数据结构与算法在数据库内核中的应用

本章聚焦数据库内核中最核心的四种数据结构和算法：B+树、LSM树、哈希索引、排序算法。面试中高频考察点包括：结构选择的权衡、写放大与读放大、合并策略、适用场景对比。以下通过问答模型+项目模板帮助你建立结构化表达。

上图展示了面试官对“B+树”的典型追问路径，每个节点对应一个可能的深入问题。

🎯 面试问题：请解释B+树在数据库索引中的核心优势，为什么不用B树？

面试官考察点： 是否理解B+树的磁盘友好性、范围查询能力、节点结构差异。

回答框架：

简短示例回答： B+树内节点只存键，扇出大，树高通常3~4层，减少磁盘IO。叶子节点有序链表支持范围查询一次定位后顺序扫描。B树内节点存数据，扇出小，树高增加；范围查询需多次回溯，随机IO更多。因此数据库索引默认使用B+树。

可能追问： B+树的插入和删除如何维护平衡？为什么不用红黑树？

⚠️ 避坑提醒： 不要只说“B+树更快”，要量化说明扇出、树高差异。避免混淆B树和B+树定义。

🎯 面试问题：LSM树如何优化写操作？常见的合并策略有哪些？

面试官考察点： 写放大/读放大理解、compaction策略、数据分层思想。

回答框架：

简短示例回答： LSM树将随机写转化为顺序写：数据先入内存表，后台追加写入SSTable，避免原地更新。合并策略中，Size-Tiered适合写多读少场景，Leveled（如LevelDB）能有效降低读放大，但写放大更大。选择策略需权衡读写性能。

可能追问： LSM树如何解决读放大？Bloom filter在这里的作用？

⚠️ 避坑提醒： 不要只讲优点，要主动点出读放大和写放大矛盾。Merge过程是高频考点，需清晰描述层次结构。

🎯 面试问题：哈希索引与B+树索引的适用场景有什么区别？数据库内部排序算法通常如何实现？

面试官考察点： 是否理解哈希索引仅支持等值查询、不支持范围；排序算法在外部排序中的应用。

回答框架：

简短示例回答： 哈希索引只适用于等值查询如主键点查，无法做范围扫描；B+树索引适用范围广。数据库排序如ORDER BY，通常使用外部归并排序：将数据分块排序到磁盘，再多路归并，控制内存和磁盘IO比例。MySQL Sort Buffer用于快速排序。

可能追问： 哈希冲突解决方法？归并排序的通用写法与优化（如替换选择法）？

⚠️ 避坑提醒： 不要忽略哈希索引的局限性；排序算法要结合磁盘IO和内存限制讲，不能只讲快排。

📁 项目名称：自研分布式数据库存储引擎升级（混合索引+排序优化）

业务背景	原有系统基于B+树纯引擎，写吞吐不足；需支持高并发写入和部分范围查询场景。重新设计混合存储引擎。
规模指标	日均写入2亿行，存储节点10个，单节点SSD 2TB，QPS峰值8万，延迟P99 < 10ms。
技术栈	C++17、RocksDB（LSM树）、自研B+树缓存层、多路归并外部排序、Bloom Filter优化读。
核心难点	写放大与读放大的平衡；LSM树与B+树分片策略冲突；大规模数据排序时内存不足导致IO抖动。

🎤 面试高频追问：

💡 可迁移回答话术：

“在本项目中，我们采用冷热分离原则——热数据先写LSM树保证写入吞吐，通过后台合并将稳定数据迁移到B+树索引以优化范围查询。排序方面使用外部归并排序，通过调整run大小控制内存占用，并引入Bloom Filter减少LSM树读放大。这一架构在保持高写入性能的同时，将范围查询延迟降低60%。”

数据结构/算法	核心特点	典型数据库应用	面试高频点
B+树	扇出大、树高低、叶子链表	InnoDB主键索引	范围查询、与B树对比
LSM树	顺序写、分层合并、写放大	RocksDB、LevelDB	Compaction策略、Bloom Filter
哈希索引	O(1)等值查找、不支持范围	Memory引擎、自适应哈希	与B+树对比场景
外部排序	多路归并、run生成、磁盘IO	ORDER BY、GROUP BY排序	替换选择法、归并路数

💡 复习提示：面试官常将多个数据结构放在同一问题中对比，建议日常练习时使用“画图+表格”方式快速梳理差异。本章四个知识点建议形成一张A4纸对比图，考前反复默写。

第3章 数据结构与算法在数据库内核中的应用