logo
УП_САОД_2003

Представление файлов b-деревьями

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

B-дерево представляет собой дерево поиска степени m, характеризующееся следующими свойствами:

  1. корень либо является листом, либо имеет не менее 2-х потомков;

  2. каждый узел, кроме корня и листьев, имеет от (m/2) до m потомков;

  3. все пути от корня до любого листа имеют одинаковую длину.

В каждой вершине будем хранить не более NumberOfItems записей. Также необходимо будет хранить текущее количество записей в вершине. Для удобства возврата назад к корню дерева будем запоминать для каждой вершины указатель на ее предка.

Type

PBTreeNode = ^TBTreeNode;

TBTreeNode = record {вершина дерева}

Count: integer; {количество записей в вершине}

PreviousNode: PBTreeNode; {указатель на предка}

Items: array[0..m+1] of record {массив записей}

Value: ItemType;

NextNode: PBTreeNode;

end;

end;

TBTree = PBTreeNode;

У элемента Items[0] будет использоваться только поле NextNode. Дополнительный элемент Items[NumberOfItems+1] предназначен для обработки переполнения, о чем будет рассказано ниже, при описании алгоритма добавления элемента в B-дерево.

Поскольку дерево упорядочено, то

Items[1].Value<Items[2].Value<…<Items[Count].Value.

Указатель Items[i].NextNode указывает на поддерево элементов, больших Items[i].Value и меньших Items[i+1].Value. Понятно, что указатель Items[0].NextNode будет указывать на поддерево элементов, меньших Items[1].Value, а указатель Items[Count].NextNode – на поддерево элементов, больших Items[Count].Value.

У корневой вершины PreviousNode будет равен nil.

Рисунок 19. B-дерево и его организация

        1.