Файловая система NTFS
Каталоги
Каталог на NTFS представляет собойспецифический файл, хранящий ссылки надругие файлы и каталоги, создаваяиерархическое строение данных на диске.Файл каталога поделен на блоки, каждый изкоторых содержит имя файла, базовыеатрибуты и ссылку на элемент MFT, который ужепредоставляет полную информацию обэлементе каталога. Внутренняя структуракаталога представляет собой бинарноедерево. Вот что это означает: для поискафайла с данным именем в линейном каталоге,таком, например, как у FAT-а, операционнойсистеме приходится просматривать всеэлементы каталога, пока она не найдетнужный. Бинарное же дерево располагаетимена файлов таким образом, чтобы поискфайла осуществлялся более быстрым способом- с помощью получения двухзначных ответовна вопросы о положении файла. Вопрос, накоторый бинарное дерево способно датьответ, таков: в какой группе, относительноданного элемента, находится искомое имя -выше или ниже? Мы начинаем с такого вопросак среднему элементу, и каждый ответ сужаетзону поиска в среднем в два раза. Файлы,скажем, просто отсортированы по алфавиту, иответ на вопрос осуществляется очевиднымспособом - сравнением начальных букв.Область поиска, суженная в два раза,начинает исследоваться аналогичнымобразом, начиная опять же со среднегоэлемента.
Вывод - для поиска одного файла среди 1000,например, FAT придется осуществить в среднем500 сравнений (наиболее вероятно, что файлбудет найден на середине поиска), а системена основе дерева - всего около 10-ти (2^10 = 1024).Экономия времени поиска налицо. Не стоит,однако думать, что в традиционных системах(FAT) всё так запущено: во-первых, поддержаниесписка файлов в виде бинарного деревадовольно трудоемко, а во-вторых - даже FAT висполнении современной системы (Windows2000 илиWindows98) использует сходную оптимизациюпоиска. Это просто еще один факт в вашукопилку знаний. Хочется также развеятьраспространенное заблуждение (которое ясам разделял совсем еще недавно) о том, чтодобавлять файл в каталог в виде дереватруднее, чем в линейный каталог: этодостаточно сравнимые по времени операции -дело в том, что для того, чтобы добавить файлв каталог, нужно сначала убедится, что файлас таким именем там еще нет
Какую информацию можно получить, простопрочитав файл каталога? Ровно то, что выдаеткоманда dir. Для выполнения простейшейнавигации по диску не нужно лазить в MFT закаждым файлом, надо лишь читать самую общуюинформацию о файлах из файлов каталогов.Главный каталог диска - корневой - ничем неотличается об обычных каталогов, кромеспециальной ссылки на него из началаметафайла MFT.
