B-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''B-дерево''' — дерево поиска, впервые предложенное Р. Бэйером и Е. МакКрейтом в 1970 году. B-де…»)
(нет различий)

Версия 03:38, 5 марта 2011

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

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

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

Назначение

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

Поиск ключа

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

Добавление ключа