查找值在某区间内的所有键值对用什么数据结构
哪些公司问过
答案要点
- 一次性查询直接遍历过滤,O(n)
- 多次查询需按值建有序索引:平衡树或跳表
- 定位下界后顺序遍历,O(log n + k)
- 值可能重复,索引的值应存 key 列表或用 multimap
- 静态数据用排序数组 + 二分;磁盘场景用 B+ 树
易错点
- 用哈希表按值查询范围,哈希表无序无法高效范围查找
- 忽略值重复,导致同值的 key 被覆盖
- 只建值索引却忘了更新 key 时同步维护
面试官常见追问
- 原来的 key 到 value 的查询还要保留,怎么同时支持?
- 为什么数据库索引用 B+ 树而不是红黑树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。