参考答案
内容深度:适中 · 无代码示例 · 来源:网络整理 · 未复核 · 71 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
从"磁盘 IO 次数"这个核心约束出发逐个排除:
- 哈希表:等值查询 O(1) 很快,但不支持范围查询与排序(数据无序),而范围查询是数据库最高频需求之一。
- 二叉搜索树/红黑树:树高 = log₂N,100 万数据约 20 层,每层一次磁盘 IO,且数据量大时树会越来越高;二叉结构每节点只存 1 个键,浪费磁盘页空间。
- B 树:多叉已降低树高,但每个节点都存数据,单页(16KB)能放的键变少,树高变高;且范围查询需要中序回溯,IO 不友好。
- B+ 树:①非叶子节点只存键,一个 16KB 页可放上千个键,3~4 层即可承载千万级数据(查询仅 3~4 次 IO,顶层还常驻内存);②数据全在叶子节点且叶子间双向链表相连,范围查询、排序沿链表顺序扫描即可;③查询性能稳定(每次都到叶子层)。
这就是为什么 MySQL 的千万级表 B+ 树索引依然稳定高效。