后端工程中的常见索引结构：B+Tree、跳表、时序分块与倒排索引

我参加工作以来的第一位 mentor 曾说：“后端就是玩表”。刚开始我只把这句话理解为会建表、会写 SQL、会加索引；但真正进入业务后才发现，后端面对的并不只是某一张 MySQL 表，而是一整条围绕数据写入、查询、检索、聚合和派生的工程链路。

在实际工作中，我先后遇到过几类典型问题：AI 对话和 UGC 内容需要在 MySQL 中高效维护主数据；排行榜、热度和实时计数需要借助 Redis ZSet；用户事件、埋点和状态流转天然带有时序特征；而内容搜索、审核结果检索和推荐召回又离不开 Elasticsearch/Lucene。也正是在这些业务需求中，B+Tree、跳表、时序分块、倒排索引这些看似分散的数据结构，被串联到了一条真实的后端数据链路里。

因此，本文从工程实践中常见的存储与查询问题出发，梳理 MySQL InnoDB B+Tree 索引、Redis ZSet、TimescaleDB 时序分块，以及 Elasticsearch/Lucene 倒排索引背后的数据组织方式。理解这些结构，有助于我们判断索引为什么生效、什么时候失效，以及在不同业务场景下应该如何选择更合适的数据存储与检索方案。

MySQL InnoDB 中的索引

理解MySQL中的索引类型，我们可以将其分为三个层次以避免接下来的叙述歧义：逻辑类型、数据结构和物理结构。

我们在开发应用中常说的主键索引、普通索引、唯一索引、联合索引等都属于逻辑类型。而这里提到的四种索引在数据结构上都是由B+Tree实现的，在InnoDB的物理结构上则被分为聚簇索引（Clustered Index）和二级索引（Secondary Index）两类。另外MySQL / InnoDB还支持一些非树状结构的索引类型，不在本文、本章节的讨论范围内，就不展开了。

InnoDB 的聚簇索引与二级索引

在 InnoDB 中，聚簇索引决定了表数据的物理组织方式。通常主键索引就是聚簇索引，因此数据按照主键顺序组织在聚簇索引 B+Tree 的叶子节点中，非叶子节点仅保存索引键和子节点指针用于查找，叶子节点存放的就是完整的数据记录。在这种索引结构下，索引目标直接指向数据本身，因此查询速度极快。

二级索引，也被称为非聚簇索引，其不影响数据物理存储顺序，建立二级索引时实际上会建立一张独立的索引表。二级索引采用独立的 B+Tree 组织索引数据：非叶子节点仅保存索引键和子节点指针用于查找，叶子节点保存索引列和对应的主键值。如果查询列超出二级索引覆盖范围，则需要根据主键回表。

以INSERT为例理解索引机制

Q1：现假设存在表有id, A, B, C四个字段，有索引**PRIMERY KEY(id)和INDEX(A,B,C)** ，当我们向该表中插入一条数据时，会发生什么？

构造待插入记录：首先MySQL Server会进行SQL解析、权限检查等前置工作，然后将插入请求交给InnoDB，由InnoDB构造待插入记录
维护聚簇索引：InnoDB 会在聚簇索引 B+Tree 中进行查找，最终定位到某一个叶子页，然后将完整数据行插入该叶子页；若页空间不足则会发生页分裂，重新平衡B+Tree
维护二级索引：InnoDB会在另一个B+Tree上定位并插入该行记录索引列的值以及主键ID；必要时也会发生页分裂
维护事务相关结构：为了保证事务的 ACID，InnoDB将生成Undo Log、Redo Log，并修改 Buffer Pool 中的数据页，后续由后台线程刷盘

Q2：此时追加插入一条A, B, C字段相同的数据，会发生什么？

当前场景中提到的联合索引是普通索引，其允许重复。并且由于在二级索引的B+Tree中实际参与索引的是(A,B,C,id)，因此二级索引即使允许重复，也始终有唯一顺序，两条记录会自然排在一起。

关于唯一联合索引：如果联合索引使用的是UNIQUE(A,B,C)，那么插入流程会多一步：在索引中查找(A,B,C)是否已经存在，若存在则报Duplicate entry，否则继续插入。

另补充：在对(A,B,C)进行查询时，会首先在二级索引定位第一个(A,B,C)，然后顺着叶子节点查找到已有的上述两条记录主键id，然后依次去聚簇索引找到对应的整行记录，返回两条记录。并因为同一棵 B+Tree 的所有叶子节点按照键值顺序通过双向链表连接起来，查询索引速度依然很快。

另补充：对于支持自增主键的场景，一条不含主键ID的插入SQL到达InnoDB时，会首先申请ID，然后该表AUTO_INCREMENT值+1，接下来的操作和前述内容一致。

索引查询的优先级

MySQL 在存在多个索引时，并不存在固定的"索引优先级"。真正决定使用哪个索引的是优化器（Optimizer），它会根据统计信息估算每种执行方案的成本，选择预估成本最低的执行计划。在实践中，应使用EXPLAIN验证表索引的有效性。常见的索引原则如下：

联合索引最左前缀原则：对于联合索引INDEX(A,B,C)实际上的排序规则是：
```
A → A+B → A+B+C
```
WHERE B 或者WHERE B,C通常无法利用该联合索引做高效的 range/ref 定位，实际以 EXPLAIN 为准
优先选择匹配最多的索引：例如INDEX(A,B,C)与INDEX(A)、INDEX(B)同时存在时，进行查询WHERE A=? AND B=?不会使用单列索引，而是会使用idx_abc的前两列
范围查询会影响后续列的利用：例如 WHERE A=? AND B>? AND C=?，通常只能利用到 A 和 B，C 无法继续参与索引定位
当多个符合条件的索引存在，或索引本身无法满足查询需求时，优化器会对查询成本、是否回标等进行检查和复杂运算，以选择更优的索引

最左前缀索引的数据结构原理：InnoDB创建和维护联合索引的B+Tree时，比较的是复合键，其排序采用字典序（Lexicographical Order） ，类似字符串比较。对于索引INDEX(A,B,C)，先比较A；A相同再比较B；B相同再比较C. 由此可以理解，单独对于列B，其在B+树中的位置根本就不连续，所以单独查询列B时，无法利用该联合索引。

Redis ZSet的数据结构

Redis 本身就是一个 Key-Value 数据库，Key 就是一级索引，没有 MySQL 意义上的二级索引、联合索引、聚簇索引等概念。Redis中数据类型包括String、List、Hash、Set以及ZSet，在本文中着重讨论Redis ZSet的数据结构及其应用。

ZSet被定义为按Socre排序的唯一集合，Score相同时按Member字典序排序。ZSet支持点查询（ZSCORE）、排名查询（ZRANK/ZREVRANK）、范围查询（ZRANGE/ZRANGEBYSCORE）以及权重修改（ZINCRBY），源于其底层结构采用了两种数据结构进行维护：Hash表和跳表。

在ZSet中，Hash table负责元素Member与排序权重Score的映射，因此ZSCORE操作是O(1)的。跳表（SkipList）负责维护Score的排序，时间复杂度为O(log n)。

Q1: 跳表本身也能查询到Member，为什么还需要Hash table呢？

SkipList 实际排序依据是 (score, member)，member本身在跳表中并没有连续性，因此查询成本极高，所以采用了Hash table维护Member - Score，在进行member查询时不会查跳表，这很优雅。

Q2：红黑树的复杂度也是O(logN)为什么不用直接红黑树呢？

实现简单，没有颜色、旋转和平衡设计
跳表从结构上对范围查询的支持天然优秀
插入删除的维护比红黑树更简单
Redis在内存中运行，由于其无需像B+Tree一样优化磁盘IO，因此性能充足

跳表的维护：SkipList 的插入和删除都分为两步：第一步，从最高层开始查找目标位置，并记录每一层最后一个小于目标值的节点（即 update 数组）；第二步，根据随机算法决定新节点的层数，并修改对应层的 forward 指针。删除时同样先找到目标节点，再利用 update 数组将各层前驱节点直接连接到后继节点即可。整个过程无需像红黑树那样旋转，也无需像 B+Tree 那样进行页分裂或页合并，因此实现简单，插入和删除的平均时间复杂度均为 O(logN)。

需要注意的是，Redis中大集合常见实现是 dict + skiplist，但小 ZSet 可能使用 listpack 编码。

TimescaleDB 的时序本质

最近在一个强时序性业务（用户事件上传）中遇到的存储应用需求（往往还需要结合Redis实时计数）。TimescaleDB 本质上是 PostgreSQL 的一个 Extension（扩展），在 PostgreSQL 之上增加了一套专门针对时间序列数据的组织、分区和查询优化机制。

任何时序数据库都有一个特点，即数据随时间不断追加，同时时间列几乎参与所有查询。在普通 PostgreSQL 单大表中，随着时序数据持续追加，表和索引规模不断增大，时间范围查询、历史删除和大窗口聚合的维护成本会上升。

而在TimescaleDB中 Hypertable 将数据按时间序列进行分块（Chunk），由此带来了以下特性：

查询快：只需要访问对应时间的Chunk，其它分区直接跳过，避免了全表扫描
写入快：数据只写当前所在Chunk，索引范围小、缓存命中率高
删除快：对于历史数据的删除，可直接按块DROP CHUNK，速度极快
聚合快：原生提供Continuous Aggregate能力，对于类似avg(cpu)这种情形，可以提前维护每小时平均CPU
时序性：整个数据库按照时间单调递增设计，数据分块、连续平均、自动删除历史等能力都围绕时间

Elasticsearch 中的倒排索引

倒排索引通过将内容与记录反向组织的形式以避免在全文检索中的遍历扫描，其底层实现上并非单一数据结构，而是多层数据结构相结合。Elasticsearch 是基于 Lucene 构建的分布式搜索与分析引擎，Lucene 负责底层索引和搜索能力。本文主要关心 Lucene 的倒排索引数据结构原理。

Lucene 的倒排索引（Inverted Index）不是一种单一数据结构，而是一套围绕全文检索组织的数据结构集合。Lucene 倒排相关结构包括 Term Dictionary、Term Index、Postings/Frequencies、Positions、Payloads/Offsets 等。总的来看，可以将其拆分为词典（Term Dictionary）和倒排列表（Posting List）两部分。

词典

词典维护term到Posting List的映射。

现代Lucene采用 FST作为词典索引（Term Index） 。FST 把所有词项的前缀、后缀都高度共享，压缩成一个状态图。每个词项作为输入路径时，可以在末端输出一个 long 值。这个值就是指向 Term Dictionary 文件中某个 Block 的起始指针和一些元数据（如块内第一个词项、文件偏移等）。

词典（Term Dictionary） 存储每个词项的统计信息，以及指向具体 Posting List 的 文件指针。它并不把所有词项平铺罗列，而是组织成一棵“块树”（Block Tree）。

整体查找流程如下：

FST 拿到最匹配的 Block 地址。
从 .tim 读入该 Block，进行二分查找或顺序扫描，定位到具体词项。
获取 DocFreq 和 .doc 文件指针，准备读取倒排列表。

倒排列表

Posting 被拆成三个主要物理文件，针对不同信息使用不同编码和压缩。Posting List中有每个词对应的DocID列表、词频、词在文档中出现的位置，还有词项的payload及其偏移量。

在Posting中还引入了Skip Data，与完整的跳表不同，它只是Posting List上的跳跃索引，允许在DocID检索时跳过一大段Posting，减少线性扫描。

Posting List中还支持压缩编码，先将升序的文档号和位置转换为差值（Delta 编码），再按固定块大小（如128个）分组，对每组根据最大差值动态选择恰好能容纳的最小位宽，整个块统一用该位宽紧凑存储（Frame of Reference），同时配合跳跃表按需定位和解压，从而实现高压缩率与快速随机访问的平衡。

编码与压缩

在前面提到的Lucene结构中，采用了Delta、FOR编码技术及FST作为前缀共享实现，在这里拆出来讲一下。

Delta编码：增量编码，不存绝对数值，只存相邻数值的差值。例如文档号 [103, 110, 125] → Delta 编码后存 [103, 7, 15]，大幅压缩数值存储消耗的bit数
Frame of Reference（FOR，参照帧压缩） ：传统变长整数（VInt）每个数用整字节，且需要字节对齐；FOR 是按 bit 存储，非常紧密。将 Delta 编码后的数值序列按固定大小（默认 128 个）分成块（Block）。对每个块，找出其中的最大数值，确定需要多少 bit 才能表示（例如最大是 15，则只需 4 bits）。然后整个块的所有数值都用这同一个位宽（4 bits）紧密打包，并在块头记下这个位宽值。
FST（Finite State Transducer，有限状态转换器） ：可以理解为一种升级版的有限状态自动机（FSA），每条边不光有字符，还可以带一个输出值（Output）。沿着字符路径走到达终结状态时，把这些边上的输出累加（或按某种运算组合），就得到了这个词对应的数值。所以，FST = 共享前缀的有向图 + 边上的输出，可以高效存储一个 SortedMap<ByteSequence, Long> 结构。在Lucene中，FST实现了前缀共享、后缀共享和输出值压缩，实现了极高低的压缩率。

附表：常见索引速查表

结构	适用查询	写入代价	典型系统
Hash	等值查询	重哈希、无序	KV、缓存
B+Tree	等值、范围、排序	页分裂、随机写	MySQL/InnoDB
LSM Tree	高写入、范围扫描	Compaction、读放大	RocksDB/LevelDB
倒排索引	全文检索	分词、merge	Lucene/ES
Bitmap	低基数字段过滤	更新成本	OLAP、标签筛选
Trie/FST	前缀、词典压缩	构建成本	Lucene term dict
Bloom Filter	快速判不存在	误判	LSM、缓存穿透
R-Tree/KD/BKD	空间/数值范围	结构维护	GIS、Lucene Point
HNSW/IVF/PQ	向量近邻	召回和内存权衡	向量检索

参考阅读

MySQL 索引