索引格式 · 倒排索引与符号表

注意最后那个 TOC（Table of Contents），规范说它“serves as an entry point into the index”——而且它在文件末尾**。**

为什么目录放最后？因为索引是顺序写出来的：写的时候你并不知道各个段最终有多长、在什么偏移。写完了才知道，所以把“各段在哪”的目录追加在最后。读的时候先跳到文件尾读 TOC，再按图索骥。

这是“一次顺序写”格式的经典手法（ZIP 文件的中央目录也在末尾，同一个道理）——它让写入永远是顺序追加，不用回头改已写的部分。又一次呼应不可变 + 顺序写这条主线。

规范原文：

The symbol table holds a sorted list of deduplicated strings that occur in label pairs of the stored series. They can be referenced from subsequent sections and significantly reduce the total index size.

想想为什么这招这么有效： 一个 block 里有 100 万条 series，它们的标签里，job="api-server" 这个字符串可能出现 50 万次、__name__="http_requests_total" 出现 10 万次。如果每条 series 都存一份完整字符串，索引会被重复字符串撑爆。

符号表的做法：把所有出现过的字符串去重、排序、存一份，然后各处只存“第几个字符串”这个整数引用。

符号表:  [0]="__name__"  [1]="api-server"  [2]="http_requests_total"  [3]="job" ...
series:  { 3→1, 0→2 }   ← 只存整数,不存字符串!
         (job="api-server", __name__="http_requests_total")

这和第 1 部分那个 dedupelabels 的 Labels 实现是同一个思想在两个层面的体现：内存里去重共享标签、磁盘上用符号表去重字符串。“标签字符串大量重复”这个观察，被 Prometheus 在每一层都利用到了。

为什么要排序？因为排序后可以二分查找，而且相邻字符串常有公共前缀，利于进一步压缩。

“倒排”的意思是：正着是“series → 有哪些标签”，倒过来是“标签 → 有哪些 series”。查询要的正是后者。

于是 {job="api-server", status="500"} 的求解变成：

postings(job="api-server") = [1, 5, 7, 12, 19, 23]
postings(status="500")     = [5, 12, 88, 91]
────────────────────────────────────────────────
交集(AND)                  = [5, 12]      ← 答案

多个匹配器 = 多个 postings 求交集。 这就是为什么 PromQL 里加一个标签筛选通常会让查询更快——交集只会更小。

而“单调递增”这个约束是关键：两个有序列表求交集，可以用归并的方式线性扫过去（两个指针，谁小谁前进），而不需要哈希表或排序。这是倒排索引能快的核心原因——所有的集合运算（交、并）都退化成有序列表的归并。

更进一步：有序还允许 跳跃（skip） 优化——如果一个列表当前是 5、另一个是 88，可以直接跳过第一个列表里所有 < 88 的项，不用逐个比。这在列表长度差异悬殊时（比如 job="api" 有 50 万条、status="500" 只有 10 条）能带来巨大加速。

注意这是个两级查找**：先查 offset table 找到 postings 的位置，再去读 postings 本身。**

为什么不把它们放一起？因为 offset table 小得多（每个标签对一条记录），可以整个加载进内存或轻松二分；而 postings 本身很大（一个热门标签对的 series 列表可能有几十万个 uint32），按需读取更合理。

“小的元数据常驻，大的数据按需读”——这是几乎所有存储引擎的通用套路。

倒排索引对“等值匹配”（job="api"）极快——直接查表拿 postings。但对“正则匹配”（job=~"api.*"）就没那么美好了。

因为倒排索引是按“具体的标签对”建的，job=~"api.*" 没有现成的 postings。TSDB 必须：

1. 遍历 job 这个标签的所有取值，逐个用正则测试。
2. 把所有匹配上的取值的 postings 求并集。

如果 job 有 10 万种取值，这就是 10 万次正则匹配 + 一次大规模并集。 这也是为什么：

• 能用等值就别用正则 —— {job="api"} 远快于 {job=~"api"}（后者虽然结果一样，但走的是正则路径）。
• 锚定的正则更快 —— Prometheus 会对 =~"api.*" 这类做优化（提取公共前缀），但 =~".*api.*" 这种两头开放的几乎必然全表扫。
• 高基数标签上做正则 = 灾难 —— 又一次，基数是万恶之源。

源码里 model/labels/regexp.go 专门做正则优化（比如识别出“其实是个等值匹配”、提取字面量前缀），但它只能优化，不能变魔术。第 4 部分讲 PromQL 性能时会再碰这个话题。