索引数据结构原理（B+树、倒排索引）
为什么需要了解索引结构？
做加密SDK兼容排查时，我经常会遇到一种情况——明明代码逻辑没问题，但查询就是慢得离谱。你想想看，加密SDK里经常要查密钥、查设备指纹、查黑白名单，这些操作背后都依赖索引。不懂索引结构，出了问题都不知道从哪里下手。
我记得刚入行时接手过一个项目，一条简单SQL跑了十几秒。加了个索引就降到几十毫秒。嗯，从那以后我就再也不把索引当黑盒了。说白了，索引就是数据的「目录」，但不同场景的目录结构差别很大。今天我就把两种最核心的索引结构掰开揉碎了讲清楚。
B+树：数据库索引的基石
B+树是什么？说白了就是一棵平衡的多路搜索树，所有数据都存放在叶节点上。这是关系型数据库最常用的索引结构，MySQL的InnoDB引擎就用它。
为什么数据库选B+树而不是二叉树？我举个例子：假设有一张1000万行的表，二叉树的高度要20多层，每次读取一个节点就要一次磁盘IO。20多次IO，你想想看得有多慢。B+树一个节点能存几百个键值，树高通常只有3到4层。这就是为什么它能扛住大数据量。
B+树的核心特点：
- 所有数据都在叶节点，内部节点只存键值做路由
- 叶节点之间通过链表连接，支持范围查询
- 每个节点通常对应一个磁盘页大小（InnoDB默认16KB）
- 插入和删除都会触发节点分裂或合并，保持树平衡
我在项目中遇到过一个问题：某个表数据量涨到5000万后，插入速度突然暴跌。查了半天，发现是B+树的叶节点分裂太频繁了。每次分裂都要修改大量指针，导致写性能雪崩。当时我的解决方案是调整了索引字段的顺序，把离散度高的字段放前面，大大减少了节点分裂频率。
避坑指南：
我曾经接手过一个慢查询，明明走索引了还是慢。后来发现是索引字段的基数太低——性别字段只有两个值，B+树几乎把所有数据都塞到一个叶节点里。这种索引建了还不如不建。我的经验是：基数低于1000的字段不要单独建索引，优先考虑联合索引。
B+树还有一个容易被忽略的点：聚簇索引和非聚簇索引的区别。InnoDB的主键索引就是聚簇索引，数据直接存在叶节点上。而辅助索引的叶节点存的是主键值，所以查询时先走辅助索引找到主键，再回表查数据。这就是为什么主键长度越小，辅助索引越高效。
倒排索引：全文检索的核心
倒排索引又是什么？它常用于搜索引擎与全文检索领域。比如你在一堆文档里搜「加密SDK」，传统方式要遍历所有文档，看每篇里有没有这个词。数据量一上来，这种方式根本没法用。
倒排索引的思路反过来了——它不建立从文档到词的映射，而是建立从词到文档列表的映射。这样查「加密SDK」的时候，直接找到这个词对应的文档ID列表，瞬间定位。
# 倒排索引构建示例（伪代码）
documents = [
{"id": 1, "content": "加密SDK支持AES算法"},
{"id": 2, "content": "AES算法需要密钥管理"},
{"id": 3, "content": "SDK兼容性问题排查"}
]
# 构建倒排列表
inverted_index = {}
for doc in documents:
for word in tokenize(doc["content"]):
if word not in inverted_index:
inverted_index[word] = []
inverted_index[word].append(doc["id"])
# 查询"SDK" -> 返回 [1, 3]
我曾经在项目里碰到过一个怪问题——用加密SDK的全文检索功能，关键词明明存在，就是查不出来。最后发现是分词器词典没更新。「AES-256」被分成了「AES」和「256」，而索引里只有「AES-256」这个完整词条。匹配不上，自然查不到。
注意：倒排索引的维护成本很高
尤其是文档频繁增删时。每新增一篇文档都要重新解析、拆词、更新倒排列表。如果你的系统需要实时写入，建议用延迟合并策略：先把新数据放在一个小的内存索引里，等积累到一定量再批量合并到磁盘上的主索引。这样可以避免逐条修改带来的性能开销。
倒排索引还有两个关键优化：压缩和跳表。压缩是为了节省空间——倒排列表里的文档ID通常用差值编码存储，比如5,8,9存成5,3,1，空间能省一大半。跳表则是为了加速查询——如果你要同时查两个词的文档交集，有跳表结构就不用一一比对，直接跳着查。
B+树 vs 倒排索引：你怎么选？
很多人问过我这个问题：加密SDK里到底用哪种索引？我一般这样回答：看场景。如果你主要做精确匹配和范围查询，选B+树；如果你做关键词搜索，选倒排索引。还有一种混合场景——比如既按用户ID（精确值）查，又要按描述文字（关键词）搜，那就两种索引都用上。
| 维度 | B+树 | 倒排索引 |
|---|---|---|
| 核心用途 | 精确匹配、范围查询、排序 | 全文检索、关键词搜索 |
| 存储结构 | 平衡多路树，数据在叶节点 | 词项 → 文档ID列表 |
| 查询复杂度 | O(log N) | O(1) 查词项，O(K) 取列表 |
| 写性能 | 较高（依赖节点分裂策略） | 较低（需分词、合并列表） |
| 空间占用 | 较低 | 较高（需存词典和倒排列表） |
| 典型应用 | 数据库索引、订单查询 | 搜索引擎、日志分析 |
嗯，说到最后我想强调一点：索引不是建得越多越好。我在项目里见过一张表建了十几个索引，写入速度慢到让人崩溃。每次写入都要更新所有索引，代价非常高。我的习惯是：先分析查询模式，再针对性地建索引。不常用的索引该删就删，别舍不得。