B-дерево
Материал из Википедии — свободной энциклопедии
 |
Для улучшения этой статьи желательно?:
|
B-дерево (по-русски произносится как Б-дерево) — с точки зрения внешнего логического представления, сбалансированное сильно ветвистое дерево во внешней памяти.
Использование B-деревьев впервые было предложено Р. Бэйером и Е. МакРейтом в 1970.
Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же.
Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
Дерево характеризуют степенью t:
- В вершине может быть максимум 2t-1 и минимум t-1 элементов, за исключением корня.
- Вершина содержащая n элементов имеет n+1 потомков или является терминальной(листовой).
Содержание |
[править] Поиск
Поиск в B-дереве — это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной lognm. Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.
[править] Основные достоинства В-дерева
- Во всех случаях полезное использование пространства вторичной памяти занимает свыше 50%. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
- Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
- В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
- Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.
Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных по вторичному ключу.
[править] Ссылки
- http://www.unix.org.ua/osbd/glava_39.htm
- http://algolist.manual.ru/ds/s_btr.php
- Визуализаторы В-деревьев
- 2-3 дерево - частный случай B-дерева
- R-дерево - обобщение B-дерева на многомерный случай
[править] Литература
- Ананий В. Левитин Глава 7. Пространственно-временной компромисс: B-деревья // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 331-339. — ISBN 0-201-74395-7
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
 |
Это незавершённая статья о программировании. Вы можете помочь проекту, исправив и дополнив её. |
