21-算法与数据结构
第 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+ 数据只在叶、叶子链;范围与顺序更优。
记忆要点
- B+ = 多路平衡、叶存全部 key 且成链、非叶仅索引。
- 节点=块、高扇出、树矮 → 少次 IO;叶子链 → 范围/顺序友好。
- 数据库索引首选;3~4 层覆盖大量数据。