索引设计与海量数据查找 | 算法教程

加载中…

索引设计与海量数据查找 | 算法教程

一、问题背景

当数据量达到千万、亿级时，如何在海量数据中快速查找某条记录？

核心矛盾：

内存放不下所有数据 → 必须依赖磁盘
磁盘 IO 极慢（毫秒级 vs 内存纳秒级）→ 必须减少 IO 次数
数据持续增长 → 索引必须支持动态插入/删除

二、索引的需求定义

以数据库为例，索引需支持：

需求类型	示例
等值查询	`WHERE id = 1234`
区间查询	`WHERE id BETWEEN 1000 AND 2000`
前缀匹配	`WHERE name LIKE '张%'`
排序	`ORDER BY create_time DESC`

性能约束：

查询尽可能少磁盘 IO
索引本身不能占太多内存
写入时索引维护代价可控

三、候选数据结构对比

数据结构	等值查询	区间查询	磁盘友好	动态更新
散列表	O(1)	❌	一般	✅
有序数组	O(log n)	✅	✅	❌ 插入慢
二叉搜索树	O(log n)	✅	❌ 树高	✅
跳表	O(log n)	✅	一般	✅
B+树	O(log_m n)	✅	✅ 矮胖	✅

INDEX(a, b, c)

✅ WHERE a = 1
✅ WHERE a = 1 AND b = 2
✅ WHERE a = 1 AND b = 2 AND c = 3
❌ WHERE b = 2（跳过了 a）
❌ WHERE c = 3（跳过了 a, b）

-- 索引 INDEX(name, age)
SELECT name, age FROM user WHERE name = '张三';
-- 直接从索引返回，不访问数据行

场景	示例
对索引列使用函数	`WHERE YEAR(create_time) = 2024`
隐式类型转换	`WHERE phone = 13800138000`（phone 是 varchar）
LIKE 左模糊	`WHERE name LIKE '%张'`
OR 连接非索引列	`WHERE a = 1 OR b = 2`（b 无索引）
NOT IN / !=	通常导致全表扫描