AI Infra 305
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+ 数据只在叶、叶子链;范围与顺序更优。

记忆要点

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

返回模块 | 返回总览