В-Деревья

работы с дисковой памятью (и другими типами вторичной памяти с

непосредственным доступом).
В-деревья похожи на красно­черные деревья, но отличаются более высокой оптимизацией диско­вых операций ввода-вывода. Многие СУБД используют для хранения информации именно В-деревья (или их разновидности).
В-деревья отличаются от красно-черных деревьев тем, что узлы В-дерева могут иметь много дочерних узлов — до тысяч, так что степень ветвления В-дерева может быть очень большой.
В-деревья схожи с красно-черными деревьями в том, что все В-деревья с n узлами имеют высоту О (lg n), хотя само значение высоты В- дерева существенно меньше, чем у красно-черного дерева за счет более сильного ветвления. Таким образом, В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время О (lg n).

узел В- дерева содержит n [x] ключей, то у него

n [x] + 1 дочерних узлов.
Ключи в узле x используются как разделители диапазона ключей, с которыми имеет дело данный узел, на n [x] + 1 поддиапазонов, каждый из которых относится к одному из дочерних узлов x.
При поиске ключа в В-дереве мы выбираем один из n [x] + 1 дочерних узлов путем сравнения искомого значения с n [x] ключами узла х.
Структура листьев В-дерева отличается от структуры внутренних узлов;

и все они не могут одновременно разместиться в оперативной памяти.

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

зависит в первую очередь от количества выполняемых операций с диском

Disk_Read и Disk_Write, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа.

такое дерево может хранить более миллиарда ключей.
При этом, поскольку

корневой узел может храниться в оперативной памяти постоянно, для поиска ключа в этом дереве требуется максимум два обращения к диску!

поиска и красно-черных деревьев, что сопутствующая информация, связанная с ключом,

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

обладающее следующими свойствами.
Каждый узел x содержит следующие поля:
а) n [x], количество

ключей, хранящихся в настоящий момент в узле x.
б) Собственно ключи, количество которых равно n [x] и которые хранятся в невозрастающем порядке, так что кеу1 [x] ≤ кеу2 [x] ≤ • • • ≤ кеуn [x]
в) Логическое значение leaf [х], равное TRUE, если х является листом, и FALSE, если х — внутренний узел.

указателей с1 [х], с2 [х],…,cn [х] на дочерние узлы. Листья

не имеют дочерних узлов, так что их поля сi не определены.
Ключи кеуi [х] разделяют поддиапазоны ключей, хранящихся в поддеревьях: если кi — произвольный ключ, хранящийся в поддереве с корнем ci [х], то к1 ≤ кеу1 [x] ≤ к2≤ кеу2 [x] ≤ • • • ≤ кеуn [x] ≤ кеуn+1
Все листья расположены на одной и той же глубине, которая равна высоте дерева h.

в узле. Эти границы могут быть выражены с помощью одного

фиксированного целого числа t ≥ 2, называемого минимальной степенью (minimum degree) В-дерева:
A) Каждый узел, кроме корневого, должен содержать как минимум t - 1 ключей. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.
Б)Каждый узел содержит не более 2t — 1 ключей. Таким образом, внут­ренний узел имеет не более 21 дочерних узлов. Мы говорим, что узел заполнен (full), если он содержит ровно 2t — 1 ключей

внутренний узел может иметь 2, 3 или 4 дочерних узла,

и мы получаем так называемое 2-5- 4-дерево (2-3-4 trее).
Однако обычно на практике используются гораздо большие значения t.

с В-деревом, пропорционально его высоте.
Теорема: Высота В-дерева T c

n≥ 1 узлами и минимальной степенью t ≥ 2 не превышает logt (n + 1)/2.
Здесь мы видим преимущества В-деревьев над красно-черными деревьями. Хотя высота деревьев растет как О (lg n) в обоих случаях (t — константа), в случае В-деревьев основание логарифмов имеет гораздо большее значение.
Таким образом, В-деревья требуют исследования примерно в lg t раз меньшего количества узлов по сравнению с красно-черными деревьями.
Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.

бинарном дереве поиска, но с тем отличием, что если в

бинарном дереве поиска мы выбираем один из двух путей, то здесь предстоит сделать выбор из большего количества альтернатив, завися­щего от того, сколько дочерних узлов имеется у текущего узла. Точнее, в каждом внутреннем узле х нам предстоит выбрать один из т[х] + 1 дочерних узлов.
Операция B_Tree_Search представляет собой естественное обобщение процедуры Tree_Search. В качестве параметров процедура B_Tree_Search получает указатель на корневой узел х поддерева и ключ к, который следует найти в этом поддереве.
Таким образом, вызов верхнего уровня для поиска во всем дереве имеет вид B_Tree_ Search(root [Т], к).

пару (у, i), состоящую из узла у и индекса i,

такого что keyi [у] = к. В противном случае процедура вернет значение NIL.

B_TREE_SЕARCH (x, к)
i ← 1
while i ≤ n[x] и к > кеуi[х]
do i ← i + 1
if i ≤ n[x] и к = кеуi[х]
then return (х, i)
if leaf[x]
then return nil
else DlSK_READ(ci [x])
return B_Tree_Search(ci [x], к)

что к ≤ keyi [x] (иначе i присваивается значение n

[х] +1).
В строках 4-5 проверяется, не найден ли ключ в текущем узле, и если он найден, то выполняется его возврат.
В строках 6-9 процедура либо завершает свою работу неудачей (если х является листом), либо рекурсивно вызывает себя для поиска в соответствующем поддереве х (после выполнения чтения с диска необходимого дочернего узла, являющегося корнем исследуемого поддерева).
Процедура B_Tree_Search, как и процедура Tree_Search при поиске в бинарном дереве, проходит в процессе рекурсии узлы от корня в нисходящем порядке.
Количество дисковых страниц, к которым выполняется обращение процедурой B_Tree_Search, равно 0(h) = О (logt n), где h — высота В-дерева, а n — количество содержащихся в нем узлов.
Поскольку n [x] < 2t, количество итераций цикла while в строках 2-3 в каждом узле равно О (t), а общее время вычислений — О (th) = О (t logt n).

процедурой B_Tree_Create для создания пустого корневого узла, а затем вносить

в него новые ключи при помощи процедуры B_Tree_Insert.
В обеих этих процедурах используется вспомогательная процедура Allocate_Node, которая выделяет дисковую страницу для нового узла за время О (1).

x

в бинарное дерево поиска. Как и в случае бинарных деревьев

поиска, мы ищем позицию листа, в который будет вставлен новый ключ.
При работе с В-деревом мы не можем просто создать новый лист и вставить в него ключ, поскольку такое дере­во не будет являться корректным В-деревом.
Вместо этого мы вставляем новый ключ в существующий лист. Поскольку вставить новый ключ в заполненный лист невозможно, мы вводим новую операцию — разбиение (splitting) заполненного (т.е. содержащего 2t — 1 ключей) узла на два, каждый из которых содержит по t -1 ключей.
Медиана, или средний ключ, — keyt [у] (median key) — при этом перемещается в родительский узел, где становится разделительной точкой для двух вновь образовавшихся поддеревьев.

его также следует разбить, и такой процесс разбиения может идти

по восходящей до самого корня.
Как и в случае бинарного дерева поиска, в В-дереве мы вполне можем осуществить вставку за один нисходящий проход от корня к листу.
Для этого нам не надо выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. Вместо этого при проходе от корня к листьям в поисках позиции для нового ключа мы разбиваем все заполненные узлы, через которые проходим (включая лист).
Тем самым гарантируется, что если нам надо разбить какой-то узел, то его родительский узел не будет заполнен.

внутренний узел х (находящийся в оперативной памяти), индекс i и

узел у (также находящийся в оперативной памяти), такой что у = сi[x] является заполненным дочерним узлом х.
Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля х, внося в него информацию о новом дочернем узле.
Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можем исполь­зовать вызов B_Tree_Split_Child. При этом высота дерева увеличивается на 1.

—1
for j ← 1 to t — 1 do кеyj[z]

← keyj+t[y)
if not leaf[y]
then for j ← 1 to t do cj[z] ← cj+t[y]
n[y]← t - 1
for j ← n[x] + 1 downto i + 1 do cj+1[x] ← cj[x]
ci+1[x] ← z
for j ← n[x] downto i do keyj+1[x] ← keyj[x]
kеуi[х] ← keyt[y]
n[x] ← n[x] + 1
DlSK_WRITE(y ) DISK_WRITE(z) DlSK_WRITE(x)

является i-м дочерним узлом х и представляет собой именно тот

узел, который будет разбит на два.
Изначально узел у имеет 2t дочерних узла (содержит 2t — 1 ключей); после разбиения количество его дочерних узлов снизится до t (t — 1 ключей). Узел z получает t больших дочерних узлов (t — 1 ключей) у и становится новым дочерним узлом х, располагаясь непосредственно после у в таблице дочерних узлов х. Медиана у перемещается в узел х и разделяет в нем y и z.
В строках 1-8 создается узел z и в него переносятся большие t — 1 ключей и соответствующие t дочерних узлов у. В строке 9 обновляется поле количества ключей в у.
И наконец, строки 10-16 делают z дочерним узлом х, перенося медиану из у в ж для разделения у и z, и обновляют поле количества ключей в x. В строках 17-19 выполняется запись на диск всех модифицированных данных. Время работы процедуры равно θ (t) из-за циклов в строках 4-5 и 7-9 (прочие циклы выполняют О (t) итераций).

root[T]
2 if n[r] = 2t — 1
3 then

s ← Allocate_Node()
4 root[T] ← s
5 leaf[s] ← FALSE
6 n[s] ← 0
7 cj[s] ← r
8 B_Tree_Split_Child(s, 1, r)
9 B_Tree_Insert_Nonfull(s, k)
10 else B_Tree_Insert_Nonfull(r, k)

один нисходящий проход по дереву, требующий О (h) обращений к

диску. Необходимое процессорное время составляет О (th) = О (tlogf n).
Процедура B_Tree_Insert использует процедуру B_Tree_Split_Child для гарантии того, что рекурсия никогда не столкнется с заполненным узлом.
Строки 3-9 предназначены для случая, когда заполнен корень дерева: при этом корень разбивается и новый узел s (у которого два дочерних узла) становится новым корнем В-дерева.
Разбиение корня — единственный путь увеличения высоты В-дерева. В отличие от бинарных деревьев поиска, у В-деревьев высота увеличивается “сверху”, а не “снизу”.

ключа к в дерево с незаполненным корнем.
Данная процедура при

необходимости рекурсивно спускается вниз по дереву, причем каждый узел, в который она входит, является незаполненным, что обеспечивается (при необходимости) вызовом процедуры B_Tree_Split_Child.
Вспомогательная процедура B_Tree_Insert_Nonfull вставляет ключ к в узел x, который должен быть незаполненным при вызове процедуры.
Операции B_Tree_Insert и B_Tree_Insert_Nonfull гарантируют, что это условие незаполненности будет выполнено.

и к < кеу{ [x]

do keyi+1[x] ← кеу{[х]
i ← i — 1
keyi+1 [x] ← к
n[х] ← n[x] + 1
DlSK_WRITE(x)
else while i ≥1 и к < кеуi [х]
do i ← i — 1
i ← i + 1
Disk_Read(ci [x])
if n[cj[x]] = 2t — 1
then B_Tree_Split_Child(x, i, Ci(x))
if к > кеуi[x]
then i ← i + 1
B_Tree_Insert_Nonfull(c, [x] , к)

х является листом; при этом ключ к просто вставляется в

данный лист.
Если же х не является листом, то мы должны вставить к в подходящий лист в поддереве, корнем которого является внутренний узел х.
В этом случае строки 9-11 определяют дочерний узел х, в который спустится рекурсия.
В строке 13 проверяется, не заполнен ли этот дочерний узел, и если он заполнен, то вызывается процедура B_TREE_SPLIT_CHILD, которая разбивает его на два незаполненных узла, а строки 15-16 определяют, в какой из двух получившихся в результате разбиения узлов должна спуститься рекурсия.
Строки 13-16 гарантируют, что процеду­ра никогда не столкнется с заполненным узлом. Строка 17 рекурсивно вызывает процедуру B_TREE_lNSERT_NONFULL для вставки к в соответствующее поддерево.

h, составляет 0(h), поскольку между вызовами B_Tree_Insert_Nonfull выполняется только О

(1) операций Disk_Read и Disk_Write.
Необходимое процессорное время равно 0(th) = О (t logt n). Поскольку в B_Tree_Insert_Nonfull использована оконечная рекурсия, ее можно реализовать итеративно с помощью цикла while, наглядно показывающего, что количество страниц, которые должны находиться в оперативной памяти, в любой момент времени равно 0(1).

вставке, представляет собой более сложную задачу. Это связано с тем,

что ключ может быть удален из любого узла, а не только из листа, а удаление из внутреннего узла требует определенной перестройки дочерних узлов.
Как и в случае вставки, мы должны обеспечить, чтобы при выполнении операции удаления не были нарушены свойства В-дерева. Аналогично тому, как мы имели возможность убедиться, что узлы не слишком сильно заполнены для вставки нового ключа, нам предстоит убедиться, что узел не становится слишком мало заполнен в процессе удаления ключа (за исключением корневого узла, который может иметь менее t — 1 ключей, хотя и не может иметь более 2t — 1 ключей).

корнем которого является узел х. Эта процедура разработана таким образом,

что при ее рекурсивном вызове для узла х гарантировано наличие в этом узле по крайней мере t ключей.
Это условие требует наличия в узле большего количе­ства ключей, чем минимальное в обычном В-дереве, так что иногда ключ может быть перемещен в дочерний узел перед тем, как рекурсия обратится к этому дочернему узлу.
Такое ужесточение свойства В-дерева (наличие “запасного” ключа) дает нам возможность выполнить удаление ключа за один нисходящий проход по дереву (с единственным исключением, которое будет пояснено позже).
Следует также учесть, что если корень дерева х становится внутренним узлом, не содержащим ни одного ключа (такая ситуация может возникнуть в рассматриваемых ниже случаях 2в и 36), то узел х удаляется, а его единственный дочерний узел с1 [х] становится новым корнем дерева (при этом уменьшается высота В-дерева и сохраняется его свойство, требующее, чтобы корневой узел непустого дерева содержал как минимум один ключ).

листом — удаляем к из х.
Если узел к находится в

узле х и х является внутренним узлом, выполняем следующие действия.
а) Если дочерний по отношению к х узел у, предшествующий ключу к в узле х, содержит не менее t ключей, то находим к' — предшественника к в поддереве, корнем которого является у. Рекурсивно удаляем к' и заменяем к в х ключом к'. (Поиск ключа к' и удаление его можно выполнить в процессе одного нисходящего прохода.)
б) Ситуация, симметричная ситуации а: если дочерний по отношению к х узел 2, следующий за ключом к в узле х, содержит не менее t ключей, то находим к' — следующий за к ключ в поддереве, корнем которого является 2. Рекурсивно удаляем к' и заменяем к в х ключом к'. (Поиск ключа к' и удаление его можно выполнить в процессе одного нисходящего прохода.)
в) В противном случае, если и у, и z содержат по t — 1 ключей, вносим к и все ключи z в у (при этом из х удаляется к и указатель на 2, а узел у после этого содержит 2t — 1 ключей), а затем освобождаем 2 и рекурсивно удаляем к из у.

сi [х] поддерева, которое должно содержать к (если таковой ключ

имеется в данном В-дереве). Если сi [х] содержит только t — 1 ключей, выполняем шаг За или 36 для того, чтобы гарантировать, что далее мы переходим в узел, содержа­щий как минимум t ключей. Затем мы рекурсивно удаляем к из поддерева с корнем сi [х] .
а) Если сi [х] содержит только t — 1 ключей, но при этом один из ее непосредственных соседей (под которым мы понимаем дочерний по отношению к х узел, отделенный от рассматриваемого ровно одним ключом-разделителем) содержит как минимум t ключей, передадим в сi [х] ключ-разделитель между данным узлом и его непосредственным соседом из х, на его место поместим крайний ключ из соседнего узла и перенесем соответствующий указатель из соседнего узла в сi [х] .
б) Если и сi [х] и оба его непосредственных соседа содержат по t — 1 ключей, объединим сi [х] с одним из его соседей (при этом бывший ключ-разделитель из х станет медианой нового узла).

что на практике чаще всего удаления будут выполняться из листьев.

Процедура B_Tree_Delete в этом случае выполняется за один нисходящий проход по дереву, без возвратов.
При удалении ключа из внутреннего узла процедуре может потребоваться возврат к узлу, ключ из которого был удален и замещен его предшественником или последующим за ним ключом (случаи 2а и 26).
Хотя описание процедуры выглядит достаточно запутанным, она требует все­го лишь О (h) дисковых операций для дерева высотой h, поскольку между ре­курсивными вызовами процедуры выполняется только 0(1) вызовов процедур