3.3 Индексация имен файлов
Каталог в NTFS — это просто индекс имен файлов, т. е. набор их имен (с соответствующими файловыми ссылками), организованный особым способом для ускорения доступа. Для создания каталога NTFS индексирует атрибуты-имена файлов из этого каталога. Запись MFT для корневого каталога тома показана на рис. 3-12.
Концептуально запись MFT для каталога содержит в своем атрибуте корня индекса отсортированный список файлов каталога. Однако для больших каталогов имена файлов на самом деле хранятся в индексных буферах — отрезках размером 2 Кбайт или равных размеру кластера (в зависимости от того, что больше). Индексные буферы реализуют структуру данных Ь+ дерево (b+ tree), что минимизирует количество обращений к диску при поиске данного файла, особенно в случае больших каталогов. Атрибут корня индекса содержит первый уровень структуры Ь+ дерево и указывает на индексные буферы, содержащие следующий уровень. Атрибут размещения индекса отображает VCN отрезков индексных буферов в LCN, которые указывают местоположение индексных буферов на диске.
На рис. 3-12 в атрибуте корня индекса и в индексных буферах показаны только имена файлов (например^/еб), но каждая запись индекса содержит также файловую ссылку на запись MFT, описывающую данный файл, плюс отметку времени и информацию о размере файла. NTFS копирует отметку времени и размер из записи MFT для файла. Такой подход, используемый файловыми системами FAT, HPFS и NTFS, требует записи обновленной информации в два места. Однако при этом существенно ускоряется просмотр каталогов, поскольку файловая система может отобразить временные отметки и размеры файлов, не открывая каждый файл каталога.
Рис. 3-12. Индекс имен файлов для корневого каталога тома.
Атрибут размещения индексов содержит отображение VCN-LCN для индексных буферов, а битовая карта используется для отслеживания того, какие VCN в индексных буферах заняты, а какие свободны. На рис. 3-12 на каждый VCN, т.е. на каждый кластер, приходится по одной записи для файла, но на самом деле кластер содержит несколько записей. Каждый индексный буфер размером
2 Кбайт может содержать около 15 записей для имен файлов (3 или 4 на кластер в случае 512-байтового кластера).
Структура данных Ь+ дерево (она используется и в HPFS) — это разновидность сбалансированного дерева, идеальная для организации сортированных данных, хранящихся на диске, так как позволяет минимизировать количество обращений к диску при поиске заданного элемента. В MFT атрибут корня индекса для каталога содержит несколько имен файлов, выступающих в качестве индексов для второго уровня Ь+ дерева. С каждым именем файла в атрибуте корня индекса связан необязательный указатель индексного буфера. Этот индексный буфер содержит имена файлов, которые меньше данного имени с точки зрения лексикографии. Например, на рис. 3-12 file4 — это элемент первого уровня Ь+ дерева. Он указывает на индексный буфер, содержащий имена файлов, которые меньше (лексикографически), чем имя в этом элементе — ftleO,filel nflle3.
Хранение имен файлов в виде Ь+ дерева дает несколько преимуществ. Поиск в каталоге выполняется быстрее, так как имена файлов хранятся в отсортированном порядке. И когда программное обеспечение более высокого уровня перечисляет файлы в каталоге, NTFS возвращает уже отсортированные имена. Наконец, поскольку Ь+ дерево имеет тенденцию к росту в ширину, а не в глубину, то скорость поиска не уменьшается с ростом размера каталога.
В настоящее время NTFS индексирует только атрибуты-имена файлов, но новые версии этой файловой системы могут позволить приложениям как вводить новые атрибуты, так и индексировать их. Например, если в качестве атрибута добавить имя автора, то NTFS могла бы поддерживать Ь+ деревья файлов, упорядоченные по именам авторов.