на главную | войти | регистрация | DMCA | контакты | справка | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


моя полка | жанры | рекомендуем | рейтинг книг | рейтинг авторов | впечатления | новое | форум | сборники | читалки | авторам | добавить





Индексация

B NTFS каталог — это просто индекс имен файлов, т. е. совокупность имен файлов (с соответствующими файловыми ссылками), организованная таким образом, чтобы обеспечить быстрый доступ. Для создания каталога NTFS индексирует атрибуты «имя файла» из этого каталога. Запись MFT для корневого каталога тома показана на рис. 12–42.

C концептуальной точки зрения, элемент MFT для каталога содержит в своем атрибуте «корень индекса» отсортированный список файлов каталога. Ho для больших каталогов имена файлов на самом деле хранятся в индексных буферах размером по 4 Кб, которые содержат и структурируют имена файлов. Индексные буферы реализуют структуру данных типа «b+ tree», которая позволяет свести к минимуму число обращений к диску при поиске какого-либо файла, особенно в больших каталогах. Атрибут «корень индекса» содержит первый уровень структуры b+ tree (подкаталоги корневого каталога) и указывает на индексные буферы, содержащие следующий уровень (другие подкаталоги или файлы).

4.Внутреннее устройство Windows (гл. 12-14)

Ha рис. 12–42 в атрибуте «корень индекса» и индексных буферах показаны только имена файлов (например, файл 6), но каждая запись индекса содержит и файловую ссылку на запись MFT, описывающую данный файл, плюс метку времени и информацию о размере файла. NTFS дублирует метку времени и информацию о размере файла из записи MFT для файла. Такой подход, используемый файловыми системами FAT и NTFS, требует записи обновленной информации в два места. Ho даже при этом просмотр каталогов существенно ускоряется, поскольку файловая система может сообщать метки времени и размеры файлов, не открывая каждый файл в каталоге.

Атрибут «выделенная группа индексов» сопоставляет VCN групп индексных буферов с LCN, которые указывают, в каком месте диска находятся индексные буферы, а битовая карта используется для учета того, какие VCN в индексных буферах заняты, а какие свободны. Ha рис. 12–42 на каждый VCN, т. е. на каждый кластер, приходится по одной записи для файла, но на самом деле кластер содержит несколько записей. Каждый индексный буфер размером 4 Кб может содержать 20–30 записей для имен файлов.

Структура данных b+ tree — это разновидность сбалансированного дерева, идеальная для организации отсортированных данных, хранящихся на диске, так как позволяет минимизировать количество обращений к диску при поиске заданного элемента. B MFT атрибут корня индекса для каталога содержит несколько имен файлов, выступающих в качестве индексов для второго уровня b+ tree. C каждым именем файла в атрибуте корня индекса связан необязательный указатель индексного буфера. Этот индексный буфер содержит имена файлов, которые с точки зрения лексикографии меньше данного имени. Например, на рис. 12–42 файл 4 — это элемент первого уровня b+ tree. Он указывает на индексный буфер, содержащий имена файлов, которые лексикографически меньше имени в этом элементе, — файл 0, файл 1 и файл 3. Обратите внимание, что использованные в этом примере имена (файл1, файл2 и др.) не являются буквальными, — они просто иллюстрируют относительное размещение файлов, лексикографически упорядоченных в соответствии с показанной последовательностью.

Хранение имен файлов в структурах вида b+ tree дает несколько преимуществ. Поиск в каталоге выполняется быстрее, так как имена файлов хранятся в отсортированном порядке. A когда высокоуровневое программное обеспечение перечисляет файлы в каталоге, NTFS возвращает уже отсортированные имена. Наконец, поскольку b+ tree имеет тенденцию к росту в ширину, а не в глубину, скорость поиска не уменьшается с увеличением размера каталога.

Кроме индексации имен, NTFS обеспечивает универсальную индексацию данных, и некоторая функциональность NTFS (в том числе идентификации объектов, отслеживания квот и консолидированной защиты) использует индексацию для управления внутренними данными.



Файл журнала изменений | 4.Внутреннее устройство Windows (гл. 12-14) | Идентификаторы объектов