B-дерево

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск
Файл:B-tree-definition.png
Пример B-дерева, Степени 2.

B-дерево (по-русски произносится как Б-дерево) — с точки зрения внешнего логического представления, сбалансированное сильно ветвистое дерево во внешней памяти.

Использование B-деревьев впервые было предложено Р. Бэйером(R. Bayer) и Е. МакКрейтом(E. McCreight) в 1970.

Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же.

Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.

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

Содержание

Структура и Принцип построения B-Дерева

Принцип построения B-Дерева является развитием принципа построения бинарного дерева поиска. В отличие от бинарного дерева поиска, B-Дерево состоит из страниц. Каждая страница содержит ключи, упорядоченные по возрастанию; каждый ключ имеет двух потомков - "левого" и "правого", как в бинарном дереве поиска. "Правый" потомок ключа является в то же время "левым" потомком следующего ключа. Таким образом, если количество ключей на некоторой странице B-Дерева равно <math>l</math>, то эта страница имеет <math>l+1</math> потомков. Страницу B-Дерева можно рассматривать как упорядоченный список, в котором чередуются ключи и ссылки (указатели) на потомков.

Степень B-Дерева

Количество ключей, содержащихся на странице B-Дерева, не может быть произвольным; оно определяется степенью В-дерева. Каждая страница В-дерева степени <math>k</math> должна содержать от <math>k</math> до <math>2k</math> ключей, кроме корневой страницы, которая может содержать от <math>1</math> до <math>2k</math> ключей.

Поиск в В-дереве

Поиск в B-дереве — это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной <math>\log_n{m}</math>. Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.

Основные достоинства В-дерева

  • Во всех случаях полезное использование пространства вторичной памяти занимает свыше 50%. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
  • Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
  • В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
  • Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных по вторичному ключу.

См. также

Ссылки

Литература

  • Ананий В. Левитин. Глава 7. Пространственно-временной компромисс: B-деревья // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 331-339. — ISBN 0-201-74395-7
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 515­-536. — ISBN 0-07-013151-1


<span id="interwiki-de-ga" />ca:Arbre-B cs:B-strom de:B-Baum en:B-tree es:Árbol-B fa:درخت بی fr:Arbre B hr:B-stablo hu:B-fa it:B-Albero ja:B木 ko:B 트리 lt:B-medis pl:B-drzewo pt:Árvore B sr:Б-стабло sv:B-träd uk:Б-дерево zh:B树

Личные инструменты

Served in 0.121 secs.