B+-деревья
Наиболее популярным подходом к организации индексов в базах данных является использование техники B+-деревьев. Техника B- и B+-деревьев была предложена в начале 1970-х гг. Рудольфом Байером (Rudolf Bayer) и Эдом Маккрейтом (Ed McCreight) . С точки зрения внешнего логического представления B-дерево – это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева – это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница). В B+-дереве внутренние и листовые страницы обычно имеют разную структуру.
Типовая структура внутренней страницы B+-дерева показана на рис. 12.2.
Рис. 12.2. Типовая структура внутренней страницы B+-дерева
При этом выдерживаются следующие свойства:
- ключ1
ключ2
...
ключm;
- в странице дерева Nm
находятся ключи k
со значениями ключm
<= k <= ключm+1.
Листовая страница обычно имеет следующую структуру, показанную на рис. 12.3.
Рис. 12.3. Структура листовой страницы B+-дерева
Листовая страница обладает следующими свойствами:
- ключ1
< ключ2
< ... < ключk;
- списокr
– упорядоченный список идентификаторов кортежей (tid), включающих значение ключr;
- листовые страницы связаны одно- или двунаправленным списком.
Поиск в B+-дереве – это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку B+-деревья являются сильно ветвистыми и сбалансированными, для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n
ключей, то при хранении m
записей требуется дерево глубиной logn(m).