1. B+-drzewa w NTFS

Jak już było wspomniane, atrybuty Index root, Index allocation i Bitmap dla danego katalogu pamiętają pliki i podkatalogi w nim zawarte. Opiszemy je pokrótce (są one istotną optymalizacją):

  1. Index root - Jeżeli jest ich na tyle mało, żeby atrybut ten mógł być rezydentny, to jest pamiętana po prostu ich lista posortowana leksykograficznie po nazwach (pliki pamiętane są za pomocą nazwy, wielkości, stempla czasowego i położenia w tablicy MFT; redundancja stempla czasowego ma cele optymalizacyjne - wyświetlenie stempli czasowych wszystkich plików w katalogu nie wymaga odczytu wszystkich plików z dysku!). Jeżeli atrybut jest nierezydentny, to pliki i podkatalogi są utrzymywane w czterokilobajtowych buforach indeksowych (jak już wspomniane, jest to inna nazwa ekstentów dla tego przypadku). Bufory indeksowe implementują strukturę zwaną B+-drzewem, która stosunkowo minimalizuje liczbę dostępów do dysku, koniecznych do dostępu do danego pliku.

  2. Index allocation - mapowanie między numerami VCN buforów indeksowych a ich numerami LCN.

  3. Bitmap - pamięta, które VCN-y odpowiadają zajętym, a które wolnym buforom indeksowym.

    Figure 7.1. Katalog jako B+-drzewo

    Katalog jako B+-drzewo

    Wykorzystanie B+-drzew, które jak wiadomo z algorytmiki rosną bardziej na szerokość niż na głębokość, pozwala bardzo silnie zoptymalizować wyszukiwanie plików spełniających dane kryteria i wyszukiwanie pliku w katalogu przy posiadaniu jego nazwy nawet w przypadku katalogów z bardzo dużą zawartością. Dlatego też tego typu struktury są używane w NTFS-ie także w innych celach (patrz np. sekcja o pliku $Secure file), ale także szeroko w innych popularnych Linuksowych systemach plików, takich jak: ReiserFS, XFS czy JFS.