Составители:
65
дой операции требует, чтобы осуществлялось чтение всего файла. Од-
нако существуют способы организации файлов, позволяющие обращать-
ся к записи, считывая в основную память лишь небольшую часть фай-
ла. Такие способы предусматривают наличие у каждой записи файла
так называемого ключа, т. е. поля (или совокупности полей), которое
уникальным образом идентифицирует каждую запись. К сожалению,
при отсутствии ключей, ускорения операций добиться не удается.
Хеширование – широко распространенный метод обеспечения быст-
рого доступа к информации, хранящейся во внешней памяти. Основная
идея этого метода подобна методу цепочек, который рассматривается в
2.3.2. Только здесь, вместо записей таблицы организуется связный спи-
сок блоков. Заголовок i-го блока содержит указатель на физический
адрес (i+1)-го блока. Записи, хранящиеся в одном блоке, связывать друг
с другом с помощью указателей не требуется. Сама таблица представ-
ляет собой таблицу указателей на блоки.
Такая структура оказывается вполне эффективной, если в выполня-
емой операции указывается значение ключа. В этом случае среднее ко-
личество обращений к блокам равно n/bk, где n – количество запи-
сей; b – количество записей в блоке; k – длина таблицы. Это в среднем
в k раз меньше, чем в случае последовательного файла.
Чтобы вставить запись с ключом (запись с таким ключом отсутству-
ет, так как значение ключа уникально), вычисляется хеш-функция по
ключу, т. е. определяется строка таблицы указателей и просматривается
соответствующая цепочка блоков. Для каждого блока осуществляется
попытка вставки новой записи (при наличии свободного места в бло-
ке). Если не удалось вставить ни в один блок цепочки, то у файловой
системы запрашивается новый блок, который добавляется в конец це-
почки и в него вставляется новая запись.
Чтобы удалить запись, также вычисляется строка таблицы указате-
лей и находится запись в соответствующей цепочке блоков, а затем за-
пись помечается как удаленная. Способы пометки записи здесь те же,
что и в последовательных файлах. Если записи не являются закреплен-
ными, то можно заменять удаляемую запись на последнюю запись в
последнем блоке текущей цепочки. Если в результате такой замены пос-
ледний блок стал пустым, то его можно вернуть файловой системе для
повторного использования.
Еще одним распространенным способом эффективной организации фай-
ла записей, называемым индексированным файлом, является поддержание
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
