B-дерево

Материал из Википедии — свободной энциклопедии

Для улучшения статьи желательно^?:

Переработать оформление в соответствии с правилами написания статей

Пример B-дерева.

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

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

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

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

[править] Ссылки

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