Базы данных. Вводный курс


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).


- Начало -  - Назад -  - Вперед -