📚 课程目录第2章索引数据结构

索引数据结构：B+树、哈希、全文索引

索引选不对，查询两行泪。我入行前几年，碰过一张千万级的用户表，加了个哈希索引，心想点查够快了吧？结果要做范围统计时，整条SQL直接全表扫描。那次之后我才真正下功夫研究索引底层的三种结构——B+树、哈希、全文索引。

一、B+树：绝大多数数据库的心脏

B+树是多路平衡查找树的变体，说白了就是所有数据都只存在叶子节点，内部节点只存键值和指针。为什么MySQL InnoDB选它做主索引？因为我个人习惯从磁盘IO角度去理解——每个节点刚好塞满一个页（默认16KB），一次磁盘读取就能拿到几十到上千个键值，树高只有3-4层。查询任意一条记录，最多3-4次IO搞定。

最关键的是叶子节点之间用双向链表串联起来。这带来了什么好处？范围查询不用再回溯父节点，顺着链表往后扫就行。我在项目中遇到过一个大坑：有人把表按时间分区分成几十份，却在分区内用了B+树索引，但分区裁剪不当，范围查询跨了太多分区，链表扫描反而变慢。调了分区键顺序后，查询时间从8秒降到了0.2秒。

B+树 vs B树：B树数据分散在所有节点，范围查询要走中序遍历；B+树数据集中在叶子，链表连续读，磁盘预读更高效。

建B+树索引时，有两个参数值得关注：innodb_page_size（默认16KB）和fill_factor（填充因子）。页太小，树高增加；页太大，单次IO浪费。我一般OLTP场景保持默认，OLAP批量写场景可以调小填充因子减少页分裂。

-- InnoDB B+树索引本质是聚簇索引
-- 每次插入或更新都可能触发页分裂
-- 监控索引碎片可以用这个查询
SELECT 
    name, 
    page_number, 
    data_length / 1024 AS data_kb
FROM information_schema.INNODB_SYS_INDEXES
WHERE name = 'YOUR_INDEX_NAME';

我的一点经验：B+树索引的命中率（Buffer Pool中缓存的页比率）如果低于95%，优先检查索引是否建对了，而不是盲目扩内存。

二、哈希索引：快如闪电，但只适合点查

哈希索引用哈希函数将键值映射到桶中，每个桶是一个链表（链地址法解决冲突）。等值查询理论上O(1)，你想想看，一次哈希计算就能定位数据。但为什么OLTP主索引不都用哈希？因为哈希不支持任何范围操作，>、BETWEEN、ORDER BY统统不行。我在项目中见过一个报表系统，把时间戳字段建了哈希索引，结果查询WHERE time > '2024-01-01'走不了索引，全表扫描几百GB数据，运维直接打电话投诉。

我曾经踩过的坑：MySQL的Memory引擎默认就是哈希索引，重启数据就丢，而且不支持事务。千万别拿它存重要业务数据。要是实在想用哈希加速等值查询，可以用InnoDB的自适应哈希索引——它会自动把热点的B+树页转为哈希缓存，对用户透明。

哈希索引的另一个问题是哈希冲突。当冲突链太长，查询退化接近O(n)。解决办法：保证哈希函数分布均匀，桶的数量够大。实际库中CRC32或FNV方案比较常见，但记住，哈希索引不能用部分前缀匹配，因为整个键值都被哈希了。

三、全文索引：对付大段文本的屠龙刀

当你需要在文章、评论、描述这些长短文本里搜关键词，LIKE '%xxx%'根本走不了B+树索引，必须全文索引上。全文索引的核心是倒排索引——把文档中的词项（term）解析出来，记录每个词出现在哪些文档以及具体位置。查询时先查词项词典，再找到文档列表，最后做相关性排序（比如经典的TF-IDF）。

我处理过社区发帖的搜索功能，用户输入「漫威复联」，如果用LIKE '%漫威%'或%复联%，SQL跑了3秒以上。换成MySQL的MATCH ... AGAINST全文索引，耗时降到0.01秒。但要注意中文分词——MySQL内置的分词器对中文支持很差，我建议用Elasticsearch或带ngram插件的方案。在MySQL里至少得设好ngram__size，否则「双肩包」会被拆成「双」「肩」「包」，搜不出正确结果。

-- MySQL 创建全文索引（支持ngram）
ALTER TABLE articles ADD FULLTEXT INDEX ft_body (body) WITH PARSER ngram;

-- 查询用法
SELECT * FROM articles 
WHERE MATCH(body) AGAINST('+漫威 +复联' IN BOOLEAN MODE);

全文索引的缺点也很明显：写入代价高，每次插入或更新都得重新拆词更新倒排表。不适合高频写入的OLTP表，我只在只读或准只读的搜索场景下用。

四、三种索引一表对清

特性	B+树索引	哈希索引	全文索引
查询类型	等值、范围、排序、前缀匹配	等值（精确匹配）	文本关键词、短语、布尔
存储结构	多路平衡树 + 叶子链表	哈希桶 + 链地址法	倒排列表（词项→文档ID列表）
磁盘IO次数	树高3~4次（最差）	通常1~2次（无冲突）	词典常驻内存，取文档需随机IO
支持排序	✅（按索引顺序）	❌	仅相关性排序
写放大	低（页分裂时较高）	低	高（拆词+倒排合并）
典型引擎	InnoDB、MyISAM（非聚簇）	Memory、InnoDB自适应	MyISAM、InnoDB（5.6+）

五、一张图看懂三种索引结构

嗯，到这里你应该对三种索引的结构和脾气有了底。下次设计表结构时，多花一分钟想想：查询模式是什么？是点查还是范围？要不要排序？有没有大文本搜索？搞清楚了再下手，避免后期重造索引的剧痛。