Методы размещения файлов

Реализация директорий

Директория – центральная системная структура в файловой системе, на которой основан поиск файлов. Поэтому эффективная реализация директорий особенно важна.

Наиболее простой метод реализации директорий - линейный список имен с указателями на блоки данных. Такая реализация просто программируется, однако требует большого времени выполнения.

Более эффективный метод реализации - хэш-таблица– линейный список с хэш-оглавлением и подразделением на (небольшие) списки элементов с одним и тем же значением хеш-функции. Такой метод уменьшает время поиска в директории.

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

Смежное размещение.Термин метод размещенияозначает метод, с помощью которого размещаются блоки файла во внешней памяти. Различаются следующие основные методы размещения файлов:

• Смежное размещение
• Ссылочное размещение
• Индексированное размещение.

При смежном размещениикаждый файл занимает набор смежных блоков на диске. Преимущество данного метода - простота: требуется хранить только одну ссылку (номер блока) и длину (число блоков). Другим преимуществом является возможность произвольного доступа.

Недостатки данного метода следующие:

• возможны потери дисковой памяти из-за фрагментации (метод аналогичен общей задаче динамического распределения памяти, рассмотренной ранее);
• невозможность увеличения размера файла.

Смежное размещение файлов иллюстрируется на рис. 20.2.

Рис. 20.2. Смежное размещение файлов.