第2章 高频面试问题与回答框架

• 对 B+ 树数据结构与磁盘 IO 关系的理解深度
• 是否了解实际存储引擎（InnoDB）的页结构、节点分裂/合并机制
• 能否将「范围查询」与「叶子节点链表」的物理设计关联起来

1. 理解问题：B+ 树本质是多路平衡查找树，专为磁盘 IO 优化
2. 定位根因：范围查询效率高因为叶子节点形成有序双向链表
3. 方案推演：页内二分 → 内部节点引导路径 → 叶子节点顺序扫描
4. 效果量化：三层 B+ 树可支撑千万级数据，范围查询仅需一次随机 IO + 顺序 IO
5. 总结升华：B+ 树设计体现了「以页为单位的 IO 局部性」思想，是现代关系数据库的基石

B+ 树所有数据存储在叶子节点，内部节点仅存键值用于路由。叶子节点通过双向链表连接，支持顺序遍历。范围查询时，从根节点二分定位起始键，沿内部节点下探到叶子，再从起始位置沿链表向右扫描至结束键，全程将随机 IO 转化为顺序 IO，显著提升吞吐。

• 阿里方向：OceanBase 中 B+ 树与 LSM-Tree 如何融合？混合存储场景下索引分裂策略有何不同？
• 腾讯方向：分布式数据库 TDSQL 中，B+ 树索引如何分片？全局索引与局部索引如何协同？
• 字节方向：veDB 在高并发写入下 B+ 树页面分裂的瓶颈是什么？如何通过无锁优化提升性能？

• 不要只讲数据结构理论，要结合 InnoDB 实际实现（页大小 16KB、Adaptive Hash Index、Change Buffer）。
• 阿里面试官特别看重「IO 局部性」和「页面缓存」的联动分析，避免空谈复杂度。
• 区分「聚簇索引」和「二级索引」的叶子节点内容，不要混淆。

• 对 MVCC 核心组件（undo log、read view、事务 ID）的掌握程度
• 能否清晰区分「快照读」和「当前读」的机制差异
• 是否理解 Gap Lock 与 Next-Key Lock 在幻读防御中的具体作用

1. 理解问题：MVCC 实现读写不冲突，可重复读需同时解决幻读
2. 定位根因：幻读因其他事务插入新行导致，需要锁机制补充 MVCC
3. 方案推演：快照读依赖 MVCC 版本链 + read view 可见性判断；当前读依赖 Next-Key Lock
4. 效果量化：MVCC 使读写并发度提升 3-5 倍，Next-Key Lock 保证事务隔离不出现幻行
5. 总结升华：MVCC + 行锁 + Gap Lock 的组合是「乐观并发 + 悲观兜底」的经典设计模式

InnoDB 通过 undo log 构建历史版本链，每行记录隐藏字段 DB_TRX_ID 和 DB_ROLL_PTR。事务启动时生成 read view 判断可见性。可重复读下快照读无需加锁；当前读（SELECT FOR UPDATE）使用 Next-Key Lock = 行锁 + Gap Lock，锁定范围和间隙，防止幻行插入。

• 华为方向：GaussDB 中 MVCC 与分布式一致性协议如何协同？长事务导致 undo 膨胀如何处理？
• PingCAP 方向：TiDB 的 MVCC 基于 PD 分配全局时间戳，与 InnoDB 的本地事务 ID 机制有何本质区别？
• 字节方向：veDB 存储计算分离架构下，MVCC 版本链是放在计算节点还是存储节点？为什么？

• 不要混淆「快照读」和「当前读」，这是面试中扣分最多的概念错误。
• 腾讯面试官特别关注分布式 MVCC 中的全局事务可见性，建议提前了解 TDSQL 的全局时间戳方案。
• 回答 Gap Lock 时需说明只在「可重复读」级别生效，读已提交下只锁行。

• 对优化器整体架构（逻辑优化 → 物理优化 → 代价估算）的理解
• 是否掌握 Join 顺序选择的经典算法（动态规划、贪心、遗传算法）
• 能否结合实际统计信息（行数、NDV、数据分布）设计启发式规则

1. 理解问题：Join 顺序直接影响中间结果大小和执行效率
2. 定位根因：不同 Join 顺序产生不同代价，核心是减少中间行数
3. 方案推演：启发式规则 → 小表驱动大表 + 过滤条件下推 + 选择率估算
4. 效果量化：贪心算法可将搜索空间从 O(n!) 降至 O(n²)，覆盖率超 95% 最优计划
5. 总结升华：启发式 + 动态规划混合策略是工业级优化器的常见选型

优化器先做逻辑优化（谓词下推、投影剪裁），再进入物理优化。Join 顺序选择上，我倾向贪心 + 动态规划混合：先用贪心选出 Top-K 候选顺序，再对候选集做动态规划精搜。核心启发式是「优先 Join 选择率最高的表对」，同时用 histgram 估算过滤后行数，避免全局搜索爆炸。

• 阿里方向：OceanBase 中 Join 下推在分布式场景下如何与 Shuffle 策略配合？
• 字节方向：veDB 微服务数据分片后，跨节点 Join 的代价模型与传统单机有何不同？
• 腾讯方向：TDSQL 全局查询计划中，Join 顺序选择如何考虑网络传输代价？

• 不要只背优化器流程，要讲出你实际设计过的启发式规则细节（如选择率如何计算）。
• 阿里/腾讯面试官特别看重分布式场景下的 Join 优化，建议准备跨节点 Join 的代价模型案例。
• 区分「逻辑优化」和「物理优化」的概念，不要混为一谈。