Диплом К

3.4.5.2. Класс btCtrlBlock

Данный класс реализует управляющий блок дерева. Формат управляющего блока описан в разделе 3.4.4.3.

3.4.5.3. Класс btResBlock

Данный класс реализует управление блоком данных дерева. Формат блока данных описан в разделе 3.4.4.4.

3.4.5.4. Класс btTreePath

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

Логически путь в дереве представляет собой цепочку блоков, по одному с каждого уровня. Эта цепочка формируется во время операции поиска по дереву, когда произво-

дится спуск от корневого блока до блока данных. Те блоки, которые будут считаны во время этого спуска, и составят путь. Ускорение (для операций добавления, удаления,

поиска близко расположенных ключей) достигается за счет сокращения операций вво-

да/вывода, так как при наличии требуемого блока в пути, он не будет считываться с диска (по крайней мере в пути всегда будет находиться корневой блок). Построение пу-

ти осуществляет метод дерева btTree::Search(), который вызывается в начале всех мето-

дов корректировки дерева.

Операции по массовому добавлению и удалению из дерева следует проводить с учетом такого построения пути, а именно: массивы ключей (значений) надо перед до-

бавлением отсортировать по возрастанию – это обеспечит минимальное число обраще-

ний к диску.

Путь в дереве является тем объектом, в ведении которого находятся операции ввода/вывода блоков дерева в/из файла (само дерево таких операций не проводит, а ра-

ботает только с блоками из пути). Поэтому, если требуемого классом btTree блока нет в пути, то производится его подкачка из файла на определенное место в пути (в зависи-

мости от уровня местонахождения в дереве). Если же это место в пути занято другим блоком, то он записывается в файл (если менялся) и освобождается. Обработки опу-

стевших блоков здесь не проводится.

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

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

ление опустевших блоков и обнуление соответствующего элемента пути.

Последней задачей, возложенной на объект пути, является операции по созданию и удалению дерева. Дерево при создании делается сразу двухуровневым: верхний уро-

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

Необходимым действием по инициализации дерева является добавление в оба образо-

ванных блока "нулевых" ключей. В корневом блоке в элементе с нулевым ключом прос-

тавляется ссылка на единственный пока блок данных, а в блоке данных проставляется единственное нулевое значение. Вид дерева сразу после его создания представлен на рис. 18.

Операция по удалению дерева заключается в удалении всех его блоков из DS–

файла. Алгоритм рекурсивный, и корневой блок удаляется последним.

3.4.5.5. Класс btTree

Объект, предназначенный для организации данных (пар ключ–значение) в виде В+дерева, с целью проведения быстрого поиска значений по ключу. Особенность дан-

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

Логически дерево состоит из набора блоков, связанных определенным образом, и

описателя дерева.

Каждый блок дерева является записью в DS–файле и содержит как ключи, так и значения. Блоки дерева могут быть двух типов: блоки данных (класс btResBlock) и

управляющие блоки (класс btCtrlBlock). Блоки данных расположены на самом нижнем

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

В описателе задаются все параметры дерева: номер, имя, ВСН корневого блока,

число уровней, тип ключей, а также максимальный размер блока (он равен длине дан-

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

– общее число ключей, общее число значений, общую длину ключей и общую длину значений.

Все операции ввода/вывода с DS-файлом проводятся через путь (класс–предок btTreePath), а само дерево работает только с блоками из пути. Путь строится во время операции поиска по дереву.

3.4.5.6. Класс btTreeStack

Служит для ускорения одновременной работы с несколькими деревьями в индекс-

ном файле.

Логически представляет собой стек, элементами которого являются указатели на открытые деревья. Глубина стека задается при конструировании объекта.

Использование его просто – после первого открытия какого-либо дерева указатель на него помещается в стек, а при всех последующих запросах на открытие этого дерева указатель на него берется готовым из стека и используется (не надо конструировать де-

рево, выделять и инициализировать путь и т.п.). Если в стеке найден указатель на тре-

буемое дерево, то он меняется местами с указателем на вершине стека, с целью недо-

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

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

Физически стек представляет собой два указателя (вершина и база стека), выде-

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

ную глубину стека. Память под элементы стека выделяется динамически, но глубина

стека может быть не более 255 (все равно в индексном файле не может быть больше 255

индексов). Стек растет в сторону увеличения адресов.

3.4.5.7. Класс btTreeRes

Предназначен для формирования и работы со значениями найденного в дереве ключа.

Является потомком блока данных (класс btResBlock) и представляет собой цепоч-

ку блоков данных (с нижнего уровня дерева), содержащих значения одного ключа. Гра-

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

ливается текущим нужный элемент.

В памяти объект btTreeRes содержит только один блок – он называется текущим.

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

3.4.5.8. Класс btFind

Является надстройкой над классом btTreeRes, дополнительно включающим вре-

менный файл и функцию сравнения значений.

Объект btFind, создаваемый первым в текущем сеансе работы создает временный файл, который используется всеми объектами btFind, созданными после в этом же сеан-

се работы. Соответственно при удалении последнего объекта btFind производится уда-

ление файла.

Для объекта btFind дополнительно задан метод, позволяющий проводить базовые операции И, ИЛИ, И–НЕ над другими объектами btFind (btTreeRes), что дает возмож-

ность осуществлять обработку сложных запросов.

3.4.5.9. Класс btCatalog

Предназначен для хранения в памяти описателей всех деревьев, созданных в BT–

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

файле, а именно:

массив адресов функций сравнения для разных типов ключей

массив адресов функций сравнения для разных типов значений

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

массив длин значений для разных их типов

массив адресов нулевых ключей

Задачей каталога при создании нового индекса является формирование нового описателя индекса и его включение в каталог BT–файла. При удалении индекса из BT–

файла каталог удаляет сам индекс и его описатель из массива описателей.

При работе с созданными в BT–файле индексами каталог проводит их открытие и закрытие с использованием стека (класс btTreeStack). Те индексы, адреса которых нахо-

дятся в стеке: не закрываются и не открываются что существенно ускоряет работу с ни-

ми.

Физически каталог представляет собой непрерывную область памяти, куда запи-

сываются описатели индексов. Эти данные при закрытии BT–файла записываются как запись в DS–файле, а при открытии считываются. Номер этой записи сохраняется в за-

головке BT–файла, записываемым на 0-ю страницу.

3.4.5.10. Класс btFile

Предназначен для организации использования совокупности индексов. Логически представляет DS-файл, в котором размещается каталог индексов (в виде отдельной за-

писи) и все индексы (каждый блок индекса – отдельная запись).

В функции объекта btFile входит добавление и удаление новых индексов; поиск,

удаление и добавление новых ключей (пар ключ–значение) в созданные индексы; пере-

мещение по ключам в созданных индексах.

Кроме того, пользователю объекта btFile доступны все методы классов dsFile и btCatalog.

3.4.6. Алгоритмы управления индексом В данном разделе описаны алгоритмы управления отдельным индексом. К ним от-

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

ритм разбиения блоков индекса. Все перечисленные алгоритмы представлены в графи-

ческой части проекта.

3.4.6.1. Алгоритм поиска пары ключ–значение

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

– число значений при искомом ключе в индексе, код уточнения результата поиска и по-

строение внутреннего пути с текущими значениями в блоках на искомом ключе и зна-

чении.

Основное тело алгоритма – цикл по уровням индекса (блок 2), начиная с верхнего,

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

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

ном блоке производится поиск заданного ключа.

Если индекс хранит уникальные ключи постоянной длины, то производится би-

нарный поиск ключа (блоки 5-6), иначе производится проверка на актуальность теку-

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

иначе с первого.

В пределах блока поиск выполняется цикл перебора (блоки 11-21) ключей и срав-

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

При этом текущим делается предыдущий ключ (ближайший меньший или совпадаю-

щий ключ блока).

После выхода из цикла поиска ключей внутри блока, при условии наличия иско-

мого ключа в этом блоке (блок 22), проводим поиск искомого значения в списке значе-

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

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

После выхода из цикла прохода уровней индекса проверяется признак наличия ис-

комого ключа в индексе. Если ключ был найден, то из самого верхнего блока пути, со-

держащего искомый ключ берется значение счетчика значений и возвращается как ре-

зультат алгоритма. Помимо этого формируется код уточнения результата поиска, кото-

рый может принимать следующие значения:

0 – найден и ключ и значение;

1 – ключ есть, значения нет, но оно должно в списке значений при ключе;

2 – ключ есть, но искомое значение больше самого большего значения при иско-

мом ключе;

3 – ключ есть, но искомое значение меньше самого меньшего значения при ис-

комом ключе;

10 – ключ найден, а поиска значения не задавалось;

11 – искомого ключа нет, но есть совпадение с началом некоторого ключа из ин-

декса (текущие значения выставляются по этому ключу);

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

13 – искомый ключа больше самого большего ключа индекса (текущие значения выставляются по самому большому ключу);

3.4.6.2. Алгоритм добавления пары ключ–значение

Алгоритм добавления пары ключ–значение является наиболее простым из рас-

сматриваемых алгоритмов. Входными данными являются добавляемые ключ и значение к этому ключу. Результат работы – изменение внутреннего содержимого индекса.

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

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

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

шему ключу. После поиска остается только добавить в блок данных, оказавшийся пути,

заданный ключ и значение (блоки 6-10), причем размещать добавляемый ключ или зна-

чение надо после текущего ключа или значения блока данных.

Если в индексе уже есть заданный ключ, то производится добавление только зна-

чения в список значений при заданном ключе (блок 8), в противном случае производит-

ся добавление и ключа и значения.

В конце производится проверка на необходимость разбиений (блок 11), так как данные в блоках дерева после разбиения могут превысить пороговую длину. Алгоритм разбиения описан в разделе 3.4.6.4.

3.4.6.3. Алгоритм удаления пары ключ–значение.

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

ты – модификация блоков индекса.

Прежде всего перед удалением заданной пары ключ-значение проводится предва-

рительный поиск ее в индексе (блок 2). Если такая пара не существует, то осуществля-

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

вает текущие значения в блоках пути.

Основное тело алгоритма – цикл по блокам пути (блок 4), начиная с уровня блоков данных и до верхнего уровня, где находится только корневой блок.

При первом проходе цикла из пути берется (блок 3) блок данных, при последую-

щих – управляющие блоки, при последнем –корневой блок.

Для каждого считанного блока проводится анализ и сохранение положения теку-

щего ключа (блоки 6,7,13). Затем производится удаление заданного значения из списка значений текущего ключа. Если после этого удаления у ключа не осталось значений, то удаляется и ключ тоже. Если удаление проводилось из управляющего блока, то к этому моменту должен быть сформирован элемент для записи в управляющий блок с нижнего уровня, вместо удаленного. Если удалили только значение, то добавляем только значе-

ние из этого элемента, иначе добавляем весь элемент (блоки 9-11).

При удалении всего ключа из блока данных проверяем наличие блоков со значе-

ниями такого же ключа (блоки 15-18). Если таковых нет, то фиксируем информацию для корректировки статистики индекса.

Если был удален ключ и он являлся первым ключом блока, то при условии не опу-

стения блока производится формирование элемента для передачи на верхний уровень индекса (блоки 19-23).

После выхода из цикла прохода блоков пути производится корректировка стати-

стики индекса в зависимости от того удалили мы только значение или и ключ тоже

(блоки 26-28).

В конце производится проверка на необходимость разбиений (блок 29), так как некоторые блоки индекса после операции удаления могут опустеть. Алгоритм разбие-

ния описан в разделе 3.4.6.4.

3.4.6.4. Алгоритм разбиения индекса.

Блок-схема алгоритма удаления ключа в индексе приведена в графической части проекта. Входные параметры отсутствуют. Результат работы – модификация блоков ин-

декса. Задачей этого алгоритма является удаление опустевших блоков и разбиение пе-

реполненных. При разбиении блоков между уровнями индекса производится передача информации. Наличие элемента от нижнего уровня индекса, который нужно разместить на текущем уровне, индицируется специальным флагом – ActiveDivide. При входе в ал-

горитм от устанавливается в неактивное состояние (блок 2).

Основное тело алгоритма – цикл по блокам пути (блок 3), начиная с уровня блоков данных и до верхнего уровня, где находится только корневой блок.

При первом проходе цикла из пути берется (блок 4) блок данных, при последую-

щих – управляющие блоки, при последнем –корневой блок.

После получения каждого блока проводится анализ состояния флага ActiveDivide.

Если он активен, то в текущий блок, из элемента для передачи с нижнего уровня, добав-

ляется ссылка (блоки 5-9), если блок нижнего уровня был разбит по значению, или весь элемент, если было разбиение по ключу. После этого флаг ActiveDivide сбрасывается.

Для каждого полученного блока проверяется превышение длины данных в нем не-

которого порогового значения1. Если длина данных блока превышает этот порог, то производится разбиение этого блока (блоки 11-13), в противном случае производится проверка на опустение этого блока (блок 23) и, если он не пуст, то делаем следующую итерацию цикла.

После операции разбиения запоминаем тип разбиения – по ключу или по значе-

нию и, если это блок данных, корректируем ссылки между существовавшими блоками данных и новым2 блоком (блоки 14-22).

Если текущий блок оказался пустым, то он удаляется из файла индекса (блоки 23-

24) и, если это оказался блок данных, то производятся корректировки ссылок между оставшимися блоками данных (блоки 26-33).

После выхода из цикла прохода блоков пути производится анализ флага

ActiveDivide. Если он активен, то произошло переполнение корневого блока и было произведено его разбиение. В этом случае индекс вырастает на один уровень – создает-

ся новый управляющий блок, который становится корневым (блоки 35-39).

3.4.7. Описание реализации.

В данном разделе описаны наиболее существенные методы работы с ВТ–файлом.

Прототипы методов обведены в рамку, далее следует описание метода и всех парамет-

ров. Полный перечень методов с кратким описанием приведен в табл. 1 в конце раздела.

В табл. 4 приведен список всех регистрируемых в процессе работы ошибок.

1Этот порог задается при создании индекса.

2Напомним, что блоки данных связаны между собой по принципу двусвязного списка.