ai-infra-interview-305

第 286 题：B+ tree在数据库中的应用？为什么适合磁盘？

题目

B+ tree在数据库中的应用？为什么适合磁盘？

---

完整讲解

一、B+ tree 在数据库中的应用

B+ tree 是数据库索引的主流结构：多路平衡、所有 key 在叶子层有序且形成有序链表、非叶节点只存 key 与子指针（不存数据），叶子层存 key 与记录指针或数据。支持范围查询、顺序扫描、高扇出（单节点可存大量 key），适合磁盘块为单位的读写。

二、为什么适合磁盘

磁盘按块读写（如 4KB），随机 IO 贵。B+ tree 节点大小设计成块大小，一次 IO 读入一节点；高扇出（阶大）使树矮，查找次数 = 树高，通常 3～4 层即可覆盖海量数据，即 3～4 次磁盘访问。叶子链表使范围查询与全表顺序扫描只需沿叶子链，顺序 IO 友好。平衡保证任意 key 的查找路径等长，性能稳定。

三、与 B tree 区别

B+ 非叶节点不存数据、只做索引；叶子层含全部 key 且链表串联。B tree 的 key 与数据可在非叶节点出现。B+ 范围查询与顺序扫描更优，数据库多用 B+。

---

面试要点

• B+ tree：多路平衡、key 全在叶子且叶子成有序链、非叶仅索引；数据库索引常用。
• 适合磁盘：节点=块大小、高扇出树矮、查找=树高次 IO；叶子链支持范围与顺序扫描。
• 高扇出减少树高；平衡保证路径等长；顺序 IO 友好。
• 与 B tree：B+ 数据只在叶、叶子链；范围与顺序更优。

---

记忆要点

1. B+ = 多路平衡、叶存全部 key 且成链、非叶仅索引。
2. 节点=块、高扇出、树矮 → 少次 IO；叶子链 → 范围/顺序友好。
3. 数据库索引首选；3～4 层覆盖大量数据。

返回模块

返回总览