Git/Index / 暂存区内存索引

在有序索引数组中按文件名定位条目

Git 把内存中的 index 条目指针保存在有序、可增长的数组中，按路径和合并 stage 二分查找位置。

v2.46.0索引与查找核验 2026-10-08

工程问题#

暂存区需要频繁判断某个路径是否存在，并定位待替换条目或新条目的插入位置；同一路径在未解决合并时还可能有多个 stage。

实际实现#

index_name_stage_pos 通过数组下标访问中点，以路径和 stage 比较后缩小区间。未命中返回编码后的插入位置；add_index_entry 用 ALLOC_GROW 扩容并移动指针为新条目腾出位置。

处理流程#

以路径和目标 stage 构造比较键
在 cache 指针数组中折半比较
命中返回下标，未命中保留插入位置
需要新增时扩容并移动后续指针

源码片段#

固定版本 · 原文摘录

read-cache.cv2.46.0 · L514–L527

查看原文件

514	first = 0;515	last = istate->cache_nr;516	while (last > first) {517		int next = first + ((last - first) >> 1);518		struct cache_entry *ce = istate->cache[next];519		int cmp = cache_name_stage_compare(name, namelen, stage, ce->name, ce_namelen(ce), ce_stage(ce));520		if (!cmp)521			return next;522		if (cmp < 0) {523			last = next;524			continue;525		}526		first = next+1;527	}

index_name_stage_pos

first 与 last 维护半开搜索区间，cache[next] 提供中点随机访问；比较同时考虑路径和 stage。这里展示普通二分部分，函数后半段还处理 sparse-index 展开，并用 -first-1 编码未命中的插入位置。

CGPL-2.0-only

只摘录二分循环；同文件新增路径中的 ALLOC_GROW 与 MOVE_ARRAY 证明它是可增长指针数组，不能据此声称插入也为 O(log n)。

收益与取舍#

工程分析

带来的收益

普通查找需要 O(log n) 次键比较
有序指针数组兼顾随机访问与按路径扫描

付出的代价

工程分析：中间插入最坏需要移动 O(n) 个指针
路径比较有字符串成本，稀疏索引展开也可能增加开销

可比较的选择

平衡搜索树降低单次中间更新的渐进成本，但树节点和指针遍历会改变内存布局及顺序扫描成本。

版本与适用范围#

对应 Git v2.46.0 内存 index 的 cache 指针数组；条目对象本身不必连续。这不是 Git 对象数据库或提交历史索引，且稀疏索引可能先展开再重新查找。

参考来源#

源码、官方文档与原始论文

git · index_name_stage_pos

read-cache.c · index_name_stage_pos

源码v2.46.0

git · add_index_entry

read-cache.c · add_index_entry