39
правок
Изменения
Новая страница: «'''B-дерево''' — дерево поиска, впервые предложенное Р. Бэйером и Е. МакКрейтом в 1970 году. B-де…»
'''B-дерево''' — дерево поиска, впервые предложенное Р. Бэйером и Е. МакКрейтом в 1970 году.
B-дерево является сбалансированным, то есть глубина всех его листьев одинакова.
Каждый узел B-дерева, кроме корня, содержит от <tex>t - 1</tex> до <tex>2t - 1</tex> ключей. Корень содержит от <tex>1</tex> до <tex>2t - 1</tex> ключей. <tex>t</tex> — параметр дерева, не меньший 2. Ключи в каждом узле упорядочены.
== Назначение ==
B-дерево предназначено для хранения информации на жёстком диске. Время произвольного доступа к жёсткому диску очень велико (миллисекунды), поэтому важно уменьшить количество узлов, просматриваемых при каждой операции, то есть высоту дерева, что достигается путём высокой ветвистости.
== Поиск ключа ==
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
== Добавление ключа ==
B-дерево является сбалансированным, то есть глубина всех его листьев одинакова.
Каждый узел B-дерева, кроме корня, содержит от <tex>t - 1</tex> до <tex>2t - 1</tex> ключей. Корень содержит от <tex>1</tex> до <tex>2t - 1</tex> ключей. <tex>t</tex> — параметр дерева, не меньший 2. Ключи в каждом узле упорядочены.
== Назначение ==
B-дерево предназначено для хранения информации на жёстком диске. Время произвольного доступа к жёсткому диску очень велико (миллисекунды), поэтому важно уменьшить количество узлов, просматриваемых при каждой операции, то есть высоту дерева, что достигается путём высокой ветвистости.
== Поиск ключа ==
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
== Добавление ключа ==
