B+-дерево

Поделись знанием:
(перенаправлено с «B+-деревья»)
Перейти к: навигация, поиск

B+-дерево — структура данных на основе B-дерева, сбалансированное <math>n</math>-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B+-дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.

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

Вариант B-дерева, в котором все значения сохранялись в листовых узлах, систематически рассмотрен в 1979 году[1], притом отмечено, что такие структуры использовались IBM в технологии файлового доступа для мейнфреймов VSAM[en] по крайней мере с 1973 года.

Структура широко применяется в файловых системах — NTFS, ReiserFS, NSS, XFS, JFS, ReFS и BFS используют этот тип дерева для индексирования метаданных; BeFS также использует B+-деревья для хранения каталогов. Реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle Database (начиная с версии 8), Adaptive Server Enterprise и SQLite поддерживают этот тип деревьев для табличных индексов. Среди NoSQL-СУБД, работающих с моделью «ключ—значение», структура данных реализована для доступа к данным в CouchDB и Tokyo Cabinet[en].





Описание

B+-деревом называется сбалансированное <math>n</math>-арное дерево поиска порядка <math>t</math>, удовлетворяющее следующим свойствам:

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

Построение

Построение B+-дерева может требовать перестройки промежуточной структуры, это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от <math>t</math> до <math>2t</math>, где <math>t</math> — степень (или порядок) дерева. При попытке вставить в узел (<math>2t+1</math>)-й ключ возникает необходимость разделить этот узел, в качестве ключа-разделителя сформированных ветвей выступает (<math display="inline">t+1</math>)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+-дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей <math>k</math>. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

Свойства структуры

  • В B+-дереве легко реализуется независимость программы от структуры информационной записи.
  • Поиск обязательно заканчивается в листе.
  • Удаление ключа имеет преимущество — удаление всегда происходит из листа.
  • Другие операции выполняются аналогично B-деревьям.
  • B+-деревья требуют больше памяти для представления, чем классические B-деревья.
  • B+-деревья имеют возможность последовательного доступа к ключам.

Основные операции над структурой

Поиск

Корень B+-дерева является отправной точкой для всего спектра значений, в котором каждый внутренний узел представляет собой подинтервал.

Например, пусть необходимо найти значение ключа <math>k</math> в B+-дереве. Для этого ищется листовой узел, содержащий значение <math>k</math>. В каждом внутреннем узле нужно выяснить, на какой последующий дочерний узел необходимо следовать, внутренний узел B+-дерева имеет не более <math>t</math> потомков, где каждый из них представляет собой отдельный подынтервал. Выбирается соответствующий узел с помощью поиска в ключевых значениях узла:

Function: search (k)
 return tree_search (k, root);

Function: tree_search (k, node)
   if node is a leaf then
     return node;
   switch k do
     case k < k[0]
       return tree_search(k, p[0]);
     case k[i] ≤ k < k[i + 1]
       return tree_search(k, p[i + 1]);
     case k[d] ≤ k
       return tree_search(k, p[d + 1]);

(Данный псевдокод рассчитан на то, что дубликаты игнорируются.)

Добавление

Для добавления нового ключа или новой записи в первую очередь необходимо найти узел, в который их необходимо добавить. В этом случае алгоритм таков:

  • Если узел полностью не заполнен (количество элементов после вставки не более чем <math>t-1</math>), то добавить ключ (запись).
  • В противном случае необходимо расщепить узел:
    • создать новый узел, затем переместить половину элементов из текущего в новый;
    • добавить наименьший ключ из нового узла и адрес на него (узел) в родительский;
    • если родительский узел заполнен, аналогично разделить его:
      • добавить средний ключ в родительский узел;
    • повторять, пока родительский узел не будет нуждаться в расщеплении.
  • Если расщепляется корень — создать новый корень, имеющий один ключ и два указателя (ключ, который добавляется к корню, удаляется из своего узла)

B-деревья, в отличие от B±деревьев, расширяются со стороны корня, а не листьев.

Удаление

Для удаления ключа или записи в первую очередь необходимо найти листовой узел, в котором они находятся. Алгоритм удаления от листового узла:

  • Если узел хотя бы наполовину заполнен — завершение алгоритма;
  • Если узел имеет меньше элементов, то:
    • выполнить попытку перераспределения элементов, то есть добавить в узел элемент из «брата» — элемента с общим предком.
    • если выполнить перераспределение не удалось, объединить узел с «братом».
  • Если произошло объединение, удалить ключ или запись, которые указывают на удалённый узел или его «брата» с родительского узла.

Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева.

Вычислительная сложность операций

Вычислительная сложность каждой операции в худшем случае: <math>O(\log \frac{t}{2n})</math>, где <math>t</math> — порядок дерева или коэффициент ветвления; <math>n</math> — количество элементов в дереве ветвей в узлах дерева.

Напишите отзыв о статье "B+-дерево"

Примечания

  1. Douglas Comer [wwwold.cs.umd.edu/class/fall2002/cmsc818s/Readings/b-tree.pdf The Ubiquitous B-Tree] (англ.) // ACM Computing Surveys. — 1979. — June (vol. 11, no. 2). — P. 121-137. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0360-0300&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0360-0300].

Литература

  • Зубов В. С., Шевченко И. В. Глава 6. Поиск в недвоичных деревьях - B-деревьях // Структуры и методы обработки данных. Практикум в среде Delphi. — Филинъ, 2004. — С. 144-164. — ISBN 5-9216-0053-9.
  • Дональд Кнут. 4. Генерация всех деревьев. История комбинаторной генерации // Искусство программирования = The Art of Computer Programming. — М.: «Вильямс», 2007. — Т. 4. — С. 160. — ISBN 0-321-33570-8.

Ссылки

  • Визуализатор B+ дерева — [www.cs.usfca.edu/~galles/visualization/BPlusTree.html B+ Tree Visualization]


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

– Едешь? – И он опять стал писать.
– Пришел проститься.
– Целуй сюда, – он показал щеку, – спасибо, спасибо!
– За что вы меня благодарите?
– За то, что не просрочиваешь, за бабью юбку не держишься. Служба прежде всего. Спасибо, спасибо! – И он продолжал писать, так что брызги летели с трещавшего пера. – Ежели нужно сказать что, говори. Эти два дела могу делать вместе, – прибавил он.
– О жене… Мне и так совестно, что я вам ее на руки оставляю…
– Что врешь? Говори, что нужно.
– Когда жене будет время родить, пошлите в Москву за акушером… Чтоб он тут был.
Старый князь остановился и, как бы не понимая, уставился строгими глазами на сына.
– Я знаю, что никто помочь не может, коли натура не поможет, – говорил князь Андрей, видимо смущенный. – Я согласен, что и из миллиона случаев один бывает несчастный, но это ее и моя фантазия. Ей наговорили, она во сне видела, и она боится.
– Гм… гм… – проговорил про себя старый князь, продолжая дописывать. – Сделаю.
Он расчеркнул подпись, вдруг быстро повернулся к сыну и засмеялся.
– Плохо дело, а?
– Что плохо, батюшка?
– Жена! – коротко и значительно сказал старый князь.
– Я не понимаю, – сказал князь Андрей.
– Да нечего делать, дружок, – сказал князь, – они все такие, не разженишься. Ты не бойся; никому не скажу; а ты сам знаешь.
Он схватил его за руку своею костлявою маленькою кистью, потряс ее, взглянул прямо в лицо сына своими быстрыми глазами, которые, как казалось, насквозь видели человека, и опять засмеялся своим холодным смехом.
Сын вздохнул, признаваясь этим вздохом в том, что отец понял его. Старик, продолжая складывать и печатать письма, с своею привычною быстротой, схватывал и бросал сургуч, печать и бумагу.
– Что делать? Красива! Я всё сделаю. Ты будь покоен, – говорил он отрывисто во время печатания.
Андрей молчал: ему и приятно и неприятно было, что отец понял его. Старик встал и подал письмо сыну.
– Слушай, – сказал он, – о жене не заботься: что возможно сделать, то будет сделано. Теперь слушай: письмо Михайлу Иларионовичу отдай. Я пишу, чтоб он тебя в хорошие места употреблял и долго адъютантом не держал: скверная должность! Скажи ты ему, что я его помню и люблю. Да напиши, как он тебя примет. Коли хорош будет, служи. Николая Андреича Болконского сын из милости служить ни у кого не будет. Ну, теперь поди сюда.
Он говорил такою скороговоркой, что не доканчивал половины слов, но сын привык понимать его. Он подвел сына к бюро, откинул крышку, выдвинул ящик и вынул исписанную его крупным, длинным и сжатым почерком тетрадь.
– Должно быть, мне прежде тебя умереть. Знай, тут мои записки, их государю передать после моей смерти. Теперь здесь – вот ломбардный билет и письмо: это премия тому, кто напишет историю суворовских войн. Переслать в академию. Здесь мои ремарки, после меня читай для себя, найдешь пользу.
Андрей не сказал отцу, что, верно, он проживет еще долго. Он понимал, что этого говорить не нужно.
– Всё исполню, батюшка, – сказал он.
– Ну, теперь прощай! – Он дал поцеловать сыну свою руку и обнял его. – Помни одно, князь Андрей: коли тебя убьют, мне старику больно будет… – Он неожиданно замолчал и вдруг крикливым голосом продолжал: – а коли узнаю, что ты повел себя не как сын Николая Болконского, мне будет… стыдно! – взвизгнул он.
– Этого вы могли бы не говорить мне, батюшка, – улыбаясь, сказал сын.
Старик замолчал.
– Еще я хотел просить вас, – продолжал князь Андрей, – ежели меня убьют и ежели у меня будет сын, не отпускайте его от себя, как я вам вчера говорил, чтоб он вырос у вас… пожалуйста.
– Жене не отдавать? – сказал старик и засмеялся.
Они молча стояли друг против друга. Быстрые глаза старика прямо были устремлены в глаза сына. Что то дрогнуло в нижней части лица старого князя.
– Простились… ступай! – вдруг сказал он. – Ступай! – закричал он сердитым и громким голосом, отворяя дверь кабинета.
– Что такое, что? – спрашивали княгиня и княжна, увидев князя Андрея и на минуту высунувшуюся фигуру кричавшего сердитым голосом старика в белом халате, без парика и в стариковских очках.
Князь Андрей вздохнул и ничего не ответил.
– Ну, – сказал он, обратившись к жене.
И это «ну» звучало холодною насмешкой, как будто он говорил: «теперь проделывайте вы ваши штуки».
– Andre, deja! [Андрей, уже!] – сказала маленькая княгиня, бледнея и со страхом глядя на мужа.
Он обнял ее. Она вскрикнула и без чувств упала на его плечо.
Он осторожно отвел плечо, на котором она лежала, заглянул в ее лицо и бережно посадил ее на кресло.
– Adieu, Marieie, [Прощай, Маша,] – сказал он тихо сестре, поцеловался с нею рука в руку и скорыми шагами вышел из комнаты.
Княгиня лежала в кресле, m lle Бурьен терла ей виски. Княжна Марья, поддерживая невестку, с заплаканными прекрасными глазами, всё еще смотрела в дверь, в которую вышел князь Андрей, и крестила его. Из кабинета слышны были, как выстрелы, часто повторяемые сердитые звуки стариковского сморкания. Только что князь Андрей вышел, дверь кабинета быстро отворилась и выглянула строгая фигура старика в белом халате.
– Уехал? Ну и хорошо! – сказал он, сердито посмотрев на бесчувственную маленькую княгиню, укоризненно покачал головою и захлопнул дверь.



В октябре 1805 года русские войска занимали села и города эрцгерцогства Австрийского, и еще новые полки приходили из России и, отягощая постоем жителей, располагались у крепости Браунау. В Браунау была главная квартира главнокомандующего Кутузова.
11 го октября 1805 года один из только что пришедших к Браунау пехотных полков, ожидая смотра главнокомандующего, стоял в полумиле от города. Несмотря на нерусскую местность и обстановку (фруктовые сады, каменные ограды, черепичные крыши, горы, видневшиеся вдали), на нерусский народ, c любопытством смотревший на солдат, полк имел точно такой же вид, какой имел всякий русский полк, готовившийся к смотру где нибудь в середине России.
С вечера, на последнем переходе, был получен приказ, что главнокомандующий будет смотреть полк на походе. Хотя слова приказа и показались неясны полковому командиру, и возник вопрос, как разуметь слова приказа: в походной форме или нет? в совете батальонных командиров было решено представить полк в парадной форме на том основании, что всегда лучше перекланяться, чем не докланяться. И солдаты, после тридцативерстного перехода, не смыкали глаз, всю ночь чинились, чистились; адъютанты и ротные рассчитывали, отчисляли; и к утру полк, вместо растянутой беспорядочной толпы, какою он был накануне на последнем переходе, представлял стройную массу 2 000 людей, из которых каждый знал свое место, свое дело и из которых на каждом каждая пуговка и ремешок были на своем месте и блестели чистотой. Не только наружное было исправно, но ежели бы угодно было главнокомандующему заглянуть под мундиры, то на каждом он увидел бы одинаково чистую рубаху и в каждом ранце нашел бы узаконенное число вещей, «шильце и мыльце», как говорят солдаты. Было только одно обстоятельство, насчет которого никто не мог быть спокоен. Это была обувь. Больше чем у половины людей сапоги были разбиты. Но недостаток этот происходил не от вины полкового командира, так как, несмотря на неоднократные требования, ему не был отпущен товар от австрийского ведомства, а полк прошел тысячу верст.