IT 面试题库

为什么数据库索引大多使用 B+ 树,而不是二叉搜索树或哈希表?

中级简答题后端开发工程师Java后端工程师索引B+树数据库

题目

从磁盘 IO、范围查询和排序等角度说明 B+ 树作为索引结构的优势。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 84 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

关系型数据库索引选择 B+ 树,核心原因是它契合磁盘的块式访问特性并天然支持范围查询:

  1. 矮胖的树高,减少磁盘 IO:B+ 树一个节点存很多关键字(通常一页 16KB 可放数百个),三层即可索引上千万行,而二叉搜索树高度 log2(n) 太大、随机 IO 多。
  2. 所有数据在叶子节点且用链表串联:范围查询(BETWEEN、ORDER BY)只需顺链表扫描,无需中序遍历回退,效率极高;哈希表不支持范围查询。
  3. 非叶子节点只存键,扇出更大:同样空间能放更多分支,进一步降低高度。
  4. 查询稳定:任何键值都要走到叶子层,IO 次数一致;哈希表虽 O(1) 但无法排序/范围,且存在哈希冲突与扩容rehash代价。

因此:等值+范围查询兼顾选 B+ 树;纯等值、对顺序无要求且追求极致命中速度时可选用哈希索引。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题