Почему git хранит объекты в каталогах с первыми двумя символами хэша?

Я разрабатываю структуру каталогов на основе UUID, поэтому я смотрю, что делает git, чтобы убедиться, что это будет хорошая модель.

Я вижу, что git хранит объекты в структуре, где первые два символа хеша используются как каталог, а остальная часть хэша - это имя файла.

Что мне интересно, почему? Если есть большое преимущество в использовании каталогов, почему не создано больше подкаталогов... скажите каталог для каждого из двух или двух символов в хэше, создающем дерево? Если нет большого преимущества, то почему каталог с первыми двумя символами?

Ответ 1

Git переключается с "свободных объектов" (в файлах с именем 01/23456789abcdef0123456789abcdef01234567) на "пакеты", когда количество свободных объектов превышает магическую константу (6700 по умолчанию, но настраивается, gc.auto). Поскольку значения SHA-1, как правило, хорошо распределены, они могут аппроксимировать общие свободные объекты, просматривая их в одном каталоге. Если в одном из каталогов объектов больше (6700 + 255)/256 = 27 файлов, это время для пакетного файла.

Таким образом, нет необходимости в дополнительном отключении (01/23/4567...): маловероятно, что вы получите столько объектов в одном каталоге. Фактически, больший разветвление, как правило, затрудняет обнаружение, что пришло время автоматической упаковки, если вы не установили пороговое значение выше (чем 6700), потому что (27 + 255)/256 равно 1, так что вы 'd хотите считать все в 01/*/, а не просто 01/.

Можно использовать 0/1234567... и разрешить до ~ 419 объектов в каталоге для получения одинакового поведения, но сканирование линейных каталогов (в любой системе, которая все еще использует их): O (n ²), а 27 ² - всего 729, а 419 ² - 175561. [Edit: это относится только к созданию файла, где у вас есть двухэтапный поиск, один раз, чтобы найти что он ОК, чтобы создать, и секунду, чтобы найти слот или добавить. Поиск по-прежнему O (n).]