Диплом К

Табл. 2. Список регистрируемых классом dsFile ошибок

3.4. Файл индексов

3.4.1. Введение Для начала следует дать необходимые определения.

Файл индексов (BT–файл) – файл данных, содержащий один или несколько индек-

сов и их каталог для доступа к отдельным индексам.

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

также возможность поиска конкретной пары ключ–значение.

3.4.2. Выбор структуры индекса Основное предназначение разрабатываемого файла индексов – быстрый поиск

ключа в дереве. В литературе (например, [3]) подробно описаны несколько вариантов решения этой задачи, например B-дерево и В+дерево. Как В-, так и В+дерево предна-

значены для хранения ключей, как правило, фиксированной длины.

Вид B-дерева показан на рис. 15. Каждый прямоугольник представляет собой страницу дерева. Видно, что при наличии N элементов на странице имеется (N+1) ссыл-

ка, выходящая с этой страницы. B-дерево содержит некоторое множество ключей, но не все ключи присутствуют на листьях дерева, часть ключей присутствует также на про-

межуточных его узлах.

Рис. 15. B-дерево порядка 2.

В отличие от B-дерева, В+дерево имеет на листьях все множество ключей, поме-

щенных в дерево. При этом некоторые ключи дублируются на промежуточных узлах дерева.

3.4.3. Особенности реализации

BT–файл реализован на базе DS–файла. Узел дерева индекса в ВТ–файле далее называется блоком. Различаются блоки данных и управляющие блоки. Блоки данных являются листьями дерева, а управляющие блоки – промежуточными его узлами.

Основным отличием разработанного ВТ–файла от классического В+дерева явля-

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

Кроме того, каждый управляющий блок дерева имеет ссылки на блоки нижнего уровня.

Причем ссылка на блок является атрибутом ключа – сколько ключей в блоке, столько и ссылок. Чтобы привести дерево к каноническому виду (N ключей и N+1 ссылка) на каждый блок вводится специальный нулевой ключ, то есть ключ, имеющий минималь-

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

Рис. 16. Сравнение блоков В+дерева и ВТ–файла

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

Каждый отдельный блок В+дерева является записью в DS–файле. Также отдель-

ной записью хранится каталог всех индексов, содержащихся в BT–файле. Номер записи,

содержащей каталог индексов, сохраняется на нулевой странице DS–файла.

В блоках данных В+деревьев совмещено хранение ключей и списков значений произвольной длины к этим ключам (инвертированных списков), что ускоряет поиск пары ключ–значение. Кроме того, блоки деревьев (блоки данных или листья) прошиты

btCtrlBlock (корневой)

Рис. 17. Общая структура дерева

btCtrlBlock (ко рен ь дерева) 0

btResBlock

Рис. 18. Структура дерева сразу после создания

3.4.4.2. Базовый блок дерева

Базовый блок – это список элементов переменной длины. В состав элемента вхо-

дит ключ (постоянной или переменной длины) и список значений этого ключа (пере-

менной длины). Структура элемента представлена на рис. и . В частном случае уни-

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

Ниже описаны все поля элемента.

Рис. 19а. Структура элемента базового блока (вариант 1)

Рис. 20. Элемент в случае уникальных ключей фиксированной длины

Длина ключа – длина ключа, включая и байт длины (если ключ фиксированной длины, то этого поля нет).

Ключ – ключ элемента (формат зависит от типа)

Счетчик ключа – Общее число значений при ключе во всем дереве. Достоверное значение находится только на самом верхнем уровне появления ключа.

Признак – бит, указывающий какая информация следует дальше: 0 – будет ссылка

(ВСН) на блок нижнего уровня; 1 – будет список значений.

Ссылка – ВСН блока следующего уровня.

Длина списка – Длина списка значений при ключе в данном элементе в байтах.

Есть след.? и Есть пред.? – биты, используемые только в блоке данных. Они пока-

зывают, есть ли еще блоки со значениями этого ключа (подробнее см. раздел 3.4.4.3.)

Значение – Значение при ключе. Для управляющего блока значение имеет формат,

показанный на рис. 21. Для блока данных – это искомое значение при ключе. Размер значения (как и ключа в случае фиксированной длины ключа) задается при создании дерева.

Äëèí à çí à÷åí èÿ 24 бита (3 байта)

Рис. 21. Структура значения при ключе в управляющем блоке

Для базового блока поддерживаются различные форматы как ключа, так и значе-

ния. Форматы ключей и значений в блоках дерева задаются при создании дерева. Реали-

зован ряд готовых форматов: целое число, строка текста переменной или постоянной длины, дата, время, деньги, телефон. Для задания нестандартных форматов клю-

чей/значений требуется наличие пользовательской функции их сравнения.

Размещение элементов при добавлении производится в порядке возрастания клю-

чей этих элементов. Значения в списке значений элементов также располагаются в по-

рядке возрастания. Это позволяет проводить бинарный поиск в списке значений (при фиксированной длине значения).

3.4.4.3. Блок данных

Предназначен для хранения списка значений. Является листом дерева (не имеет ссылок на другие блоки). Полный список как ключей, так и значений хранится именно в блоках данных. Блок данных состоит из заголовка и списка элементов. Структура заго-

ловка блока данных представлена на рис. 22. Поля заголовка блока описаны ниже.

Структура элементов списка показана на рис. . Поля элементов списка описаны в разде-

ле 3.4.4.2..

Рис. 22. Структура заголовка блока данных

Номер дерева – порядковый номер индекса, к которому относится данный блок

Уровень в дереве – номер уровня в дерева. Уровни дерева нумеруются снизу вверх, так что блоки данных всегда имеют номер 0. Данное поле вводится для единства формата заголовка с управляющим блоком.

Ссылка на следующий блок и ссылка на предыдущий блок предназначены для формирования двунаправленного списка блоков данных. Наличие такого списка суще-

ственно ускоряет процедуры перемещения по соседним ключам/значениям за счет ис-

ключения необходимости обращения к управляющим блокам. Если список значений для некоторого ключа не помещается на один блок данных, то биты Есть след.? и Есть пред.? показывают, есть ли соответственно перед и после этого блока данных еще блок или блоки со значениями этого же ключа. Пример списка значений, размещенного на трех блоках данных, приведен на рис 23. На рисунке разной штриховкой показаны списки значений, относящиеся к разным ключам.

Åñòü ï ðåä?

Рис. 23. Пример длинного списка значений

3.4.4.4. Управляющий блок

Предназначен для хранения ключей и, возможно, некоторых значений при них.

Управляющий блок состоит из заголовка и списка элементов. Структура заголовка бло-

ка данных представлена на рис. 24. Поля заголовка блока совпадают с полями блока данных и описаны в разделе 3.4.4.3. Структура элементов списка показана на рис. и .

Поля элементов списка описаны в разделе 3.4.4.2.