Высота Б-дерева

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

Теорема. Высота Б-дерева Т с n=>1 узлами и минимальной степенью t=>2 не превышает log_t(n+1)/2.

Доказательство. Пусть Б-дерево имеет высоту h. Корень дерева содержит как минимум один ключ, а все остальные узлы – как минимум по t-1 ключей. Таким образом, имеется как минимум 2 узла на глубине 1, как минимум 2t узлов на глубине 2, как минимум 2t² узлов на глубине 3 и т.д., до глубины h, на которой имеется как минимум 2t^h-1 узлов(пример такого дерева, высоты которого равна 3, показан на рисунке 1). Следовательно, число ключей n удовлетворяет следующему неравенству:

Простейшее преобразование дает неравенство t^h=<(n+1)/2. Теорема доказывается путем логарифмирования по основанию t обеих частей этого неравенства.

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

1. Корень либо является листом, либо имеет по крайней мере двух сыновей.

2. Каждый узел, за исключением корня и листьев, имеет от [ m/2] до m сыновей.

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

Каждое 2-3 дерево является Б-деревом порядка 3, т.е. 3-арным. На рисунке 3 показано Б-дерево порядка 5, здесь предполагается, что в блоке листа умещается не более трех записей.

Рисунок 3. Б-дерево порядка 5

Б-дерево можно рассматривать как иерархический индекс, каждый узел в котором занимает блок во внешней памяти. Корень Б-дерева является индексом первого уровня. Каждый нелистовой узел на Б-дереве имеет форму (p₀, k₁, p₁, k₂, p₂, …,, k_n, p_n), где p₁ является указателем на i-го сына, 0 =< i =< n, a k₁ – ключ, 1=< i =< n. Ключи в узле упорядочены, поэтому k₁ < k₂ < … < k_n. Все ключи в поддереве, на которое указывает p₀, меньше, чем k₁. В случае 1 =< i < n все ключи в поддереве, на которое указывает p₁, имеют значения, не меньше, чем k_i, и меньше, чем k_i+1. Все ключи в поддереве, на которое указывает p_n, имеют значения, не меньше, чем k_n. Считаем, то записи основного файла хранятся только в листьях.