B-дерево

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

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

Сбалансированность означает, что длина любых двух путей от корня до листьев совпадает.

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

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

Применение

Структура B-дерева применяется для организации индексов во многих современных СУБД.

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

Относительно простая реализация алгоритмов и существование готовых библиотек (в том числе для C) для работы со структурой B-дерева обеспечивают популярность применения такой организации памяти в самых разнообразных программах, работающих с большими объёмами данных.

Структура и принципы построения

B-деревом называется дерево, удовлетворяющее следующим свойствам:

1. Каждый узел содержит хотя бы один ключ. Ключи в каждом узле упорядочены. Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила. Здесь t — параметр дерева, не меньший 2 (и обычно принимающий значения от 50 до 2000).
2. У листьев потомков нет. Любой другой узел, содержащий ключи <math>K_1</math>, ..., <math>K_n</math>, содержит <math>n+1</math> потомков. При этом
   1. Первый потомок и все его потомки содержат ключи из интервала <math>(-\infty, K_1)</math>
   2. Для <math>2\le i\le n</math>, i-й потомок и все его потомки содержат ключи из интервала <math>(K_{i-1}, K_i)</math>
   3. <math>(n+1)</math>-й потомок и все его потомки содержат ключи из интервала <math>(K_n, \infty)</math>
3. Глубина всех листьев одинакова.

Свойство 2 можно сформулировать иначе: каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на потомков.

Поиск

Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему потомку. Повторяем, пока не дошли до листа.

Добавление ключа

Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.

Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше <math>2t-1</math>, но не меньше <math>t-1</math>, ключей.

1. Если х — не лист,
   1. Определяем интервал, где должен находиться K. Пусть y — соответствующий потомок.
   2. Рекурсивно добавляем K к дереву потомков y.
   3. Если узел y полон, то есть содержит <math>2t-1</math> ключей, расщепляем его на два. Узел <math>y_1</math> получает первые <math>t-1</math> из ключей y и первые <math>t</math> его потомков, а узел <math>y_2</math> — последние <math>t-1</math> из ключей y и последние <math>t</math> его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы <math>y_1</math> и <math>y_2</math>.
2. Если x — лист, просто добавляем туда ключ K.

Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.

1. Добавим K к дереву потомков R.
2. Если R содержит теперь <math>2t-1</math> ключей, расщепляем его на два. Узел <math>R_1</math> получает первые <math>t-1</math> из ключей R и первые <math>t</math> его потомков, а узел <math>R_2</math> — последние <math>t-1</math> из ключей R и последние <math>t</math> его потомков. Медианный из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы <math>R_1</math> и <math>R_2</math> становятся его потомками.

Удаление ключа

Если корень одновременно является листом, то есть в дереве всего один узел, мы просто удаляем ключ из этого узла. В противном случае сначала находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел — <math>x</math>.

Если <math>x</math> — лист, удаляем оттуда ключ. Если в узле <math>x</math> осталось не меньше <math>t-1</math> ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле. Если следующий узел есть, и в нём не менее <math>t</math> ключей, мы добавляем в <math>x</math> ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся. Если это не так, но есть предыдущий узел, и в нём не менее <math>t</math> ключей, мы добавляем в <math>x</math> ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел <math>x</math> со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только <math>t-2</math> ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до <math>t-1</math> ключей, делать ничего не надо, потому что корень может иметь и меньше <math>t-1</math> ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.

Если <math>x</math> — не лист, а K — его <math>i</math>-й ключ, удаляем самый правый ключ из поддерева потомков <math>i</math>-го потомка <math>x</math>, или, наоборот, самый левый ключ из поддерева потомков <math>i+1</math>-го потомка <math>x</math>. После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.

Основные достоинства

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

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

См. также

• B+-деревья
• 2-3-дерево
• R-дерево
• B*-дерево

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 515­—536. — ISBN 0-07-013151-1.

Ссылки

• www.unix.org.ua/osbd/glava_39.htm
• algolist.manual.ru/ds/s_btr.php
• [rain.ifmo.ru/cat/view.php/vis/trees Визуализаторы В-деревьев]
• видео: [www.youtube.com/watch?v=WXXetwePSRk B-дерево - объяснение алгоритма заполнения дерева]

Отрывок, характеризующий B-дерево

С этого дня, во время всего дальнейшего путешествия Ростовых, на всех отдыхах и ночлегах, Наташа не отходила от раненого Болконского, и доктор должен был признаться, что он не ожидал от девицы ни такой твердости, ни такого искусства ходить за раненым.
Как ни страшна казалась для графини мысль, что князь Андрей мог (весьма вероятно, по словам доктора) умереть во время дороги на руках ее дочери, она не могла противиться Наташе. Хотя вследствие теперь установившегося сближения между раненым князем Андреем и Наташей приходило в голову, что в случае выздоровления прежние отношения жениха и невесты будут возобновлены, никто, еще менее Наташа и князь Андрей, не говорил об этом: нерешенный, висящий вопрос жизни или смерти не только над Болконским, но над Россией заслонял все другие предположения.


Пьер проснулся 3 го сентября поздно. Голова его болела, платье, в котором он спал не раздеваясь, тяготило его тело, и на душе было смутное сознание чего то постыдного, совершенного накануне; это постыдное был вчерашний разговор с капитаном Рамбалем.
Часы показывали одиннадцать, но на дворе казалось особенно пасмурно. Пьер встал, протер глаза и, увидав пистолет с вырезным ложем, который Герасим положил опять на письменный стол, Пьер вспомнил то, где он находился и что ему предстояло именно в нынешний день.
«Уж не опоздал ли я? – подумал Пьер. – Нет, вероятно, он сделает свой въезд в Москву не ранее двенадцати». Пьер не позволял себе размышлять о том, что ему предстояло, но торопился поскорее действовать.
Оправив на себе платье, Пьер взял в руки пистолет и сбирался уже идти. Но тут ему в первый раз пришла мысль о том, каким образом, не в руке же, по улице нести ему это оружие. Даже и под широким кафтаном трудно было спрятать большой пистолет. Ни за поясом, ни под мышкой нельзя было поместить его незаметным. Кроме того, пистолет был разряжен, а Пьер не успел зарядить его. «Все равно, кинжал», – сказал себе Пьер, хотя он не раз, обсуживая исполнение своего намерения, решал сам с собою, что главная ошибка студента в 1809 году состояла в том, что он хотел убить Наполеона кинжалом. Но, как будто главная цель Пьера состояла не в том, чтобы исполнить задуманное дело, а в том, чтобы показать самому себе, что не отрекается от своего намерения и делает все для исполнения его, Пьер поспешно взял купленный им у Сухаревой башни вместе с пистолетом тупой зазубренный кинжал в зеленых ножнах и спрятал его под жилет.
Подпоясав кафтан и надвинув шапку, Пьер, стараясь не шуметь и не встретить капитана, прошел по коридору и вышел на улицу.
Тот пожар, на который так равнодушно смотрел он накануне вечером, за ночь значительно увеличился. Москва горела уже с разных сторон. Горели в одно и то же время Каретный ряд, Замоскворечье, Гостиный двор, Поварская, барки на Москве реке и дровяной рынок у Дорогомиловского моста.
Путь Пьера лежал через переулки на Поварскую и оттуда на Арбат, к Николе Явленному, у которого он в воображении своем давно определил место, на котором должно быть совершено его дело. У большей части домов были заперты ворота и ставни. Улицы и переулки были пустынны. В воздухе пахло гарью и дымом. Изредка встречались русские с беспокойно робкими лицами и французы с негородским, лагерным видом, шедшие по серединам улиц. И те и другие с удивлением смотрели на Пьера. Кроме большого роста и толщины, кроме странного мрачно сосредоточенного и страдальческого выражения лица и всей фигуры, русские присматривались к Пьеру, потому что не понимали, к какому сословию мог принадлежать этот человек. Французы же с удивлением провожали его глазами, в особенности потому, что Пьер, противно всем другим русским, испуганно или любопытна смотревшим на французов, не обращал на них никакого внимания. У ворот одного дома три француза, толковавшие что то не понимавшим их русским людям, остановили Пьера, спрашивая, не знает ли он по французски?
Пьер отрицательно покачал головой и пошел дальше. В другом переулке на него крикнул часовой, стоявший у зеленого ящика, и Пьер только на повторенный грозный крик и звук ружья, взятого часовым на руку, понял, что он должен был обойти другой стороной улицы. Он ничего не слышал и не видел вокруг себя. Он, как что то страшное и чуждое ему, с поспешностью и ужасом нес в себе свое намерение, боясь – наученный опытом прошлой ночи – как нибудь растерять его. Но Пьеру не суждено было донести в целости свое настроение до того места, куда он направлялся. Кроме того, ежели бы даже он и не был ничем задержан на пути, намерение его не могло быть исполнено уже потому, что Наполеон тому назад более четырех часов проехал из Дорогомиловского предместья через Арбат в Кремль и теперь в самом мрачном расположении духа сидел в царском кабинете кремлевского дворца и отдавал подробные, обстоятельные приказания о мерах, которые немедленно должны были бытт, приняты для тушения пожара, предупреждения мародерства и успокоения жителей. Но Пьер не знал этого; он, весь поглощенный предстоящим, мучился, как мучаются люди, упрямо предпринявшие дело невозможное – не по трудностям, но по несвойственности дела с своей природой; он мучился страхом того, что он ослабеет в решительную минуту и, вследствие того, потеряет уважение к себе.
Он хотя ничего не видел и не слышал вокруг себя, но инстинктом соображал дорогу и не ошибался переулками, выводившими его на Поварскую.
По мере того как Пьер приближался к Поварской, дым становился сильнее и сильнее, становилось даже тепло от огня пожара. Изредка взвивались огненные языка из за крыш домов. Больше народу встречалось на улицах, и народ этот был тревожнее. Но Пьер, хотя и чувствовал, что что то такое необыкновенное творилось вокруг него, не отдавал себе отчета о том, что он подходил к пожару. Проходя по тропинке, шедшей по большому незастроенному месту, примыкавшему одной стороной к Поварской, другой к садам дома князя Грузинского, Пьер вдруг услыхал подле самого себя отчаянный плач женщины. Он остановился, как бы пробудившись от сна, и поднял голову.
В стороне от тропинки, на засохшей пыльной траве, были свалены кучей домашние пожитки: перины, самовар, образа и сундуки. На земле подле сундуков сидела немолодая худая женщина, с длинными высунувшимися верхними зубами, одетая в черный салоп и чепчик. Женщина эта, качаясь и приговаривая что то, надрываясь плакала. Две девочки, от десяти до двенадцати лет, одетые в грязные коротенькие платьица и салопчики, с выражением недоумения на бледных, испуганных лицах, смотрели на мать. Меньшой мальчик, лет семи, в чуйке и в чужом огромном картузе, плакал на руках старухи няньки. Босоногая грязная девка сидела на сундуке и, распустив белесую косу, обдергивала опаленные волосы, принюхиваясь к ним. Муж, невысокий сутуловатый человек в вицмундире, с колесообразными бакенбардочками и гладкими височками, видневшимися из под прямо надетого картуза, с неподвижным лицом раздвигал сундуки, поставленные один на другом, и вытаскивал из под них какие то одеяния.
Женщина почти бросилась к ногам Пьера, когда она увидала его.
– Батюшки родимые, христиане православные, спасите, помогите, голубчик!.. кто нибудь помогите, – выговаривала она сквозь рыдания. – Девочку!.. Дочь!.. Дочь мою меньшую оставили!.. Сгорела! О о оо! для того я тебя леле… О о оо!
– Полно, Марья Николаевна, – тихим голосом обратился муж к жене, очевидно, для того только, чтобы оправдаться пред посторонним человеком. – Должно, сестрица унесла, а то больше где же быть? – прибавил он.
– Истукан! Злодей! – злобно закричала женщина, вдруг прекратив плач. – Сердца в тебе нет, свое детище не жалеешь. Другой бы из огня достал. А это истукан, а не человек, не отец. Вы благородный человек, – скороговоркой, всхлипывая, обратилась женщина к Пьеру. – Загорелось рядом, – бросило к нам. Девка закричала: горит! Бросились собирать. В чем были, в том и выскочили… Вот что захватили… Божье благословенье да приданую постель, а то все пропало. Хвать детей, Катечки нет. О, господи! О о о! – и опять она зарыдала. – Дитятко мое милое, сгорело! сгорело!