Использование инвертированных списков в СУБД HyTech

В СУБД HyTech любые поля записи, кроме больших двоичных объектов и текста, могут быть объявлены ключевыми. Для таких полей строится индекс. Индексы могут быть построены для группы из нескольких полей. Такая совокупность полей называется агрегатом, а ключ – составным.

СУБД HyTech можно отнести к классу систем с частично инвертированными файлами, так как:

· Записи располагаются в произвольной последовательности (соответствующей последовательности ввода);

· Первичный индекс отсутствует (нет ключа, в соответствии с которым записи упорядочены в файле данных);

· Для прямой адресации записей используются инвертированные индексы.

Индексы ключевых полей и групп полей строятся как инвертированные списки, упорядоченные по значению ключа пары «значение ключа - номер записи». Физическая организация списка зависит от гистограммы значений ключа:

· Уникальные (или ключи, где значения почти не повторяются);

· Ключи с повторяющимися значениями – повторяющиеся ключи;

· Ключи, которые имеют малое число значений (не более 2-3 десятков), однако для каждого из этих значений имеется масса записей – массовые ключи.

Инвертированный список для уникальных ключей непосредственно состоит из пар «значение - номер» и для ускорения поиска имеет оглавление. При большом числе записей строится еще и оглавление 2-го порядка. Оглавление представляет собой упорядоченный список значений, каждый элемент которого выбран из основного инвертированного списка с некоторым интервалом.

Основной инвертированный список условно разбивается на некоторое количество сегментов равного размера. Число таких сегментов - корень квадратный из числа записей в постоянной части. В оглавление 1-го порядка собираются первые элементы каждого сегмента основного инвертированного списка. Аналогичным образом, в оглавление 2-го порядка собираются первые элементы каждого сегмента оглавления первого порядка. Для создания оглавления 2-го порядка оглавление 1-го порядка также разбивается на сегменты. Если ключ не является строго уникальным, значения ключа в инвертированном списке будут повторяться.

Если повторов значений много, выгоднее хранить только уникальные значения и счетчики повторов. Для таких повторяющихся ключей инвертированный список устроен сложнее: пары «значение - номер» заменены на пары «значение - адрес в таблице номеров». Хранятся только уникальные значения ключа. В остальном, индекс похож на предыдущий. Для ускорения поиска индекс имеет оглавление, а при большом числе записей строится еще и оглавление 2-го порядка, в которое собираются первые элементы каждого сегмента оглавления первого порядка. Для создания оглавления 2-го порядка оглавление 1-го порядка также разбивается на сегменты.Если же число повторов каждого значения очень велико (а, значит, число самих значений мало (не более 2 - 3-х десятков)), целесообразнее строить индекс массового типа. Оглавление такого индекса будет состоять из списка значений ключа, а для каждого значения строится битовая строка, содержащая по одному биту для каждой записи постоянной части. При этом номер бита соответствует номеру записи.

Следует отметить, что при построении индексов для постоянной части используется априорная информация, полученная при образовании постоянной части. В частности, значения ключа в индексе занимает столько байтов, чтобы хранить максимальное по длине значение (а не заданное в описателе ключа); все счетчики и адреса занимают минимальное число байтов, необходимое для хранения максимальных значений; индексы ключевых элементов таблицы хранятся в файле ассоциатора в виде связанного списка.