Усовершенствованные сбалансированные древовидные индексы

Сбалансированное дерево

Во многих СУБД для хранения данных или индексов используется структура данных, называемая деревом. Дерево состоит из иерархии узлов (node), в которой каждый узел, за исключением корня (root), имеет родительский (parent) узел, а также один, несколько или ни одного дочернего (child) узла. Корень не имеет родительского узла. Узел, который не имеет дочерних узлов, называется листом (leaf).

Глубиной дерева называется максимальное количество уровней между корнем и листом. Глубина дерева может быть различной для разных путей доступа к листам. Если же она одинакова для всех листов, то дерево называется сбалансированным, или В-деревом (В-Тгее). Степенью (degree) (или порядком (order)) дерева называется максимально допустимое количество дочерних узлов для каждого родительского узла. Большие степени обычно используются для создания более широких и менее глубоких деревьев. Поскольку время доступа в древовидной структуре зависит от глубины, а не от ширины, обычно принято использовать более "разветвленные" и менее глубокие деревья. Бинарным деревом (binary tree) называется дерево порядка 2, в котором каждый узел имеет не больше двух дочерних узлов.

Усовершенствованные сбалансированные древовидные индексы определяются по следующим правилам.

• Если корень не является лист-узлом, то он должен иметь, по крайней мере, два дочерних узла.
• В дереве порядка n каждый узел (за исключением корня и листов) должен иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого.
• В дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого.
• Количество значений ключа в нелистовом узле на единицу меньше количества указателей.
• Дерево всегда должно быть сбалансированным, т.е. все пути от корня к каждому листу должны иметь одинаковую глубину.
• Листы дерева связаны в порядке возрастания значений ключа.