3.2.14.1 Примеры реализации директорий в некоторых ос
Директории в ОС CP/M
В ОС CP/M только одна директория.
Каждая запись - строка содержит следующие поля: идентификатор собственника, имя файла, тип файла, поле extent, которое показывает, хватит ли для идентификации файла одной строки или нужны еще, число блоков, номера блоков. То есть адреса всех блоков файла перечислены в записи в директории!
Директории в ОС MS-DOS
В ОС MS-DOS типовая запись в директории имеет вид:
Рис. 3.2.11 Вариант записи в директории MS-DOS
В ОС MS-DOS, как и в большинстве современных ОС, директории могут содержать поддиректории (специфицируемые битом атрибута), что позволяет конструировать произвольное дерево директорий файловой системы.
Номер первого блока используется в качестве индекса в таблице FAT . Далее по цепочке могут быть найдены остальные блоки.
Директории в ОС Unix
Структура директории проста. Каждая запись содержит имя файла и номер его индексного узла. Вся остальная информация о файле (тип, размер, времен модификации, владелец и т. д. и номера дисковых блоков) находится в индексном узле.
Рис. 3.2.12. Вариант записи в директории Unix
3.2.14.2 Поиск в директории
Итак, директория - есть файл, имеющий специальный формат, состоящий из записей фиксированной длины, где каждая запись соответствует одному из обычных файлов или директорий, входящих в состав данной директории. Как правило, список файлов в директории оказывается не упорядоченным по именам файлов. Поэтому правильный выбор алгоритма поиска имени файла в директории имеет большое влияние на эффективность и надежность файловых систем.
Линейный поиск
Совокупность записей о файлах в директории является линейным списком символьных имен файлов. Существует несколько стратегий просмотра такого списка. Простейшей из них является линейный поиск. Директория просматривается с самого начала, пока не встретится нужное имя файла. Хотя это наименее эффективный способ поиска, оказывается, что в большинстве случаев он работает с приемлемой производительностью. Например, авторы Unix утверждали, что вполне достаточно линейного поиска. По-видимому, это связано с тем, что на фоне относительно медленного доступа к диску, некоторые задержки, возникающие в процессе сканирования списка несущественны.
Метод прост, но требует временных затрат. Для создания нового файла вначале нужно просканировать директорию на наличие такого же имени. Затем, имя нового файла вставляется в конец директории (если, разумеется, файл с таким же именем в директории не существует, в противном случае нужно информировать пользователя). Для удаления файла нужно также выполнить поиск его имени в списке и пометить запись как неиспользуемую.
Реальный недостаток данного метода - линейный поиск файла. Информация о структуре директории используется часто, и плохая реализация будет замечена пользователями. Можно свести поиск к бинарному, если отсортировать список файлов. Однако это усложнит создание и удаление файлов, так как требуется перемещения большого объема информации.
Хеш таблица
Хеширование (см. например, [13]) - другой способ, который может быть использован для размещения и последующего поиска имени файла в директории. В данном методе имена файлов также хранятся в каталоге в виде линейного списка, но дополнительно используются хеш таблица. Хеш таблица, точнее построенная на ее основе хеш-функция позволяет по имени файла получить указатель на имя файла в списке. Таким образом, можно существенно уменьшить время поиска.
В результате хеширования могут возникать коллизии, то есть ситуации, когда функция хеширования, примененная к разным именам файлов, дает один и тот же результат. Обычно имена таких файлов объединяют в связные списки, предполагая в дальнейшем осуществление в них последовательного поиска нужного имени файла. Выбор хорошего алгоритма хеширования позволяет свести к минимуму число коллизий. Однако всегда есть вероятность неблагоприятного исхода, когда непропорционально большому числу имен файлов функция хеширования ставит в соответствие один и тот же результат. В этом случае преимущество использования этой схемы по сравнению с последовательным поиском практически утрачиваются.
Другие методы поиска
Помимо описанных методов поиска имени файла в директории существуют и другие. В качестве примера можно привести организацию поиска в каталогах файловой системы NTFS при помощи, так называемого B-дерева, которое стало стандартным способом организации индексов в системах баз данных.