Каждая страница индекса называется индексной страницей, или узлом индекса. Структура индекса начинается на верхнем уровне с корневого узла.

Индексы в SQL-сервер.

Бинарное дерево (В-дерево)

Структура бинарного дерева является следствием дальнейшего расширения концепции использования индексов (строится индекс над индексом) и представляет собой многоуровневые индексы.

Как следует из названия "B-дерево", узлы-ветви разветвляются от корневого узла в древовидной форме. Каждая группа узлов-ветвей одного уровня в древовидной структуре называется уровнем индекса (Рисунок).

Рис. Уровни индекса

Каждая страница индекса называется индексной страницей, или узлом индекса. Структура индекса начинается на верхнем уровне с корневого узла.

Корневой узел (Root Node) соответствует началу индекса: это первые данные, к которым осуществляется доступ при поиске данных. Корневой узел содержит ряд строк индекса. Эти строки содержат значение ключа и указатель на определенную индексную страницу, которая называется узлом-ветвью (Branch Node, Рисунок).

Рис.. Корневой узел и узлы-ветви

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

Если использовать в качестве аналога книгу, то индекс действует следующим образом: предположим, что началом индекса (алфавитного указателя) является страница, где указаны номера страниц для статей индекса на букву "a", "b", "c" и т.д.

Затем предположим, что эти страницы содержат номера страниц для статей в диапазонах aa-ab, ас-ad, ae-af и т.д., а соответствующие страницы – номера страниц для записей в диапазонах aaa-aab, aас-aad, aae-aaf и т.д.

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

Рис. В-дерево для столбца emp_no таблицы employee

Как и корневой узел, каждый узел-ветвь содержит ряд индексных строк в структуре индексной страницы. Каждая индексная строка указывает на другой узел-ветвь или на узел-лист (конечный узел, Рисунок).

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

Дата добавления: 2015-08-05