Багаторівневі індекси на основі В-дерева

B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок — это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня. Каждое B-дерево должно удовлетворять следующим условиям:

• 1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо — к вершине с большими ключами.
• 2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин.
• 3. Если неконечная вершина содержит k (kЈ n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.
• 4. Все конечные вершины расположены на одном уровне.

Алгоритм формирования B-дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент B-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно — осуществляется перестройка дерева. Пример построения B-дерева порядка 3 приведён на рис. 2.

Рис. 2 Пример построения B-дерева порядка 3

Индексирование в виде B-дерева используется, например, в СУБД Oracle (рис. 3).

Рис. 3 Пример индексного блока СУБД Oracle

Организация индексов в СУБД Oracle несколько отличается от рассмотренной выше классической организации B-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки содержат данные индекса, которые ссылаются на блоки индекса нижних уровней. Самый нижний n-й уровень содержит блоки индекса (блоки-листья), которые содержат непосредственно данные индекса (ключи) и соответствующие идентификаторы строк ROWID (row identification, КБД), используемые для нахождения самих строк. Блоки-листья связаны между собой указателями.

Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе — к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X0 и конечное значения Xк ключа, а также три указателя. Если значение искомого ключа больше, чем X0, то происходит обращение по левому указателю; если оно меньше, чем Xк, то происходит обращение по правому указателю; если оно попадает в диапазон X0ёXк — по среднему указателю.

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

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

Индекс в виде B-дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных). Например, если при добавлении новой записи с ключом «Горин» возникает переполнение соответствующего блока индекса (рис. 3), система может перераспределить значения ключей так, как показано на рис. 4.

Если все блоки-листья индекса заполнены приблизительно на три четверти, то при добавлении новой записи осуществляется полная перестройка B-дерева путём введения дополнительного уровня. Всё это скрыто от пользователя и происходит автоматически.

Рис. 4. Пример перераспределения данных индексного блока СУБД Oracle

Структура B-дерева имеет следующие преимущества:

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