Файловая система NTFS



         

Каталоги


Каталог на NTFS представляет собойспецифический файл, хранящий ссылки надругие файлы и каталоги, создаваяиерархическое строение данных на диске.Файл каталога поделен на блоки, каждый изкоторых содержит имя файла, базовыеатрибуты и ссылку на элемент MFT, который ужепредоставляет полную информацию обэлементе каталога. Внутренняя структуракаталога представляет собой бинарноедерево. Вот что это означает: для поискафайла с данным именем в линейном каталоге,таком, например, как у FAT-а, операционнойсистеме приходится просматривать всеэлементы каталога, пока она не найдетнужный. Бинарное же дерево располагаетимена файлов таким образом, чтобы поискфайла осуществлялся более быстрым способом- с помощью получения двухзначных ответовна вопросы о положении файла. Вопрос, накоторый бинарное дерево способно датьответ, таков: в какой группе, относительноданного элемента, находится искомое имя -выше или ниже? Мы начинаем с такого вопросак среднему элементу, и каждый ответ сужаетзону поиска в среднем в два раза. Файлы,скажем, просто отсортированы по алфавиту, иответ на вопрос осуществляется очевиднымспособом - сравнением начальных букв.Область поиска, суженная в два раза,начинает исследоваться аналогичнымобразом, начиная опять же со среднегоэлемента.

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

:)
- и вот тут-то влинейной системе у нас будут трудности споиском файла, описанные выше, которые слихвой компенсируют саму простотудобавления файла в каталог.

Какую информацию можно получить, простопрочитав файл каталога? Ровно то, что выдаеткоманда dir. Для выполнения простейшейнавигации по диску не нужно лазить в MFT закаждым файлом, надо лишь читать самую общуюинформацию о файлах из файлов каталогов.Главный каталог диска - корневой - ничем неотличается об обычных каталогов, кромеспециальной ссылки на него из началаметафайла MFT.




Содержание  Назад  Вперед