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

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

Каждая страница должна содержать следующие данные:

· текущее количество элементов на странице (оно изменяется от m до 2m)

· указатель на страницу, являющуюся самым левым потомком данной страницы

· основной массив элементов страницы, размерность массива 2m, каждый элемент – это запись со следующими полями:

o ключ некоторого типа

o указатель на страницу, являющуюся потомком текущей страницы и содержащую ключи, большие ключа данного элемента

o информационная часть (как некоторая структура или указатель на область памяти)

Соответствующие описания типов можно сделать следующим образом:

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

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