Руководство по созданию эффективных запросов

48

Еще больше теории: алгоритмы
Рис. 3.5 

Индексная структура
B-деревья
Самая распространенная индексная структура – это B-дерево. Структура 
B-дерева показана на рис. 3.6; коды аэропортов являются индексными клю-
чами. Дерево состоит из иерархически организованных узлов, связанных 
с блоками, хранящимися на диске.
Листовые узлы (показанные на рис. 3.6 в нижней строке) содержат точно 
такие же записи индекса, как на рис. 3.5; эти записи состоят из индексного 
ключа и указателя на строку таблицы.
Нелистовые узлы (расположенные на всех уровнях, кроме нижнего) со-
держат записи, состоящие из наименьшего ключа (на рис. 3.5 это наимень-
шее буквенно-цифровое значение) в блоке, расположенном на следующем 
уровне, и указателя на этот блок. Все записи во всех блоках упорядочены, 
и в каждом блоке используется не менее половины доступного объема.
Любой поиск ключа 
K
начинается с корневого узла B-дерева. Во время 
поиска по блоку будет найден самый большой ключ 
P
, не превышающий 
K
, 
и затем поиск продолжается в блоке, на который ссылается указатель, свя-
занный с 
P
. Поиск продолжается, пока мы не дойдем до листового узла, где 
указатели ссылаются на строки таблицы. Количество просмотренных при 
поиске узлов равно глубине дерева. Конечно, ключ 
K
не обязательно хранится 
в индексе, но при поиске обнаруживается либо ключ, либо то место, где он 
мог быть расположен.

---

Индексные структуры 

49
Рис. 3.6 

Пример B-дерева
B-деревья также поддерживают поиск по диапазону (представляемый 
операцией 
between
в SQL). Как только будет найдена нижняя граница диапа-
зона, все индексные ключи диапазона можно получить последовательным 
сканированием листовых узлов до тех пор, пока не будет достигнута верх-
няя граница диапазона. Сканирование листовых узлов необходимо также 
для получения всех указателей, если индекс не является уникальным (то 
есть значение индексного ключа может соответствовать более чем одной 
строке).