45437 (664852), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

r₄ r₅ r₆

r₇ r₈

Такой способ организации показан на рис.2.

x

Таблица

Сегментов

Рис.2. Сегменты, состоящие из связных блоков.

Если размер таблицы сегментов невелик, её можно хранить в основной памяти. В противном случае её можно хранить последовательным способом в отдельных блоках. Если нужно найти запись с ключом х, вычисляется h(x) и находится блок таблицы сегментов, содержащий указатель на первый блок сегмента h(x), пока не обнаружится блок, который содержит запись с ключом х. Если исчерпаны все блоки в связном списке для сегмента h(x), приходим к выводу, что х не является ключом ни одной из записей.

Такая структура оказывается вполне эффективной, если в выполняемом операторе указываются значения ключевых полей. Среднее количество обращения к блокам, требующееся для выполнения оператора, в котором указан ключ записи, приблизительно равняется среднему количеству блоков в сегменте, которое равно n/bk, если n – количество записей, блок содержит b записей, а k соответствует количеству сегментов. Таким образом, при такой организации данных операторы, использующие значения ключей, выполняются в среднем в k раз быстрее, чем в случае неорганизованного файла. К сожалению, ускорения операций, не основанных на использовании ключей, добиться не удаётся, поскольку при выполнении подобных операций приходится анализировать практически всё содержимое сегментов. Единственным универсальным способом ускорения операций, не основанных на использовании ключей, по-видимому, является применение вторичных индексов.

Чтобы вставить запись с ключом, значение которого равняется х, нужно сначала проверить, нет ли в файле записи с таким же значением ключа. Если такая запись есть, выдаётся сообщение об ошибке, поскольку мы предполагаем, что ключ уникальным образом идентифицирует каждую запись. Если записи с ключом х нет, мы вставляем новую запись в первый же блок цепочки для сегмента h(x), в которыё эту запись удаётся вставить. Если запись не удаётся вставить ни в какой из существующих блоков сегмента h(x), файловой системе выдаётся команда найти новый блок, в который будет помещена эта запись. Этот новый блок затем добавляется в конец цепочки блоков сегмента h(x).

Чтобы удалить запись с ключом х, нужно сначала найти эту запись, а затем установить её бит удаления. Ещё одной возможной стратегией удаления (которой, впрочем, нельзя пользоваться, если мы имеем дело с закреплёнными записями) является замена удалённой записи на последнюю запись в цепочке блоков сегмента h(x). Если такое изъятие последней записи приводит к опустошению последнего блока в сегменте h(x), этот пустой блок можно затем вернуть файловой системе для повторного использования.

Хорошо продуманная организация файлов с хешированным доступом требует лишь незначительного числа обращений к блокам при выпол6нении каждой операции с файлами. Если мы имеем дело с хорошей функцией хеширования, а количество сегментов приблизительно равно количеству записей в файле, делённому на количество записей, которые могут уместиться в одном блоке, тогда средний сегмент состоит из одного блока. Если не учитывать обращения к блокам, которые требуются для просмотра таблицы сегментов, типичная операция поиска данных, основанного на ключах, потребует лишь одного обращения к блоку, а операции вставки, удаления или изменения потребуют двух обращений к блокам. Если среднее количество записей в сегменте намного превосходит количество записей, которые могут уместиться в одном блоке, можно периодически реорганизовывать таблицу сегментов, удваивая количество сегментов и деля каждый сегмент на две части.

Характеристики

Список файлов реферата