В индексах NTFS атрибуты сортируются в виде особой разновидности деревьев, а именно В-деревьев. Деревом называется совокупность структур данных, называемых узлами; узлы связываются между собой, начиная с корневого узла. На рис. 11.13 (А) сверху находится узел А, связанный с узлами В и С. В свою очередь, узел В связывается с узлами D и Е. Родительским узлом называется узел, от которого идут связи к другим узлам, а дочерним - тот узел, к которому ведет связь. Например, узел А является родительским по отношению к узлам В и С, а последние являются дочерними по отношению к А. Листом (или листовым узлом) называется узел, не имеющий дочерних узлов. Так, узлы С, D и Е являются листовыми. Дерево, показанное на рисунке, называется бинарным, потому что каждый узел имеет не более двух дочерних узлов.

Древовидные структуры упрощают поиск и сортировку данных. На рис. 11.13 (В) показано то же дерево, что и на рис. 11.13 (А), но в нем каждому узлу присвоено некоторое значение. Если потребовалось найти значение в дереве, сначала мы сравниваем его с корневым узлом. Если корневое значение больше, мы переходим к левому дочернему узлу, а если меньше - к правому. Допустим, потребовалось найти значение 6; мы сравниваем его с корневым значение 7. Корневой узел больше, поэтому мы переходим к левому узлу и сравниваем искомое значение со значением этого узла (5). Значение узла меньше, мы переходим к правому дочернему узлу; его значение равно 6. Таким образом, значение было найдено всего за три сравнения. Например, значение 9 находится всего за 2 сравнения вместо 5, необходимых при хранении значений в списке.

Рис. 11.13. Примеры: (А) - дерево с пятью узлами, (В) - то же дерево после сортировки узлов

В NTFS используются В-деревья, которые напоминают бинарное дерево с рис. 11.13, но в них каждый узел может иметь более двух дочерних узлов. Как правило, количество дочерних узлов зависит от того, сколько значений может храниться в каждом узле. Например, в бинарном дереве в каждом узле хранилось одно значение, поэтому количество допустимых потомков было равно двум. Если бы в каждом узле хранилось пять значений, потомков было бы шесть. Существует много разновидностей В-деревьев и всевозможных правил, которые здесь не будут рассматриваться - ведь этот раздел всего лишь знакомит читателя с основными концепциям В-деревьев, а не описывает процесс их создания.

На рис. 11.14 показано В-дерево, содержащее имена вместо чисел. Узел А содержит три значения и имеет четыре дочерних узла. Скажем, при поиске файла ggg.txt мы обратились бы к корневому узлу и определили, что искомое имя по алфавиту расположено между eee.txt и Ul.txt. Обращаясь к узлу С, мы находим в нем искомое имя файла.

С добавлением и удалением узлов дело обстоит сложнее. Тем не менее это довольно важный момент - он объясняет, почему в NTFS трудно найти имена удаленных файлов. Предположим, что каждый узел вмещает только три имени файлов и в узел добавляется файл jjj.txt. На первый взгляд все просто, но в действительности эта операция приводит к удалению двух и созданию пяти новых узлов. Определив, где должен находится узел jjj.txt, мы увидим, что он должен следовать в конце узла С, за именем iii.txt (рис. 11.15, вверху). К сожалению, это имя станет четвертым, тогда как узел вмещает только три имени. Следовательно, узел С разбивается надвое, имя ggg.txt смещается на один уровень вверх, и в дереве создаются узлы F и G с именами из узла С (рис. 11.15, внизу).

К сожалению, теперь выясняется, что узел А содержит четыре значения. Соответственно, он разбивается надвое, и значение ggg.txt перемещается на уровень выше (рис. 11.16). Добавление одного файла привело к удалению узлов А и С и добавлению узлов F, G, Н, J и J. Все данные, оставшиеся в узлах А и С от ранее удаленных файлов, к этому моменту могут быть утрачены.

Теперь удалим файл zzz.txt. Операция исключает имя из узла Е и не требует других изменений. В зависимости от реализации информация файла zzz.txt может оставаться в узле; возможно, ее удастся восстановить.

Рис. 11.15. Наверху: добавление имени jjj.txt в узел С; внизу: результат удаления узла С (так как каждый узел может содержать только три имени)

Рис. 11.16. Конечное состояние дерева после добавления файла jjj.txt

С удалением файла fff.txt дело обстоит сложнее. Узел Е становится пустым, и его необходимо заполнить. Значение eee.txt перемещается из узла I в узел Р, а значение bbb.txt - из узла В в узел I. Дерево остается сбалансированным, а все листья находятся на одинаковом расстоянии от узла Н (рис. 11.17).

Рис. 11.17. Дерево после удаления файлов zzz.txt и fff.txt

В свободном пространстве узла В находится значение bbb.txt, потому что значение bbb.txt было перемещено в узел I. Программа анализа может показать, что файл bbb.txt был удален, но на самом деле это не так - он просто переместился из-за удаления fff.txt.

Я продемонстрировал процесс добавления и удаления значений из дерева с единственной целью: показать, насколько сложной может оказаться эта процедура. В файловых системах, использующих простые списки имен в каталогах (например, FAT), легко узнать, почему удаленное имя существует (или не существует) в системе. При использовании древовидных структур предсказать конечный результат операции бывает очень трудно.

Индексы | Криминалистический анализ файловых систем | Атрибуты индексов ntfs


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



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

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