logo
ZH ос 20 вопр 36 стр

19. Структура больших файлов и каталогов в ntfs. Индексация файлов в ntfs.

Здесь мы будем говорить о структуре каталогов NTFS. Каталог в NTFS представляет собой индекс имён файлов, то есть список имён, упорядоченных по любому признаку. В настоящий момент упорядочивание файлов происходит только по имени. Для индексации или упорядочивания используется b+ дерево.

В случае больших каталогов списки файлов располагаются в отрезках. Атрибут корень индекса содержит первый уровень структуры b+ дерева и указывает на индексные буферы, содержащие следующий уровень. То есть в данном случае корень индекса создаёт только несколько имён. Атрибут корень индекса и каждый отрезок, содержащий список файлов, содержащий имя файла, файловую ссылку на запись MFT, метку времени и информацию о размере файла. Эта информация дублируется из соответствующих записей. Дублируется для того, чтобы ускорить просмотр. Атрибут размещения индекса содержит отображение VCN-LCN для индексных буферов.

Битовая карта используется для отслеживания того, какие VCN в индексных буферах заняты, а какие свободны. Каждый индексный буфер размером 2 Кб может содержать около 15 записей для имён файлов. Это 3-4 записи на кластер, размером 512 байт. Рассмотрим пример. Файл f4 – это элемент первого уровня b+ дерева, он указывает на индексный буфер, содержащий имена файлов, которые меньше чем f4 (в смысле символа). Например, мы создали файл с именем f31. Он будет расположен раньше, чем f4.

Хранение имён файлов в виде b+ дерева даёт следующие преимущества:

  1. Поиск в каталоге выполняется быстрее.

  2. Так как b+ дерево имеет тенденцию к росту в ширину, а не в глубину, то скорость поиска не уменьшается с ростом каталогов.

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

Master File Table управляет файлами и так называемыми метаданными в относительной структуре базы данных. Ее легко представить в качестве таблицы. Информация относительно файлов размещена в строки, а атрибуты (скрытый, зашифрованный, сжатый, система, и т.д.) - в столбцы. Для больших файлов MFT содержит указатели о месте их нахождения. То же самое и с папками: достаточно маленькие полностью включены в файловую таблицу. NTFS управляет большими папками с помощью так называемой структуры B-tree, которая индексирует похожие файлы или их названия, что ускоряет последующую обработку.

Каталог в NTFS представляет собой индекс имён файлов, то есть список имён, упорядоченных по любому признаку. В настоящий момент упорядочивание файлов происходит только по имени. Для индеек-ии или упоряд-ия используется b+ дерево.

В случае больших каталогов списки файлов располагаются в отрезках. Атрибут корень индекса содержит первый уровень структуры b+ дерева и указывает на индексные буферы, содержащие следующий уровень. То есть в данном случае корень индекса создаёт только несколько имён. Атрибут корень индекса и каждый отрезок, содержащий список файлов, содержащий имя файла, файловую ссылку на запись MFT, метку времени и информацию о размере файла. Эта информация дублируется из соответствующих записей. Дублируется для того, чтобы ускорить просмотр. Атрибут размещения индекса содержит отображение VCN-LCN для индексных буферов.

Хранение имён файлов в виде b+ дерева даёт следующие преимущества:

  1. Поиск в каталоге выполняется быстрее.

  2. Так как b+ дерево имеет тенденцию к росту в ширину, а не в глубину, то скорость поиска не уменьшается с ростом каталогов.