.idx 文件:fanout 表与二分查找

← 上一篇 delta 链:window 与 depth 对 pack 大小的影响

布局

实测 · 本机执行输出

  魔数 b'\xfftOc'  版本 2  对象数(fanout[255]) = 3,032  文件大小 85,968 字节
  0000  ff 74 4f 63 00 00 00 02 00 00 00 09 00 00 00 14  .tOc............
  0010  00 00 00 20 00 00 00 2c 00 00 00 34 00 00 00 41  ... ...,...4...A
  …(共 85968 字节)
  各段字节范围: fanout [8,1032)  hash 表 [1032,61672)  crc 表 [61672,73800)  offset 表 [73800,85928)  再加 20+20 字节校验和
  4 + 4 + 1024 + 3032×(20+4+4) + 40 = 85,968(与文件大小一致: True)

v2 的 .idx 依次是:魔数 \377tOc、版本号 2、256 项 fanout 表、对象 hash 表(按升序)、每个对象的 CRC32 表、每个对象在 pack 里的偏移表(超过 2 GB 的偏移走 64 位表)、pack 的 SHA-1、idx 自己的 SHA-1。每个对象在 idx 里占 28 字节。

fanout 表

实测 · 本机执行输出

  hash 表是按 hash 升序排列的: True
  用 hash 表重新数出来的累计值与 fanout 全部一致: True
  部分条目:
    fanout[0x00] =     9   该档对象数 = 9
    fanout[0x01] =    20   该档对象数 = 11
    fanout[0x7f] =  1493   该档对象数 = 7
    fanout[0xfe] =  3021   该档对象数 = 6
    fanout[0xff] =  3032   该档对象数 = 11
  256 档的对象数:最少 4,最多 23,平均 11.8

fanout[i] 是 hash 第一个字节不超过 i 的对象个数,最后一项就是对象总数。hash 近似均匀分布,所以每一档大小接近(本例 4~23 个,平均 11.8)。

查找

实测 · 本机执行输出

  目标 4102105e48f2ee80cbb6be56a4dbb3cb56d92f20
  第一个字节 0x41 → fanout[0x40]=773, fanout[0x41]=786,候选范围 [773, 786) 共 13 个
    第 1 次比较:下标 779  hash 412c89ac4ceb…  > 目标
    第 2 次比较:下标 776  hash 4113bd999f10…  > 目标
    第 3 次比较:下标 774  hash 4108fa986f0d…  > 目标
    第 4 次比较:下标 773  hash 4102105e48f2…  == 目标
  下标 773 → offset 表里的值 37542;git verify-pack 给出的偏移 37542  一致: True

用 hash 的第一个字节从 fanout 查到一段范围 [fanout[b-1], fanout[b]),只在这一段里二分;找到下标后,在偏移表同一下标取出 pack 里的位置。

省多少

实测 · 本机执行输出

  对象数 N=3032
  不用 fanout(整表二分):平均 10.65 次,最多 12 次;log2(N) = 11.57
  用 fanout 圈范围再二分:平均 3.10 次,最多 5 次

3,032 个对象,整表二分平均 10.65 次比较,用 fanout 平均只要 3.10 次,最多 5 次。代价是多存一张 1 KB 的表。对象越多,整表二分的步数越大(log N),fanout 把查找范围先缩小 256 倍左右。

校验

实测 · 本机执行输出

  idx 倒数第 40~21 字节(pack 的 SHA-1): 9e4d0c96da5052a6f9768bc476a5597bef2ccfb0
  pack 文件最后 20 字节               : 9e4d0c96da5052a6f9768bc476a5597bef2ccfb0
  idx 最后 20 字节(idx 自己的 SHA-1)  : 4add1e1a599c42de31f21e222021860ba22d4585
  重新算 idx 前面全部内容的 SHA-1        : 4add1e1a599c42de31f21e222021860ba22d4585
  取 pack 里偏移 262 的条目原始字节算 CRC32 = 15673c87;idx 的 crc 表里这一项 = 15673c87  一致: True

idx 同时记着 pack 的校验和(与 pack 文件末尾相同,用于配对)和自己的校验和;crc 表让复用 pack 里的原始数据(比如 fetch 时)时不用解压就能检查数据是否损坏。

分步演示

.idx 与 fanout

本步的对象

本文用到的工具与边界

本机 macOS 27 arm64 / git 2.54.0(Apple Git-157);每个实验在临时目录里新建仓库,HOME 和全局配置指向实验专用的空目录(不读用户自己的 git 配置),提交的作者与时间固定以便复现;需要网络协议的实验用本机的 file:// 或 git daemon 回环端口(9800 以上),不碰任何远程仓库;计时用 time.perf_counter,数字每次运行会有小幅抖动。仓库是 3000 个很小的文件加 git gc 之后的单个 pack(3,032 个对象:3,000 个 blob、31 个 tree、1 个 commit);.idx 由我用 Python 按字节解析(ll.py 外,实验脚本内),对账对象是 git verify-pack -v 和 pack 文件末尾
没有验证:超过 2 GB 的 pack 的 64 位偏移表;idx 版本 1(已淘汰);multi-pack-index 与 reverse index(.rev,后面单独一篇讲 multi-pack-index);hash 分布不均匀时 fanout 的退化;SHA-256 仓库的 idx(hash 长 32 字节)

下一篇 · GIT 20

multi-pack-index