引言
索引是数据库提升查询性能最有效的手段之一。但索引并不是银弹——不当的索引设计反而会拖慢写入性能、 浪费存储空间。理解不同索引的底层数据结构，是做出正确索引决策的前提。
本文针对三种最常见的索引类型——B+ 树、哈希索引和倒排索引——做一次深度解剖。
B+ 树：最通用的索引结构
B+ 树是关系型数据库的默认选择。MySQL 的 InnoDB、PostgreSQL 的默认索引都基于 B+ 树。
数据结构
B+ 树是一棵多路平衡查找树，与普通的 B 树相比有两个关键区别：
- 内部节点只存键，不存值：所有数据都存储在叶子节点
- 叶子节点通过链表相连：形成一个有序链表，便于范围查询
以 InnoDB 的聚簇索引为例，每个节点（通常是 16KB 页面）的结构大致如下：
// B+ 树页面结构（简化）
type BPlusPage struct {
PageHeader struct {
PageType uint16
NumRecords uint16
IndexID uint32
NextPage uint32
PrevPage uint32
}
Records []Record
}
查询复杂度
B+ 树的高度通常非常低。对于一个拥有 1000 万行数据的表，B+ 树的高度一般在 3-4 层。
| 行数 | 高度 | 最坏 I/O |
|---|---|---|
| 1,000 | 2 | 2 次 |
| 100,000 | 2 | 2 次 |
| 10,000,000 | 3 | 3 次 |
| 1,000,000,000 | 4 | 4 次 |
优势与局限
优势：支持范围查询（BETWEEN、>、<）、排序（ORDER BY）、 前缀匹配（LIKE ‘abc%’）、同时支持等值查询和范围查询。
局限：写入时需要维护树的平衡性，随机写入可能导致较多的页面分裂和合并。 InnoDB 的自增主键设计就是为了减少这种开销。
哈希索引：最快的等值查询
哈希索引基于哈希表实现。将键值通过哈希函数映射到桶中，理论上等值查询可以达到 O(1) 的时间复杂度。
但哈希索引的局限性也非常明显：
- 不支持范围查询：哈希函数破坏了键的有序性
- 不支持排序：ORDER BY 无法利用哈希索引
- 不支持部分匹配：LIKE 查询无法使用
- 哈希冲突：极端情况下退化为线性查找
MySQL 的 Memory 引擎默认使用哈希索引。InnoDB 也有自适应哈希索引（Adaptive Hash Index）， 但它是一个由 InnoDB 自动管理的内部优化，用户无法直接控制。
使用建议：在只需要等值查询且查询量极大的场景下考虑哈希索引， 例如缓存表、用户会话表。但大多数场景下，B+ 树是更稳妥的选择。
倒排索引：全文搜索的核心
前面两种索引都是基于键的有序性或哈希性来加速查找。但当我们搜索的关键词不是完整字段值， 而是文本内容中的某个词时，就需要倒排索引（Inverted Index）。
原理
倒排索引的构建过程：将文档集合中的每个文档分词，建立"词 → 文档列表"的映射。
type InvertedIndex struct {
Dictionary map[string]*PostingList
}
type PostingList struct {
DocIDs []uint64
Positions [][]uint16
TF []float32
}
实际应用
倒排索引广泛用于全文检索引擎：
- Elasticsearch：基于 Lucene，倒排索引是其核心
- PostgreSQL：通过 tsvector 数据类型支持全文检索
- MySQL：InnoDB 在 5.6 版本后支持 FULLTEXT 索引
如何选择索引策略
| 查询类型 | 推荐索引 | 示例 |
|---|---|---|
| 等值查询 | B+ Tree / Hash | WHERE id = 100 |
| 范围查询 | B+ Tree | WHERE age BETWEEN 20 AND 30 |
| 排序 | B+ Tree | ORDER BY created_at |
| 前缀匹配 | B+ Tree | WHERE name LIKE '张%' |
| 全文搜索 | 倒排索引 | MATCH(content) AGAINST('关键词') |
| 联合条件覆盖 | 联合索引 (B+) | WHERE a=1 AND b>2 |
总结
理解索引的底层数据结构能帮你在数据库调优时做出更明智的决策。核心要点：
- B+ 树是通用方案，绝大多数场景的默认选择
- 哈希索引适合极致的等值查询，但功能有限
- 倒排索引面向文本搜索场景，与传统 B+ 树互补
- 索引不是越多越好——每个索引都会拖慢写入性能