Многоуровневые индексы на основе В-дерева

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

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

Каждое B-дерево должно удовлетворять следующим условиям:

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

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

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

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

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

Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе – к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X₀ и конечное значения X_к ключа, а также три указателя. Если значение искомого ключа меньше, чем X₀, то происходит обращение по левому указателю; если оно больше, чем X_к, то происходит обращение по правому указателю; если оно попадает в диапазон X₀÷X_к – по среднему указателю. Вершины, которые делят следующий уровень дерева на три поддерева, могут занимать несколько уровней. Это зависит от количества индексируемых записей и среднего размера индексируемых значений.

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

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

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

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

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

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

Использование индексов

В системах, поддерживающих язык SQL, индекс создаётся командой create index. Синтаксис этой команды следующий:

create index <имя_индекса> on ( [, ,...]) [];

Имя индекса должно быть уникальным среди имён объектов БД. Если индекс составной, то входящие в него поля перечисляются через запятую. Необязательные <параметры> зависят от используемой СУБД.

Например, с помощью следующей команды можно создать составной индекс для таблицы СОТРУДНИКИ (EMP) по полям Фамилия (fam) и Имя (name):

create index ind_emp_name on emp(fam, name);

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

Система может воспользоваться индексом по определённому полю, если в запросе на значение этого поля накладывается условие, например:

SELECT * FROM emp WHERE name = 'Даль';

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

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

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

Выбор столбцов для индекса определяется следующими соображениями:

• В первую очередь выбираются столбцы, которые часто встречаются в условиях поиска.
• Стоит индексировать столбцы, которые используются для соединения таб-лиц или являются внешними ключами. В последнем случае наличие индекса позволяет обновлять строки подчинённой таблицы без блоки-ровки основной таблицы, когда происходит интенсивное конкурентное обновление связанных между собою таблиц (подробнее о блокировках – раздел 5.4).
• Нецелесообразно индексировать столбцы с низкой селективностью. Исключения для низкой селективности составляют случаи, при которых выборка чаще производится по редко встречающимся значениям.
• Не индексируются столбцы, которые часто обновляются, т.к. команды об-новления ведут к потере времени на обновление индекса.
• Не индексируются столбцы, которые часто используются как аргументы выражений или функций: как правило, это не позволяет использовать ин-декс.

В некоторых случаях использование составного индекса предпочтительнее, чем одиночного, а именно:

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