tgrep磁盘格式揭秘：lookup.bin、index.bin倒排表与6字节条目设计全解析

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/tgreptgrep 是一个基于三元组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.bin16 字节定长条目的有序查找表lookup.bin是整套格式的入口。它由固定16 字节的条目组成按三元组哈希值排序查询时可以二分查找┌────────────────┬────────────────┬────────────────┐ │ trigram_hash │ offset │ length │ │ u32 (4B LE) │ u64 (8B LE) │ u32 (4B LE) │ └────────────────┴────────────────┴────────────────┘三个字段各司其职trigram_hash4 字节三元组本身就是哈希。tgrep 把 3 个字节直接打包进 24 位整数如the→0x746865无碰撞空间可达约 1670 万种组合详见 trigram.rsoffset8 字节该三元组对应的倒排链在index.bin中的起始字节偏移length4 字节倒排链的条目数。因为条目定长且有序tgrep 可以直接把整个文件 mmap 进内存做零拷贝二分查找相关实现在 reader.rs 的IndexReader中。 index.bin6 字节帖子条目的倒排表index.bin存储所有倒排链的连续拼接。每条帖子posting只有6 字节file_id (u32 LE) loc_mask (u8) next_mask (u8) 6 bytes字段大小含义file_id4 字节该三元组出现的文件 ID指向files.binloc_mask1 字节位置掩码bit i 置位表示三元组出现在offset % 8 i的字节位置next_mask1 字节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），仅供参考