Материал: Л-9 - Методы доступа к данным

Структура В*-дерева для таблицы

EMPLOYEE (индекс по emp_no)

Поиск в В*-дереве значения 25348

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

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

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

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

Преимущества В*-дерева (1)

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

В*-дерево автоматически поддерживается в сбалансированном виде.

Обеспечивается хорошая производительность для ши-

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

Преимущества В*-дерева (2)

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

Производительность В-дерева одинаково хороша для маленьких и больших таблиц и при увеличении размера таблицы существенно не меняется.

Кластеризованный индекс

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

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

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

ный связанный список (цепочка страниц).

Листья содержат страницы данных (узлы других уровней содержат страницы индекса.) Таблица, для которой определен кластеризованный индекс, называется

кластеризованной таблицей.