Каталоги. Файл – это, прежде всего, обязательный элемент - запись в MFT

Файлы и потоки

Файл – это, прежде всего, обязательный элемент - запись в MFT. В этом месте хранится вся информация о файле, за исключением собственно данных. Имя файла, размер, положение на диске отдельных фрагментов, и т.д. Если для информации не хватает одной записи MFT, то используются несколько, причем не обязательно подряд.

Дополнительный (возможно, отсутствующий) элемент - потоки данных файла. Файл может не иметь данных - в таком случае на него не расходуется свободное место самого диска. Файл может иметь не очень большой размер. Тогда данные файла хранятся прямо в MFT, в оставшемся от основных данных месте в пределах одной записи MFT.

Каждый файл в NTFS, вообще говоря, не имеет данных как таковых, а имеет потоки (streams). Один из потоков - данные файла. Но большинство атрибутов файла - тоже потоки! Таким образом, получается, что базовая сущность у файла только одна - номер в MFT, а всё остальное опционально.

Такой подход может использоваться для создания довольно удобных вещей - например, файлу можно "прилепить" еще один поток, записав в него любые данные - например, информацию об авторе и содержании файла, как это сделано в Windows 2000 (самая правая закладка в свойствах файла, просматриваемых из проводника). Интересно, что эти дополнительные потоки не видны стандартными средствами, поэтому наблюдаемый размер файла - это лишь размер основного потока, содержащего традиционные данные. Можно, к примеру, иметь файл нулевой длины, при стирании которого освободится 1 Гбайт свободного места - просто потому, что какая-нибудь хитрая программа или технология прилепила к нему дополнительный поток (альтернативные данные) гигабайтового размера.

Имя файла может содержать любые символы, включая полый набор национальных алфавитов, так как данные представлены в Unicode - 16-битном представлении, которое дает 65535 разных символов. Максимальная длина имени файла - 255 символов.

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

Внутренняя структура каталога в NTFS представляет собой В-дерево.

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

Вывод - для поиска одного файла среди 1000, например, FAT16 придется осуществить в среднем 500 (половина от длины каталога) сравнений, а системе на основе дерева - всего 11 (2^10 = 1024). Экономия времени поиска налицо.

Не стоит, однако думать, что в традиционных системах (FAT) всё так запущено: во-первых, поддержание списка файлов в виде бинарного дерева довольно трудоемко, а во-вторых - даже FAT32 в исполнении современной системы (Windows2000 или Windows98) использует сходную оптимизацию поиска. Хочется также развеять распространенное заблуждение о том, что добавлять файл в каталог в виде дерева труднее, чем в линейный каталог: Это достаточно сравнимые по времени операции. Дело в том, что для того, чтобы добавить файл в каталог, нужно сначала убедится, что файла с таким именем там еще нет. Тут-то в линейной системе у нас будут трудности с поиском файла, описанные выше, которые с лихвой компенсируют саму простоту добавления файла в каталог.

В NTFS используется структура В-дерева, оптимизированная для работы с медленными внешними запоминающими устройствами. Поскольку время доступа к диску происходит медленнее по сравнению со временем доступа к оперативной памяти примерно в 100000 раз (!), то хотелось бы за одно чтение с диска прочесть максимальное количество нужной информации. Таким образом, за одно чтение с диска нам надо отнести имя не к одной из двух групп, а к одной из K групп. Как это сделать? Хранить в узле дерева не одно ключевое значение, а несколько. Например, если мы храним в узле дерева 4 значения, то искомое может либо совпасть с одним из них (это - совсем хорошо). Либо мы можем проверить, к какому интервалу искомое значение относится: «меньше первого значения», «больше первого, но меньше второго», «больше второго, но меньше третьего», «больше третьего, но меньше четвертого», «больше четвертого». При применении такой структуры количество возможных обращений к диску вычисляется как log по основанию K от количества записей каталога. В нашем примере для расчета K требуется определить, сколько записей каталога уместятся в блок, читаемый за одно аппаратное обращение к диску. Предположим, что размер кластера равен 4 Кб, а размер записи каталога 400 байт (это близко к правде). Тогда K=10. Таким образом, для поиска файла по каталогу из 1000 записей нам потребуется не более log₁₀1000=3 чтений.

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

Дата добавления: 2014-12-07