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

Нелинейные структуры индексов. (вопрос 13)

При организации индексов в таких случаях чаще всего используются древовидные, иерархические структуры в виде Б-деревьев.

Б-дерево представляет собой корневое сбалансированное сильно ветвистое дерево.

Сбалансированность Б-дерева означает наличие одинакового количества потомков до листовой вершины по любым разветвлениям от корневой вершины (рис. 2.16). Структура корневой вершины аналогична структуре внутренних вершин, но содержит информацию об «n» различных возрастающих значениях индексируемого поля. Число «n» называется порядком Б-дерева.

Каждая внутренняя вершина, если она полностью заполнена, содержит информацию о «n-1» различных последовательно возрастающих значениях индексируемого поля по схеме, приведенной на рис. 2.17.

Рис. 2.16. Структура внутренней вершины Б-дерева.

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

На рис. 2.17, 2.18 продемонстрировано Б-дерево 3-го порядка, уровня 2, построенное для поля «Год рождения» таблицы «Сотрудники». Напомним, что уровень узла определяется количеством предков до корня дерева.

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

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

Рис. 2.17. Пример Б-дерева 3^го порядка.

Схема листовой страницы представлена на рис. 2.18.

Рис. 2.18. Структура листовой вершины Б-дерева.

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

· Из внешней памяти в оперативную память считывается страница с корневой вершиной и последовательно просматривается до первого значения, превышающего значение индексируемого поля нужной записи. При этом определяется ссылка (номер) страницы-потомка (внутренней или листовой).

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

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

Анализ данного алгоритма показывает, что при поиске нужного значения индексируемого поля по индексу в виде Б-дерева требуется такое количество страничных обменов между внешней и внутренней памятью, которое равно уровню Б-дерева плюс единица. При достаточно большом значении порядка «n», уровень «m» Б-дерева невелик (m³2¸3), и следовательно, количество страничных индексных обменов с внешней памятью также невелико. При этом сбалансированность Б-дерева обеспечивает одинаковые затраты по доступу к любой записи с любым значением индексируемого поля.

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