Универсальная индексация
Некоторые новые свойства NTFS5 основываются на фундаментальной особенности NTFS, именуемой индексацией атрибутов (attribute indexing). Индексация атрибутов заключается в сортировке элементов с атрибутом определенного типа при помощи эффективного механизма хранения, обеспечивающего быстрый просмотр. В версиях NTFS, предшествовавших Windows 2000, индексация допускалась только для индексного атрибута $I30, в котором хранятся элементы каталога. В процессе индексации атрибутов элементы каталога сортируются по имени и сохраняются в B+ дереве (форма двоичного дерева, в каждом узле которого хранится несколько элементов). На Рисунке 1 показана запись MFT каталога, в трех узлах которой содержится девять элементов, по три в каждом узле. Корень B+ дерева находится в атрибуте index root (корень индекса). В записи MFT каталога девять элементов не умещается, поэтому некоторые элементы приходится хранить в другом месте. Для этого NTFS выделяет два буфера размещения индексов (index allocation) для хранения двух записей (как правило, корень индекса и буферы размещения индексов мо-гут хранить элементы для более чем трех файлов, в зависимости от длины имен). Размер записи MFT - 1 Кбайт, а размер буферов размещения индексов - 4 Кбайт.
Красные стрелки указывают, что элементы NTFS хранятся в алфавитном порядке. Если запустить программу, которая открывает файл e.bak в показанном на рисунке каталоге, то NTFS читает атрибут индексного корня, содержащий элементы для d.new, h.txt и i.doc, и сравнивает строку e.bak с именем первого элемента, d.new. NTFS делает вывод, что алфавитный номер e.bak больше, чем d.new, и переходит к следующему элементу - h.txt. Повторив операцию сравнения, NTFS выясняет, что алфавитный номер e.bak меньше, чем h.txt. Затем NTFS отыскивает в записи каталога h.txt номер виртуального кластера (virtual cluster number, VCN) индексного буфера, содержащего элементы каталога, алфавитные номера которых меньше, чем h.txt, но больше, чем d.new. VCN представляет собой порядковый номер кластера в файле или каталоге. На основании информации о размещении кластеров NTFS преобразует VCN в логический номер кластера (Logical Cluster Number, LCN), т. е. номер кластера относительно начала тома. Если элемент каталога для h.txt не содержит VCN индексного буфера, NTFS делает вывод, что каталог h.txt не содержит файла e.bak и сообщает о неудачном завершении поиска.
Получив VCN начального кластера индексного буфера, NTFS читает буфер размещения индексов и просматривает его в поисках совпадений. На Рисунке 1 первый же элемент индексного буфера совпадает с критерием поиска, и NTFS читает номер записи MFT e.bak из элемента каталога e.bak. В элементах каталога хранится и другая информация: в частности, временные отметки (например, время создания и последнего изменения), размер и атрибуты. NTFS хранит эту информацию и в записи MFT файла, но, благодаря дублированию информации в элементе каталога, читать запись MFT файла при составлении списков каталогов и выполнении простых файловых запросов не требуется.
Элементы каталогов сортируются по алфавиту, и именно поэтому в списках каталогов NTFS файлы всегда располагаются в алфавитном порядке. В отличие от NTFS, FAT не сортирует каталог, поэтому списки FAT не сортированы. Кроме того, поскольку элементы NTFS хранятся в B+ дереве, механизм поиска конкретных файлов в больших каталогах очень эффективен; обычно достаточно просмотреть лишь часть каталога. Данный подход отличается от линейного метода FAT, при использовании которого для поиска одного имени иногда приходится просматривать весь каталог.
В версиях NTFS, предшествовавших Windows 2000, индексировались только имена файлов, но NTFS5 обеспечивает универсальную индексацию, сохраняя в индексах произвольные данные и сортируя элементы данных не по имени, а по другим параметрам. Универсальная индексация используется для управления дескрипторами безопасности, информацией о квотах, точках повторной обработки и идентификаторах файловых объектов, т. е. элементами NTFS5, о которых идет речь в данной статье.
