tgrep磁盘格式揭秘：lookup.bin、index.bin倒排表与6字节条目设计全解析
【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgrep
tgrep 是一个基于三元组（trigram）倒排索引的 grep 工具，采用客户端/服务器架构，让大型代码库的本地正则搜索快到惊人。它的秘密藏在索引目录里的几个二进制文件中：lookup.bin倒排表、index.bin的 6 字节帖子条目，以及files.bin的文件路径映射。本文带你完整拆解这套磁盘格式的设计，看完你就明白 tgrep 为什么能比常规扫描快出数倍。
📁 索引目录里有什么？
运行tgrep index .或tgrep serve .后，仓库根目录下会出现一个.tgrep/索引目录，核心文件分工如下：
| 文件 | 角色 |
|---|---|
lookup.bin | 排序后的「三元组 → 倒排表指针」查找表 |
index.bin | 所有倒排链（posting lists）的拼接区 |
files.bin | 文件 ID → 相对路径的映射表 |
meta.json | 版本号、文件/三元组数量、时间戳、覆盖完整性 |
filestamps.json | 逐文件的 mtime/大小等版本证据，用于增量对账 |
其中前三个二进制文件就是本文的主角，完整文件清单见 README.md。
🔍 lookup.bin：16 字节定长条目的有序查找表
lookup.bin是整套格式的入口。它由固定16 字节的条目组成，按三元组哈希值排序，查询时可以二分查找：
┌────────────────┬────────────────┬────────────────┐ │ trigram_hash │ offset │ length │ │ u32 (4B LE) │ u64 (8B LE) │ u32 (4B LE) │ └────────────────┴────────────────┴────────────────┘三个字段各司其职：
- trigram_hash（4 字节）：三元组本身就是哈希。tgrep 把 3 个字节直接打包进 24 位整数，如
"the"→0x746865，无碰撞空间可达约 1670 万种组合，详见 trigram.rs； - offset（8 字节）：该三元组对应的倒排链在
index.bin中的起始字节偏移； - length（4 字节）：倒排链的条目数。
因为条目定长且有序，tgrep 可以直接把整个文件 mmap 进内存做零拷贝二分查找，相关实现在 reader.rs 的IndexReader中。
📇 index.bin：6 字节帖子条目的倒排表
index.bin存储所有倒排链的连续拼接。每条帖子（posting）只有6 字节：
file_id (u32 LE) + loc_mask (u8) + next_mask (u8) = 6 bytes| 字段 | 大小 | 含义 |
|---|---|---|
file_id | 4 字节 | 该三元组出现的文件 ID，指向files.bin |
loc_mask | 1 字节 | 位置掩码：bit i 置位表示三元组出现在offset % 8 == i的字节位置 |
next_mask | 1 字节 | 8 位布隆过滤器，记录紧跟在三元组之后的字符 |
结构定义在 ondisk.rs 的PostingEntry，是理解 tgrep 空间效率的关键。
💡 6 字节条目的设计玄机
为什么只有 6 字节却还能「超额交付」？两个 1 字节掩码花得极值：
- loc_mask 支持相邻性校验：查询字面量
"hello"会被拆成"hel"、"ell"、"llo"等三元组。仅凭倒排链只能证明「三个三元组都出现在文件 A」，不能证明它们连在一起。把每个三元组出现位置的offset % 8记成 1 位掩码后，只需把前一个三元组的掩码左旋 1 位再与下一个做与运算，非零即可能相邻（见 trigram.rs 的check_adjacency）。 - next_mask 过滤假阳性：文件里同时存在
"abcX"和"abc"的其他变体时，"abc"的倒排链一定非空，但下一个字符未必匹配。next_mask用 8 位布隆位记录后续字节，一行位与运算就能砍掉大量伪候选。
也就是说，tgrep 用 2 个额外字节换来了无需回读文件即可缩小候选集的能力——这正是它比朴素倒排索引更准更快的核心。
另外，倒排链按三元组哈希整体排序写入（构建逻辑在 builder.rs），配合 8192 条/次的分块缓冲写入，磁盘 I/O 全部是顺序大块写。
🗂️ files.bin：从文件 ID 到真实路径
倒排条目里只存 4 字节的file_id，那真实路径在哪？答案是files.bin：先写一个版本化魔数头（当前为版本 3，由INDEX_FORMAT_VERSION控制），随后是变长记录：
file_id (u32 LE) + path_len (u16 LE) + path_bytes文件 ID 保证是 0..N 的稠密无重复序列，读取端会严格校验（reader.rs），防止损坏的 ID 触发巨型内存分配。路径长度受u16上限约束，超长路径会在构建期直接报错而不是静默截断。
⚡ 一次查询是如何落地的
把三块拼起来，查询路径就清晰了：
- 把正则中的字面量部分拆成三元组（如
"fn main"→"fn "、"f m"、" ma"…）； - 对每个三元组在 mmap 的
lookup.bin中二分定位，直接读出index.bin里的倒排链区间； - 对多个三元组做倒排链求交，并用
loc_mask/next_mask过滤假阳性，得到候选文件 ID 集合； - 通过
files.bin把 ID 还原成路径，最后只用真正的正则引擎并行验证这些候选文件。
也就是说，绝大多数与查询无关的文件在整个搜索过程中一个字节都不会被读取。
🛡️ 版本管理与防损坏设计
- 版本头：
files.bin的魔数头带版本号，旧版本读者遇到新格式会主动拒绝而非误读（ondisk.rs）； - 尺寸校验：
lookup.bin大小若不是 16 的倍数、index.bin超出可用地址空间，读取端立即报错； - 截断检测：
files.bin变长记录逐条校验剩余长度，尾部缺 3 个字节都会触发IndexCorrupted错误； - 完整性元数据：
meta.json记录构建完整性标记与文件表指纹，服务器据此判断索引是否可用（meta.rs）。
这套「宁可大声失败、不可静默截断」的防御风格，也让 fuzz/ 目录下的模糊测试有了明确的攻击面。
✅ 小结
tgrep 的磁盘格式教科书式地展示了倒排索引工程的权衡艺术：
lookup.bin用 16 字节定长条目 + 排序，让查找只需一次二分；index.bin用 6 字节帖子条目，用loc_mask和next_mask两个字节额外信息换取更少的假阳性与文件回读；files.bin把路径从热路径中剥离，让倒排链保持紧凑。
配合 mmap 零拷贝读取与顺序大块写入，这套格式正是 tgrep 在大型代码库上实现极速正则搜索的基石。想动手验证的话，克隆仓库后运行tgrep index .再打开.tgrep/目录，就能亲眼看到这些文件的规模对比。
【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgrep
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
