В-деревья

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

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

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

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

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

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

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

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

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

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

 

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

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

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

Поиск

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








Дата добавления: 2014-12-02; просмотров: 984;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.