В-деревья

В-дерево - это структура, очень широко применяемая для поиска данных на внешнем носителе. Ее используют практически все существующие системы управления базами данных.

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

- каждый узел имеет не более m сыновей

- каждый узел имеет не менее m/2 сыновей

- корень, если он не лист, имеет не менее двух сыновей.

- все листья расположены на одном уровне

- узел, имеющий n сыновей, содержит n-1 ключей. Ключи расположены в узле в возрастающем порядке.

Рис.47 В-дерево

На рис 47. изображено В-дерево порядка 5 . Связи как бы вставлены между ключами так, что указатель p_i указывает на поддерево с ключами К, такими, что K_i-1 < K < K_i . Узел, содержащий n ключей и n+1 указателей можно представить как на рис. 48.

Рис.48 Узел В-дерева

Для В-дерева существует обобщение обратного обхода: сначала проходим поддерево, исходящее из P₀, затем ключ К₁, разделя­ющий поддеревья, исходящие из Р₀ и Р_1, затем поддерево, исходящее из Р_1, и так далее. Для дерева на рис. 47 обратный обход дает последовательность:

19 26 35 38 39 41 44 48 62 78 88 99.

Таким образом, обратный обход В-дерева дает сортированную последо­ва­тельность. Рассмотрим операции поиска, вставки и удаления.

Поиск

Начиная с корня, ищем ключ К среди ключей узла. Если поиск удачен, то операция завершается. Если же поиск неудачен, и нужный ключ имеет значение между K_i и K_i+1, спускаемся вниз по связи P_i и повторяем процесс. В конце концов, алгоритм либо найдет ключ, либо выйдет на пустую связь, что означает, что искомого ключа в дереве нет.