核心思路：先分析查询模式、数据规模、更新频率，再匹配时间复杂度，同时权衡空间开销。查询常见类型：单点查询、范围查询、模糊查询、条件过滤、排序后查询、聚合查询。
时间复杂度记号说明：\(O(1)\)常数、\(O(logn)\)对数、\(O(n)\)线性、\(O(nlogn)\)线性对数
一、先梳理业务特征（选型前置判断）
选型前先回答 4 个问题，直接决定数据结构：
查询类型：查单个 key？区间范围？前缀模糊？多维条件？是否需要排序输出？
读写比例：读多写少 / 读写均衡 / 写多读少。很多结构查询快，但插入删除代价很高。
数据量级：几十条内存；十万级内存；百万 / 亿级需要磁盘存储。
是否允许重复、有序、是否需要去重。
二、常用内存数据结构查询能力对比
1. 数组 / List（顺序表）
查询：下标随机访问 O (1)；按值遍历查找 O (n)
适合：已知下标直接访问；遍历全量数据。
不适合：按值搜索、频繁中间插入删除。
如果数组有序，可以使用二分查找，查询降到 \(O(logn)\)，但插入元素需要移动数组，写代价高。
2. 哈希表（HashMap / Dict）
查询：key 精确查找平均 \(O(1)\)
优点：单点 key 查询极快；缺点：不支持范围查询、不保证有序，哈希冲突会退化到 O (n)
适用：精确 key 查询，缓存场景。
局限：无法直接做
> < >= <=范围查询；内存开销较大。
3. 平衡二叉搜索树（TreeMap，红黑树）
查询：单点、范围查询 \(O(logn)\)，天然有序。
可以求大于、小于、区间遍历。
写操作也是 \(O(logn)\)；相比哈希表，单点查询略慢，但支持有序与范围。
Java TreeMap、C++ std::map 底层红黑树。
4. 跳表 SkipList
查询、插入、删除 \(O(logn)\)，有序，范围遍历友好；实现比红黑树简单。
Redis 有序集合 zset 底层就是跳表。适合内存有序数据集，高频范围查询。
5. 堆（优先队列）
查询：只能快速获取最大 / 最小值 \(O(1)\)；不支持任意 key 查询。
适合：TopN 场景，不适合普通检索。
6. 前缀树 Trie
查询：前缀匹配、字符串模糊前缀检索 \(O(len(key))\)
适合：单词检索、提示补全；不适合通用数值查询。
7. 布隆过滤器 BloomFilter
查询：判断元素一定不存在 / 可能存在；O (1)，有误判，不能删除。
适合：大数据量判不存在，减少回源查询，不能拿来获取真实数据。
三、磁盘场景（数据库、存储系统）对应数据结构
内存结构不能直接搬去磁盘，磁盘 IO 昂贵，要减少 IO 次数：
B + 树（数据库索引）
\(O(logn)\)，范围查询极强，数据全部在叶子节点，适合磁盘。MySQL InnoDB 主键索引。
适合：等值查询 + 大量范围查询，最通用数据库索引。
LSM‑Tree（LevelDB、RocksDB）
牺牲部分读性能换取极高写入性能；写多读少、海量数据。
适合：时序数据、日志存储；读会有合并开销。
哈希索引：等值查询快，不支持范围查询。
四、典型业务选型案例
案例 1：只做 key 精确查询，读多写也不少
选哈希表 HashMap。 ❌不要红黑树，单点查询性能更低。
案例 2：既要等值，又经常做范围查询、排序遍历
内存：跳表 / TreeMap；磁盘：B + 树索引。 ❌不要哈希表，哈希无法高效范围扫描。
案例 3：有序字符串前缀搜索（搜索提示）
Trie 前缀树。
案例 4：海量数据快速判断 “元素是否不存在”，不需要拿到数据
布隆过滤器。
案例 5：频繁获取 Top10 最大 / 最小，不需要查任意元素
堆。
案例 6：写压力巨大，海量时序数据，少量范围读
LSM‑Tree。
案例 7：有序数组，极少修改，大量查询
有序数组 + 二分查找。插入删除代价高，适合静态数据集。
五、提升查询效率通用原则
把查询条件匹配到索引键：数据结构的搜索 key 必须是你的查询条件；如果查询条件不是索引 key，再强的数据结构也要全量遍历。
权衡读写开销：没有万能的数据结构。查询越快，往往插入、删除、更新代价越高。
例：B + 树范围查询优秀，但是更新会产生页分裂；哈希表查 key 快，不支持范围。
区分内存与磁盘：内存看重 CPU 时间复杂度；磁盘看重 IO 次数，优先降低磁盘访问次数。
复合场景多级组合：现实工程经常组合使用。
示例：布隆过滤器过滤不存在 key → 哈希缓存热点数据 → B + 树做底层持久存储。
警惕退化场景：哈希冲突、B + 树索引失效、跳表退化，数据倾斜会让理论复杂度失效。
六、快速选型口诀
精确查 key → 哈希
要范围 + 有序 → 跳表 / B + 树 / 红黑树
字符串前缀匹配 → Trie
只取最大最小 → 堆
判断有无、允许误判 → 布隆过滤器
静态有序数据 → 有序数组 + 二分
磁盘海量写多 → LSM‑Tree
磁盘通用索引 → B + 树
本文原创作者：易君召，详见：https://www.yijunzhao.cn/authors/yijunzhao，转载请注明出处。
原文链接
欢迎访问 小易撩挨踢