Несвязанная область переполнения

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

Преимущества.
1. Высокая эффективность операций вставки
2. Нефиксированный размер БД
3. Высокая эффективность операций поиска и удаления в случае небольшого количества конфликтов (при малом количестве записей в области переполнения, которая представляет собой неупорядоченный последовательный файл со всеми его преимуществами и недостатками).

Недостаток.
Большая потеря производительности в случае большого количества конфликтов, количество которых увеличивается по мере заполнения БД.

СВЯЗАННАЯ ОБЛАСТЬ ПЕРЕПОЛНЕНИЯ

Для разрешения конфликтов используется область переполнения. Однако все сегменты содержат дополнительное поле указатель синонима, которое указывает страницу в области переполнения, использованную для разрешения конфликта. Если указатель равен нулю, конфликта нет.

Преимущества.
1. Высокая эффективность операций вставки, удаления, поиска по сравнению с предыдущими методами. Самой трудоемкой является операция вставки, для которой иногда потребуется найти свободный сегмент в области переполнения, однако в среднем она также выполняется более эффективно, чем в предыдущих методах.
2. Нефиксированный размер БД

Недостаток.
Потери на хранение дополнительных служебных данных – указателя синонима, которые, однако, относительно невелики.

МНОГОКРАТНОЕ ХЕШИРОВАНИЕ

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

ДИНАМИЧЕСКОЕ ХЕШИРОВАНИЕ

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

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

Рассмотрим кратко один тип динамического хеширования, который называется расширяемым хешированием. Вначале записи добавляются только в первый сегмент, и так продолжается до тех пор, пока он не будет полностью заполнен. В этот момент сегмент расщепляется на 2i новых сегментов, где 0 < i < n (обычно i=1, то есть сегмент разбивается на 2 новых сегмента). Адреса сегментов хранятся в каталоге – таблице адресов сегмента. Адрес сегмента, предназначенного для хранения данных со значением хеш-функции равном P, находится в k-ой ячейке каталога, где k – десятичное число, соответствующее двоичному числу, полученному из старших i бит двоичного числа P. После расщепления сегментов ранее хранимые данные перераспределяются по новым сегментам.

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

Если в результате удаления записей сегмент опустошается, он может быть удален вместе с его указателем в каталоге. В некоторых схемах возможно слияние малых сегментов и уменьшение вдвое размера самого каталога.

Лекция 14

ИНДЕКСИРОВАННЫЕ ФАЙЛЫ

Индекс – это структура данных, связанная с файлом БД, и предназначенная для повышения скорости поиска отдельных записей в файле, в соответствии с чем сокращается время выполнения запросов пользователей на поиск, модификацию и удаление записей.

Индекс аналогичен по своей структуре и назначению предметному указателю, приведенному в конце книги. Как и предметный указатель книги, индекс базы данных упорядочен, и каждый элемент индекса содержит признак искомого объекта (поле индексирования), а также один или несколько указателей на место его расположения. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, — индексным файлом.

В отличие от хеширования:
а) индексирование не требует физической упорядоченности записей в файле данных (при индексировании индексный файл «подгоняется» под файл данных, а при хешировании – файл данных под значения хеш - функции);
б) индексирование сохраняет требуемую логическую упорядоченность записей в файле данных (становится возможным поиск по интервалам, поиск близких значений, доступ к данным в их логической последовательности).

Применение индексов в целом эффективнее рассмотренных выше способов хранения и обработки данных. Это достигается за счет обработки значительно меньшего объема данных (индексного файла вместо файла данных) в операциях поиска и сортировки, особенно, если используемый индекс целиком помещается в оперативную память. Основной проблемой применения индексов является потеря производительности при их обновлении после операций удаления, вставки или изменения значения индексируемого поля.

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

Файл данных может иметь один первичный индекс и несколько вторичных индексов.

Индекс может быть разреженным (поле индексирования содержит индексные записи только для некоторых ключевых значений поиска в последовательно упорядоченном файле) или плотным (в индексе содержатся индексные записи для всех значений поиска в упорядоченном или неупорядоченном файле).

Применение индексов в целом эффективнее рассмотренных выше способов хранения и обработки данных. Это достигается за счет обработки значительно меньшего объема данных (индексного файла вместо файла данных) в операциях поиска и сортировки, особенно, если используемый индекс целиком помещается в оперативную память. Основной проблемой применения индексов является потеря производительности при их обновлении после операций удаления, вставки или изменения значения индексируемого поля.

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

Файл данных может иметь один первичный индекс и несколько вторичных индексов.

Индекс может быть разреженным (поле индексирования содержит индексные записи только для некоторых ключевых значений поиска в последовательно упорядоченном файле) или плотным (в индексе содержатся индексные записи для всех значений поиска в упорядоченном или неупорядоченном файле).