B-дерево

B-дерево — дерево поиска, впервые предложенное Р. Бэйером и Е. МакКрейтом в 1970 году.

B-дерево является сбалансированным, то есть глубина всех его листьев одинакова.

Каждый узел B-дерева, кроме корня, содержит от [math]t - 1[/math] до [math]2t - 1[/math] ключей. Корень содержит от [math]1[/math] до [math]2t - 1[/math] ключей. [math]t[/math] — параметр дерева, не меньший 2. Ключи в каждом узле упорядочены.

Назначение

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

Поиск ключа

Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.