Метод сбалансированных двоичных деревьев

Метод сбалансированных двоичных деревьев

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

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

Действительно, если, например, каталог содержит 4096 файлов, то файловая система FAT потребует чтение в среднем 64 секторов для поиска нужного файла внутри такого каталога, в то время как HPFS осуществит чтение всего только 2-4 секторов (в среднем) и найдет искомый файл. Несложные расчеты позволяют увидеть явные преимущества HPFS над FAT. Так, например, при использовании 40 входов на блок блоки дерева каталогов с двумя уровнями могут содержать 1640 входов, а дерева каталогов с тремя уровнями уже 65 640 входов. Другими словами, некоторый файл может быть найден в типичном каталоге из 65 640 файлов максимум за три обращения. Это намного лучше файловой системы FAT, где в самом плохом случае для нахождения файла нужно прочитать более чем 4000 секторов. Размер каждого из блоков, в терминах которых выделяются каталоги в текущей реализации HPFS, равен 2 Кбайт. Размер записи, описывающей файл, зависит от размера имени файла. Если имя занимает 13 байт (для формата 8.3) то 2-килобай- товый блок вмещает до 40 дескрипторов файлов. Блоки связаны друг с другом посредством списковой структуры (как и дескрипторы экстентов) для облегчения последовательного обхода.

При переименовании файлов может возникнуть так называемая перебалансировка дерева. Фактически, попытка переименования может потерпеть неудачу из-за недостатка дискового пространства, даже если файл непосредственно в размерах не увеличился. Во избежание этого «бедствия» НPFS поддерживает маленький пул свободных блоков, которые могут использоваться при «аварии». Эта операция может потребовать выделения дополнительных блоков на заполненном диске. Указатель на этот пул свободных блоков сохраняется в резервном блоке. Важное значение для повышения скорости работы с файлами имеет снижение их фрагментации. В HPFS считается, что если файл содержит больше одного экстента, он считается фрагментированным. Снижение фрагментации файлов сокращает время позиционирования и время ожидания за счет уменьшения количества перемещений головок, необходимых для доступа к данным файла. Алгоритмы работы файловой системы HPFS функционируют таким образом, чтобы по возможности размещать файлы в последовательных смежных секторах диска, что в последующем обеспечит максимально быстрый доступ к данным. В системе FAT, наоборот, запись следующей порции данных в первый же свободный кластер неизбежно приводит к фрагментации файлов. То есть НPFS записывает данные не в первый попавшийся сектор, а, если это предоставляется возможным, в смежные секторы диска. Это позволяет несколько снизить число перемещений головок чтения/записи от дорожки к дорожке. Когда данные дописываются в существующий файл, HPFS сразу же резервирует как минимум 4 Кбайт непрерывного пространства на диске. Если же часть этого пространства не потребовалась, то после закрыия файла она

высвобождается для дальнейшего использования. Файловая система HPFS равномерно размещает непрерывные файлы по всему диску для того, чтобы впоследствии без фрагментации обеспечить их возможное увеличение. Если же файл не может быть увеличен без нарушения его непрерывности, НPFS опять- таки резервирует 4 Кбайт смежных блоков как можно ближе к основной части файла с целью сократить время позиционирования головок чтения/записи и время поиска соответствующего сектора.

Очевидно, что степень фрагментации файлов на диске зависит как от числа расположенных на нем файлов, их размеров и размеров самого диска, так и от характера и интенсивности самих дисковых операций. Незначительная фрагментация файлов практически не сказываегся на быстродействии операций с файлами. Файлы, состоящие из 2-3 экстентов, практически не снижают производительности HPFS, так как эта файловая система следит за тем. чтобы области данных, принадлежа щие одному и тому же файлу, располагались как можно ближе друг к другу. Файл из трех экстентов имеет только два нарушении непрерывности и следовательно, для его чтения потребуется всего лишь два небольших перемещения головки диска. Программы (утилиты) дефрагментации, имеющиеся для этой файловой системы по умолчанию, считают наличие двух-трех экстентов у файла нормой’. Практика показывает что в среднем па диске имеется не более 2 % файлов, имеющих три и более экстентов |26| Даже общее количество фрагментированных файлов, как правило, не превышает 3 %. Такая ничтожная фрагментация оказывает пренебрежимо малое влияние на общую производительность системы