Рис. 3. Прием увеличения доступного непрерывного пространства

Во время форматирования раздела HPFS делит его на полосы по 8 Мбайт каждая. Каждая полоса - ее можно представить себе как виртуальный "мини-диск" - имеет отдельную таблицу объемом 2 Кбайт, в которой указывается , какие секторы полосы доступны, а какие заняты. Чтобы максимально увеличить протяженность непрерывного пространства для размещения файлов, таблицы попеременно располагаются в начале и в конце полос (рисунок 3). Этот метод позволяет файлам размером до 16 Мбайт (минус 4 Кбайта, отводимые для размещения таблицы) храниться в одной непрерывной области.

Затем файловая система HPFS оценивает размер каталога и резервирует необходимое пространство в полосе, расположенной ближе всего к середине диска. Сразу же после форматирования объем диска в HPFS кажется меньше, чем в FAT, так как заранее резервируется место для каталогов в центре диска. Место резервируется в середине диска для того, чтобы физические головки, считывающие данные, никогда не проходили более половины ширины диска.

Тот факт, что все пространство заранее распределено, также позволяет HPFS использовать специально оптимизированное программное обеспечение для более быстрой и эффективной работы с каталогами. Сравните это с системой FAT, где головкам требуется пройти весь путь к началу диска и прочитать таблицу размещения файлов, затем найти кластер, вновь пройти к началу диска, чтобы определить в FAT местонахождения следующего кластера, и так далее. Эта процедура становится еще более неудобной по мере нарастания фрагментации. Поэтому ясно, что размещение каталогов в середине диска повышает производительность системы. Вместе с тем, такое предварительное распределение не накладывает ограничений на число файлов, которые могут быть размещены на жестком диске. В редких случаях, когда системе HPFS потребуется больше пространства, чем изначально было отведено под каталоги, она может выделить дополнительное пространство из любой доступной области диска.

Число файлов в каждом блоке каталога - переменная величина, зависящая от длины имен файлов, которые содержатся в нем. Имена файлов в HPFS могут иметь длину до 254 символов, они сортируются в порядке, определяемом последовательностью символов в текущей кодовой странице системы.

Скорость работы увеличивается также благодаря способу хранения элементов каталогов. Система FAT последовательно просматривает каждый элемент каталога, чтобы отыскать нужный файл. Поэтому в самом худшем случае приходится перебирать все файлы в каталоге, прежде, чем найдется нужный. Но HPFS использует для хранения элементов каталогов структуру данных, называемую В-деревом. Каждый элемент каталога начинается с числа, представляющего длину элемента, которая изменяется в зависимости от длины имени файла. Затем следуют время и дата создания файла, его размер и атрибуты (только для чтения, архивный, скрытый и системный), а также указатель на F-узел файла. Каждый файл (и каталог) имеет F-узел - структуру данных, занимающую один сектор и содержащую принципиально важную информацию о файле.

F-узел содержит указатель на начало файла, первые 15 символов имени файла, дополнительные временные маркеры последней записи и последнего доступа, журнал, хранящий информацию о предыдущих обращениях к файлу, структуру распределения, описывающую размещение файла на диске, и первые 300 байт расширенных атрибутов файла. (Расширенные атрибуты редко занимают более 300 байт, что фактически означает, что HPFS для получения этой информации приходится читать на один сектор меньше, чем FAT.) Программы LAN Server и LAN Manager фирмы IBM также сохраняют в F-узле информацию об управлении пользовательским доступом (Access Control). Заметьте, что F-узлы хранятся в смежных с представляемыми ими файлами секторах, поэтому, когда файл открывается, то четыре автоматически считываемых в кэш сектора содержат F-узел и три первых сектора файла.

Структура размещения HPFS имеет дополнительные преимущества по сравнению с FAT благодаря техническому приему, называемому кодированием по длине выполнения (Run Length Encoding, RLE). Вместо того, чтобы определять в таблице каждый используемый сектор, HPFS сохраняет указатель на первый сектор и число последовательно расположенных используемых секторов. Каждая область дискового пространства, описываемая парой (сектор, длина), называется экстентом. Хотя HPFS и сводит фрагментацию к минимуму, файлы все же могут быть в некоторой степени фрагментированными. В таких ситуациях пары, описывающие экстенты, добавляются к F-узлу файла. Один F-узел может хранить до 8 экстентов, обеспечивая достаточное пространство для большинства файлов.

А если все же потребуется еще большее пространство, то HPFS изменяет структуру таким образом, что F-узел становится корнем В+-дерева секторов размещения. В+-дерево является вариантом бинарного В-дерева. Созданное как структура для более быстрого обнаружения данных по сравнению с методом последовательного перебора, бинарное дерево состоит из ветвей, каждая из которых представляет выбор одного из двух возможных продолжений. Короткое дерево территориальных телефонных кодов может выглядеть так, как показано на рисунке 4,а. Здесь левая ветвь соответствует числам с меньшими значениями, чем значение в точке разветвления, а правая - с большими. Пусть выполняется поиск, например, кода 513. Вначале анализируется код в вершине дерева, поскольку 513 больше 212, то дальнейший поиск осуществляется по правой ветви. Так как 513 больше 407, то вновь поиск идет по правой ветви, где и находится нужный элемент данных. Для того, чтобы найти данные с помощью этого метода, потребовалось выполнить только два сравнения, в то время как для последовательного перебора могло бы потребоваться пять сравнений.

Рис. 4. Бинарные древовидные структуры

Эффективность бинарных деревьев зависит от последовательности, в которой в них добавляются новые элементы данных. Если, например, добавить код 617, то он будет следовать за кодом 513, а если добавить еще один код 714, то он последует за кодом 617. Поэтому, если элементы добавляются в порядке возрастания, то результирующее дерево становится все более похожим на последовательную структуру (рис. 4,б).

Структура В-дерева была разработана в целях предотвращения этой проблемы. Методы управления В-деревьями обеспечивают сбалансированность дерева. Структуру на рисунке 4 (б) лучше реорганизовать так, чтобы она приняла вид, показанный на рисунке 4 (в). Это делает дерево более эффективным, но приводит к дополнительным затратам, так как его балансировка выполняется всякий раз при добавлении или удалении элемента, либо при изменении значения элемента.

Возвращаясь к методу описания физической структуры файла, основанному на экстентах, следует учесть, что многие современные контроллеры дисков могут читать за одно обращение сразу несколько секторов. Применяемая в HPFS схема значительно повышает шансы использовать эту возможность, при этом происходит еще большее уменьшение числа требуемых операций взаимодействия между программой, файловой системой, драйвером дискового устройства и физическим диском.