Материал: Л-9 - Методы доступа к данным
Способы организации индексов – одно- и многоуровневые индексы
Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике используется редко.
В развитых СУБД применяются более сложные методы организации индексов.
Особенно эффективными являются многоуровневые индексы в виде сбалансированных деревьев
(В-деревьев, Balance Trees).
Древовидная организация данных (1)
Древовидные структуры состоят из набора вершин и ребер. Каждая вершина содержит данные и ссылку на вершину нижнего уровня.
Дерево – совокупность элементов, называемых узлами (один из которых определен как корень), и отношений,
образующих иерархическую структуру узлов.
Древовидная организация данных (2)
Вершина в 0-м уровне – корень дерева. В корень не входит ни одного ребра. Вершины, из которых не выходит ни одного ребра, – листья.
Дерево, из каждой вершины которого выходит только по два ребра, – бинарное (дерево порядка 2).
Древовидная организация данных (дерево) – множест-
во записей, расположенных следующим образом:
на 1-м уровне расположена только одна запись (корень дерева);
к любой записи i-го уровня ведет адрес связи только от одной записи уровня (i–1).
Упорядоченность бинарных деревьев
Бинарные деревья интересны тем, что составляющие их записи могут быть упорядочены, для чего один из реквизитов записи должен быть объявлен ключевым.
В упорядоченном бинарном дереве значение ключевого реквизита каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не больше, чем ключ любой записи на ее правой ветви.
Пример упорядоченного бинарного дерева
Для набора чисел {7, 3, 5, 2, 8, 1, 6, 10, 9, 4, 11} получится бинарное дерево.
Структура бинарного дерева позволяет быстро вставлять и удалять записи и проводить эффективный поиск (в каждую запись добавлены два поля для ссылок).