Битовая карта.

Индексация имён файлов.

Лекция.

Обычно нерезидентным является содержимое файла и дескриптор защиты. Рассмотрим.

VCN 0 1 2 3

LCN 1355 1356 1357 1358

Данные VCN 4 5 6 7

LCN 1588 1589 1590

Данные

Здесь мы будем говорить о структуре каталогов NTFS. Каталог в NTFS представляет собой индекс имён файлов, то есть список имён, упорядоченных по любому признаку. В настоящий момент упорядочивание файлов происходит только по имени. Для индексации или упорядочивания используется b+ дерево.

Стандартная Имя Корень Размещение Битовая

информация индекса индекса карта

0 1 2 3

8 9 10 11

4 5 6 7

В случае больших каталогов списки файлов располагаются в отрезках. Атрибут корень индекса содержит первый уровень структуры b+ дерева и указывает на индексные буферы, содержащие следующий уровень. То есть в данном случае корень индекса создаёт только несколько имён. Атрибут корень индекса и каждый отрезок, содержащий список файлов, содержащий имя файла, файловую ссылку на запись MFT, метку времени и информацию о размере файла. Эта информация дублируется из соответствующих записей. Дублируется для того, чтобы ускорить просмотр. Атрибут размещения индекса содержит отображение VCN-LCN для индексных буферов.

Используется для отслеживания того, какие VCN в индексных буферах заняты, а какие свободны. Каждый индексный буфер размером 2 Кб может содержать около 15 записей для имён файлов. Это 3-4 записи на кластер, размером 512 байт. Рассмторим пример. Файл f4 – это элемент первого уровня b+ дерева, он указывает на индексный буфер, содержащий имена файлов, которые меньше чем f4 (в смысле символа). Например, мы создали файл с именем f31. Он будет расположен раньше, чем f4.

Хранение имён файлов в виде b+ дерева даёт следующие преимущества:

1. Поиск в каталоге выполняется быстрее.

2. Так как b+ дерево имеет тенденцию к росту в ширину, а не в глубину, то скорость поиска не уменьшается с ростом каталогов.