Б – деревья. Особенности представления Б – деревьев.

Организация внешнего поиска с помощью Б-деревьев.

Данный метод использует понятие двоичного дерева поиска, но модифицирует это понятие таким образом, что дерево получает страничную организацию. Поэтому Б-деревья часто называют деревьями со страничной организацией.
Предположим, что мы хотим организовать в оперативной памяти дерево поиска с очень большим числом вершин (миллионы и более). Пусть при этом свободной ОП не достаточно для одновременного хранения сразу всех вершин. Часть (и при том весьма существенная) вершин должна оставаться на диске. Возникает задача такой организации дерева, чтобы можно было считывать и обрабатывать сразу группу вершин. Такая группа вершин получила название “страница”. Тем самым, все сверхбольшое дерево поиска разбивается на ряд страниц и чтение вершин с диска выполняется постранично. Это позволяет существенно уменьшить количество обращений к внешней памяти.
В качестве примера рассмотрим обычное дерево поиска из 15 вершин. Пусть для простоты оно является идеально сбалансированным. Выделим в нем 5 элементарных поддеревьев по 3 вершины в каждом и логически объединим эти вершины вместе в виде страниц. Если в дереве необходимо найти какую-либо терминальную вершину, и вершины считываются в ОП по одной, то для этого в обычном дереве потребуется 4 обращения к внешней памяти. А в дереве со страничной организацией потребуется считать из внешней памяти лишь 2 страницы – корневую и одну из терминальных. Даже в этом простейшем примере страничная организация дерева позволяет уменьшить число обращений к диску в два раза. Для сверхбольших деревьев этот эффект становится еще более заметным.
 

Для эффективной страничной организации сверхбольшого дерева поиска очень важным условием является равномерность его роста, максимальное соответствие идеальной сбалансированности. К сожалению, условие идеальной сбалансированности приводит к очень сложным алгоритмам, поэтому Байером и было введено понятие дерева со страничной организацией (Б-дерево).
Б-дерево порядка  m  со страничной организацией - это структура данных, удовлетворяющая следующим условиям:

Пример. Рассмотрим простейшее Б-дерево порядка  m=2 с ключами целого типа. В соответствии с приведенными выше правилами, каждая страница такого дерева содержит от 2 до 4 вершин, а корневая – от 1 до 4. Каждая нетерминальная страница может иметь от 3 до 5 потомков. Пример дерева – на рисунке (к сожалению, терминальные страницы приходится располагать на разных уровнях).
 

Поскольку Б-дерево является обобщением классического дерева поиска, то оно обладает следующими свойствами:

Последнее свойство является обобщением основного правила дерева поиска. Например, страница с ключами 40, 50 и 60 имеет четырех потомков, причем самый левый потомок содержит ключи меньше 40 (но больше 30), более правая страница содержит ключи в диапазоне от 40 до 50, еще более правая – в диапазоне от 50 до 60, а самая правая – больше 60.
Эффективность использования Б-дерева для поиска ключей в сверхбольших наборах данных можно оценить следующим образом.. Если Б-дерево имеет порядок  m, а число элементов – n, то самым наихудшим случаем будет случай, когда на каждой странице находится минимально возможное число элементов, а именно -  m. В этом случае высота Б-дерева определяется величиной  logmn, а именно высота и определяет количество обращений к внешней памяти.
Например, если число элементов в наборе данных  n = 1 миллион,   а порядок Б-дерева  m = 100,  то log1001000000 = 3, т.е. максимум может потребоваться 3 обращения к внешней памяти. С другой стороны, даже в этом наихудшем случае оперативная память используется достаточно эффективно (примерно половина памяти от заявленного объема).

Б-дерево как структура данных

Базовым элементом Б-дерева является страница, поскольку именно она содержит всю основную информацию. Поэтому, прежде всего, необходимо описать структуру страницы Б-дерева.
Каждая страница должна содержать следующие данные:

Соответствующие описания типов можно сделать следующим образом:
type    pPage = ^Page;   {ссылочный тип для адресации страниц}
TItem = record          {описание структуры элемента массива}
key : integer;                 {ключ вершины дерева}
cPage : pPage;      {указатель на страницу-потомка}
inf : <описание информационной части>;
end;
Page = record           {описание структуры страницы}
nPage : word;               {число вершин на странице}
leftPage : pPage;    {указатель на самого левого потомка}
mas : array [1 . . 2m]  of  TItem;    {основной массив}
end;
Из переменных достаточно ввести два указателя: на корневую страницу (pRoot) и текущую обрабатываемую в данный момент страницу (pCurrent).
Схематично  структуру страницы можно представить следующим образом (для краткости указатель  pCurrent  заменен идентификатором  pC):
 

pC^.nPage

pC^.leftPage

pC^.mas[1]

pC^.mas[2]

. . . . .

pC^.mas[2m]

.key

.cPage

.inf

.key

.cPage

.inf

 

 

 

.key

.cPage

.inf

Видно, что Б-дерево является достаточно сложной комбинированной структурой, представляя собой набор связанных указателями  записей. Для использования Б-дерева необходим стандартный набор операций: поиск заданного элемента, добавление вершины, удаление вершины.

Яндекс.Метрика