Итак, мы рассмотрели общую концепцию В-деревьев; теперь нужно разобраться, как они реализуются в NTFS при построении индексов. Для каждого элемента данных в дереве создается структура данных, называемая индексным элементом и предназначенная для хранения значений каждого узла. Существует много типов индексных элементов, но они всегда содержат одинаковый набор полей заголовка (см. главу 13). Например, индексный элемент каталога содержит несколько заголовочных полей и атрибут $FILE_NAME. Индексные элементы объединяются в древовидную структуру и хранятся в виде списка. Пустой элемент обозначает конец списка. На рис. 11.18 показан пример узла в индексе каталога, содержащего четыре индексных элемента $FILE_NAME.

Для хранения индексных узлов могут использоваться два типа атрибутов записей MFT. Атрибут $INDEX_R00T всегда является резидентным и содержит только один узел с небольшим числом индексных элементов. Атрибут $INDEX_R00T всегда соответствует корневому узлу индексного дерева.

Рис. 11.18. Узел индексного дерева каталога NTFS с четырьмя индексными элементами

В больших индексах создаются нерезидентные атрибуты $INDEX_ALLOCATION, которые не ограничиваются по количеству узлов. Содержимое этого атрибута представляет собой большой буфер с одной или несколькими индексными записями. Индексная запись имеет статический размер (обычно 4096 байт) и содержит список индексных элементов. Каждой индексной записи присваивается адрес, начиная с 0. На рис. 11.19 показан атрибут $INDEX_R00T с тремя индексными элементами и нерезидентным атрибутом $INDEX_ALL0CATI0N; последнему был выделен кластер 713, и он использует три индексные записи.

Рис. 11.19. Каталог содержит три индексных элемента в резидентном атрибуте $INDEX_ROOT и три индексные записи в нерезидентном атрибуте $INDEX_ALLOCATION

Атрибуту $INDEX_ALL0CATI0N может выделяться пространство, не используемое для хранения индексных записей. Атрибут $В1ТМАР управляет состоянием выделения индексных записей. Если в дереве потребуется создать новый узел, $ BITMAP используется для поиска свободных индексных записей; если найти запись не удалось, добавляется новое пространство. Каждому индексу присваивается имя; это же имя должно присутствовать в заголовке атрибутов $INDEX_R00T, $INDEX_ALL0CATI0N и $В1ТМАР.

Каждый индексный элемент обладает флагом, который показывает, имеет ли он дочерние узлы. Если такие узлы имеются, адреса их индексных записей указываются в индексном элементе. Индексные элементы узла хранятся в отсортированном порядке, и если искомое значение меньше значения индексного элемента, а у последнего есть дочерний узел, вы обращаетесь к дочернему узлу. Добравшись до пустого элемента в конце списка, вы обращаетесь к его дочернему узлу.

Давайте рассмотрим несколько примеров. Для начала возьмем индекс с тремя элементами, помещающимися в $INDEX_R00T. В этом случае память выделяется только для атрибута $INDEX_R00T, который содержит три структуры данных индексных элементов и пустой элемент в конце списка (рис. 11.20 (А). Следующий индекс содержит 15 элементов, которые не помещаются в $INDEX_R00T, но помещаются в атрибут $INDEX_ALL0CATI0N с одной индексной записью (рис. 11.20 (В)). После заполнения всех индексных элементов в индексной записи добавляется новый уровень, в результате создается дерево из трех узлов (рис. 11.20 (С)). Оно содержит одно значение в корневом узле и имеет два дочерних узла. Каждый дочерний узел находится в отдельной индексной записи одного атрибута $IN DEX_ALL0CA-TI0N, а ссылки на него содержатся в элементах узла $INDEX_R00T.

Рис. 11.20. Три сценария в индексах NTFS: (А) - небольшой индекс с тремя элементами, (В) ■ индекс с двумя узлами и 15 записями, (С) - дерево из трех узлов с 25 элементами

В-деревья | Криминалистический анализ файловых систем | Программы анализа


Криминалистический анализ файловых систем



Новости за месяц

  • Май
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс