Możliwe jest umieszczenie wszystkich plików w jednym katalogu, choć czasem może to być nieco duże. Wiele systemów plików ma ograniczenia . Chcesz umieścić repozytorium git na dysku sformatowanym w systemie FAT32 na pamięci USB? Możesz przechowywać tylko 65 535 plików w jednym katalogu. Oznacza to, że konieczne jest podzielenie struktury katalogów, aby zapełnienie jednego katalogu było mniej prawdopodobne.
Stałoby się to nawet problemem w przypadku innych systemów plików i większych repozytoriów git. Stosunkowo małe repozytorium git, które mam na hangoucie (około 360 MB) i ma 181 546 obiektów na pliki 11k. Wyciągnij repozytorium Linuksa, a otrzymasz 4 374 054 obiektów. Jeśli umieściłbyś je wszystkie w jednym katalogu, niemożliwe byłoby wyewidencjonowanie i spowodowałoby awarię (w pewnym sensie „awarii”) systemu plików.
Więc? Dzielisz to na bajty. Podobne podejścia stosuje się w aplikacjach takich jak FireFox:
~/Li/Ca/Fi/Pr/7a/Cache $ ls
0/ 4/ 8/ C/ _CACHE_001_
1/ 5/ 9/ D/ _CACHE_002_
2/ 6/ A/ E/ _CACHE_003_
3/ 7/ B/ F/ _CACHE_MAP_
Poza tym chodzi również o kwestię wydajności. Rozważ wydajność NTFS z wieloma długimi nazwami plików :
System Windows NT zajmuje dużo czasu na wykonywanie operacji katalogowych na dyskach sformatowanych w systemie plików Windows NT (NTFS), które zawierają dużą liczbę plików o długich nazwach plików (nazwach niezgodnych z konwencją 8.3) w jednym katalogu.
Gdy NTFS wylicza pliki w katalogu, musi wyszukać nazwy 8.3 związane z długimi nazwami plików. Ponieważ katalog NTFS jest utrzymywany w stanie posortowanym, odpowiadające im długie nazwy plików i nazwy 8.3 zazwyczaj nie znajdują się obok siebie na liście katalogów. Tak więc NTFS używa liniowego przeszukiwania katalogu dla każdego obecnego pliku. W rezultacie czas potrzebny na wykonanie listy katalogów wzrasta wraz z kwadratem liczby plików w katalogu. W przypadku niewielkiej liczby plików (mniej niż kilkaset) opóźnienie czasowe jest nieznaczne. Ale gdy liczba plików w katalogu wzrasta do kilku tysięcy, czas potrzebny na wykonanie listingu może wzrosnąć do minut, godzin, a nawet dni. Problem pogłębia się, jeśli długie nazwy plików są bardzo podobne - różnią się tylko kilkoma ostatnimi znakami.
W przypadku plików nazwanych na podstawie sum kontrolnych SHA1 może to być przepis na katastrofę i fatalną wydajność.
Chociaż powyższe pochodzi z uwagi technicznej z systemu Windows NT 3.5 (i NTFS 1.2 - powszechnie używanego od 1995 r. Do początku 2000 r.), Można to również zauważyć w takich rzeczach, jak EXT3 z implementacjami systemu plików będącego listami połączeń wymagającymi wyszukiwania O (n) . I nawet przy tej zmianie B-drzewa:
Chociaż algorytm HTree znacznie skrócił czas wyszukiwania, może powodować regresję wydajności dla obciążeń wykorzystujących readdir () do wykonywania niektórych operacji wszystkich plików w dużym katalogu.
...
Jedno potencjalne rozwiązanie w celu złagodzenia tego problemu z wydajnością, które zostało zasugerowane przez Daniela Phillipsa i Andreasa Dilgera, ale nie zostało jeszcze wdrożone, polega na tym, że jądro wybiera wolne i-węzły, których numery i-węzłów spełniają właściwość grupującą i-węzły według nazw plików. Daniel i Andreas sugerują przydzielenie i-węzła z zakresu i-węzłów na podstawie wielkości katalogu, a następnie wybranie wolnego i-węzła z tego zakresu na podstawie skrótu nazwy pliku. Teoretycznie powinno to zmniejszyć liczbę przeładowań, które powstają podczas uzyskiwania dostępu do i-węzłów, do których odwołuje się katalog w kolejności readdir. Nie jest jednak jasne, czy ta strategia spowoduje przyspieszenie; w rzeczywistości może to zwiększyć całkowitą liczbę bloków i-węzłów, które mogą wymagać odwołania, a tym samym pogorszyć wydajność obciążeń readdir () + stat (). Wyraźnie,
Nawiasem mówiąc, ten fragment dotyczący poprawy wydajności pochodzi z 2005 roku, tego samego roku, w którym wydano git.
Jak widać w Firefoksie i wielu innych aplikacjach, które mają wiele haszowanych plików buforowanych, projekt dzielenia bufora na bajty. Ma znikomy koszt wydajności, a gdy jest używany na wielu platformach z systemami, które mogą być nieco stare, może równie dobrze stanowić różnicę między działającym programem lub nie.