Каталог на NTFS представляет собой специфический файл, хранящий ссылки на другие файлы и каталоги, создавая иерархическое строение данных на диске. Файл каталога поделен на блоки, каждый из которых содержит имя файла, базовые атрибуты и ссылку на элемент MFT, который уже предоставляет полную информацию об элементе каталога. Внутренняя структура каталога представляет собой бинарное дерево. Для поиска файла с данным именем в линейном каталоге (FAT), операционной системе приходится просматривать все элементы каталога, пока она не найдет нужный. Бинарное же дерево располагает имена файлов таким образом, чтобы поиск файла осуществлялся более быстрым способом - с помощью получения двухзначных ответов на вопросы о положении файла. Определяется в какой группе, относительно данного элемента, находится искомое имя - выше или ниже? Начинается все с среднего элемента, и каждый ответ сужает зону поиска в среднем в два раза. Файлы отсортированы по алфавиту, и ответ на вопрос осуществляется очевидным способом - сравнением начальных букв. Область поиска, суженная в два раза, начинает исследоваться аналогичным образом, начиная опять же со среднего (см. рис.1). Для поиска одного файла среди 1000, например, FAT придется осуществить в среднем 500 сравнений (наиболее вероятно, что файл будет найден на середине поиска), а в системе на основе дерева 12 сравнений (210 = 1024). Но поддержание списка файлов в виде бинарного дерева довольно трудоемко, а FAT в исполнении современной системы (Windows 2000 или Windows 98) уже тоже использовали сходную оптимизацию поиска. Добавление файла в каталог в виде дерева и в линейный каталог - достаточно сравнимые по времени операции. Для того, чтобы добавить файл в каталог, нужно сначала убедится, что файла с таким именем там еще нет, будут трудности с поиском файла, которые с лихвой компенсируют саму простоту добавления файла в каталог. Для выполнения простейшей навигации по диску NTFS не нужно лазить в $MFT за каждым файлом, надо лишь читать самую общую информацию о файлах из файлов каталогов. Главный каталог диска - корневой - ничем не отличается об обычных каталогов, кроме специальной ссылки на него из начала метафайла $MFT (5 запись файла $MFT). см. На рис. 2 - A90D048h - это номер начального сектора корневого каталога. Просматривая каталог, найдем каталожный блок с именем SER.doc (в нем есть номер записи файла $MFT, которая определит экстенты файла SER.doc).
Рис. 1.
Каталог начинается с сигнатуры INDX (см. рис. 2). Каталог состоит из стандартных блоков, которые начинаются с 6-ти байтов содержащих номер записи файла $MFT, которая определяет файл, имя которого содержится в этом блоке (в конце блока).
Первый блок каталога начинается с адреса 58h (рис. 2 :
начало 04 00 00 00 00 00 — это номер записи файла $MFT, конец: с адреса 0AAh расположено имя файла $AttrDef в кодировке Unicode).
просматривая блоки корневого каталога находим блок с именем SER.doc (рис. 3).
Предыдущий блок заканчивается именем IRS, которое не переходит из первых 8-ми байтов текущей строки (на рис. 3), поэтому следующий блок начинается с 8-го байта этой же строки (с адреса 78h) и мы видим в первых 6-ти байтах номер записи файла $MFT, которая определяет нужный нам файл с именем SER.doc:
- 39 00 00 00 00 00 (это номер записи файла $MFT, которая определит экстенты файла SER.doc).
Рис.
2. Начальный сектор корневого каталога
Рис.
3.
Продолжение корневого каталога (см.
блоки с именами IRS и SER.doc)
Версия сайта для слабовидящих