B-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перемещение ключа)
м (rollbackEdits.php mass rollback)
 
(не показаны 54 промежуточные версии 8 участников)
Строка 1: Строка 1:
<wikitex>'''B-дерево''' сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-дерево с $n$ узлами имеет высоту $O(\log n)$. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\log n)$
+
'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
  
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.</wikitex>
+
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в <tex>1970</tex> году.
 
== Структура ==
 
== Структура ==
 
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
 
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
<wikitex>Каждый узел B-дерева, кроме корня, содержит от $t - 1$ до $2t - 1$ ключей. Корень содержит от $1$ до $2t - 1$ ключей. $t$ — параметр дерева, не меньший $2$. Каждый внутренний узел, не являющийся корневым, имеет,
+
B-дерево имеет следующие свойства (<tex>t</tex> — параметр дерева, называемый ''минимальной степенью'' B-дерева, не меньший <tex>2</tex>.):
таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. Ключи в каждом узле упорядочены. Назовём узел заполненным, если он содержит ровно $2t-1$ ключей.</wikitex>
+
* Каждый узел, кроме корня, содержит не менее <tex>t - 1</tex> ключей, и каждый внутренний узел имеет по меньшей мере <tex>t</tex> дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.  
 +
* Каждый узел, кроме корня, содержит не более <tex>2t - 1</tex> ключей и не более чем <tex>2t</tex> сыновей во внутренних узлах
 +
* Корень содержит от <tex>1</tex> до <tex>2t - 1</tex> ключей, если дерево не пусто и от <tex>2</tex> до <tex>2t</tex> детей при высоте большей <tex>0</tex>.
 +
* Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из отрезка <tex>[k_{i - 1}; k_i],\:  k_0 = -\infty,\: k_{n + 1} = \infty</tex>.
 +
* Ключи в каждом узле упорядочены по неубыванию.
 +
* Все листья находятся на одном уровне.
  
Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из отрезка <tex>[k_{i - 1}; k_i],\k_0 = -\infty,\: k_{n + 1} = \infty</tex>.
+
=== Структура узла ===
 +
'''struct''' Node
 +
    '''bool''' leaf <span style="color:#008000">   // является ли узел листом</span>
 +
    '''int'''  n <span style="color:#008000">     // количество ключей узла</span>
 +
    '''int'''  key[] <span style="color:#008000"> // ключи узла</span>
 +
    '''Node''' c[] <span style="color:#008000">    // указатели на детей узла</span>
 +
=== Структура дерева ===
 +
  '''struct''' BTree
 +
    '''int'''  t <span style="color:#008000">      // минимальная степень дерева</span>
 +
    '''Node''' root <span style="color:#008000">  // указатель на корень дерева</span>
  
 
== Назначение ==
 
== Назначение ==
B-деревья разработаны для использования на дисках (в файловых системах) или иных вторичных устройствах хранения информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья, но они лучше минимизируют количество операций чтения-записи в диске.
+
B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с <tex>n</tex> узлами имеют  высоту <tex>O(\log n)</tex>), но они лучше минимизируют количество операций чтения-записи с диском.
 +
== Структуры данных во внешней памяти ==
 +
Кроме оперативной памяти, в компьютере используется внешний носитель, как правило, представляющий собой магнитные диски (или твердотельный накопитель). Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания.
  
=== Использование во вторичной памяти ===
+
Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется  от <tex>2</tex> до <tex>16</tex> КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение и запись становятся полностью электронными процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.
<wikitex>Как известно, наряду с оперативной памятью (первичной памятью) в компьютере используется так называемая вторичная память, как правило, представляющая собой магнитные диски (или твердотельный накопитель).
 
  
Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо, гораздо медленнее оперативной памяти. Механическое движение головки относительно диска определяется двумя компонентами — перемещением головки по радиусу и вращением дисков. При скорости вращения 7200 оборотов в минуту один оборот требует примерно 8.33 мс, что почти на 5 порядков превышает время обращения к оперативной памяти (которое составляет примерно 100 нс). То есть, пока мы ждем оборота диска, чтобы считать необходимые нам данные, из оперативной памяти мы могли бы получить эти данные почти 100000 раз. В среднем приходится ждать только половину оборота диска, но это практически ничего не меняет. Радиальное перемещение головок тоже требует времени.
+
В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которые можно создавать.
Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется  от $2^{11}$ до $2^{14}$ Байт. После того, как головка позиционирована на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение/запись становится полностью электронным процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.
 
 
 
В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которыми можно управлять.
 
  
 
Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.  
 
Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.  
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей и $t=1001$, то поиск ключа займёт две дисковые операции. </wikitex>
+
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между <tex>50</tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и <tex>t=1001</tex>, то поиск ключа займёт две дисковые операции.  
  
 
== Высота ==
 
== Высота ==
<wikitex>Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.  
+
Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.  
{{Теорема|statement=Если $n \geqslant 1$, то для B-дерева $T$ c $n$ узлами и минимальной степенью $t \geqslant 2$ имеется следующее неравенство:
+
{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B-дерева <tex>T</tex> c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex> имеется следующее неравенство:
:$h \leqslant$ $\log_t\frac{n+1}{2}$
+
:<tex>h \leqslant</tex> <tex>\log_t\dfrac{n+1}{2}</tex>
 
|proof=
 
|proof=
Корень B-дерева $T$ содержит по меньшей мере один ключ, а все остальные узлы — хотя бы $t - 1$ ключей. Так, T, высота которого $h$, имеет хотя бы $2$ узла на глубине $1$, хотя бы $2t$ узла на глубине $2$, хотя бы $2t^2$ узла на глубине $3$, и так далее, до глубины $h$ оно имеет хотя бы $2t^{h-1}$ узлов. Так, число ключей $n$ удовлетворяет неравенству:
+
Корень B-дерева <tex>T</tex> содержит по меньшей мере один ключ, а все остальные узлы — хотя бы <tex>t - 1</tex> ключей. Так, <tex>T</tex>, высота которого <tex>h</tex>, имеет хотя бы <tex>2</tex> узла на глубине <tex>1</tex>, хотя бы <tex>2t</tex> узла на глубине <tex>2</tex>, хотя бы <tex>2t^2</tex> узла на глубине <tex>3</tex>, и так далее, до глубины <tex>h</tex>, оно имеет по меньшей мере <tex>2t^{h-1}</tex> узлов. Так, число ключей <tex>n</tex> удовлетворяет неравенству:
::$n \geqslant (1+t)\sum\limits_{i = 0}^h 2t^{i-1} $
+
::<tex>n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} </tex>
:::$=1+2(t-1)(\frac{t^h-1}{t-1})$
+
:::<tex>=1+2(t-1)(\dfrac{t^h-1}{t-1})</tex>
:::$=2t^h-1$.
+
:::<tex>=2t^h-1</tex>.
  
Простейшее преобразование дает нам неравенство $t^h \leqslant (n+1)/2$. Логарифмирование по основанию $t$ обеих частей неравенства доказывает теорему
+
Простейшее преобразование дает нам неравенство <tex>t^h \leqslant (n+1)/2</tex>. Логарифмирование по основанию <tex>t</tex> обеих частей неравенства доказывает теорему
 
}}  
 
}}  
  
Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как $O(\log t)$ в обоих случаях (вспомним, что t — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в $\log t$ раз меньшего количества узлов по сравнению с красно-черными деревьями. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.</wikitex>
+
Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как <tex>O(\log t)</tex> в обоих случаях (вспомним, что <tex>t</tex> — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в <tex>\log t</tex> раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.
 
 
 
== Операции ==
 
== Операции ==
 
B-деревья представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Однако, как уже было упомянуто выше, алгоритмы B-дерева созданы специально для работы с дисками (или другими носителями информации) и базами данных (или иными видами представления большого количества информация), минимизируя количество операций ввода-вывода.
 
B-деревья представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Однако, как уже было упомянуто выше, алгоритмы B-дерева созданы специально для работы с дисками (или другими носителями информации) и базами данных (или иными видами представления большого количества информация), минимизируя количество операций ввода-вывода.
Строка 43: Строка 54:
 
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
 
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
 
=== Добавление ключа ===
 
=== Добавление ключа ===
<wikitex>Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. Если и родительский узел заполнен заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
+
Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.  
 +
[[Файл:B3inssp.png|550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
 +
 
 +
Если и родительский узел заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
 
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
 
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
+
 
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_g n)$ процессорного времени.
+
 
  B-Tree-Insert(T, k)
+
Вставка ключа в B-дерево <tex>T</tex> высоты <tex>h</tex> за один нисходящий проход по дереву потребует <tex>O(h)</tex> обращений к диску и <tex>O(th)=O(t \log_t n)</tex> процессорного времени.
 +
 
 +
  '''void''' B-Tree-Insert(T: '''BTree''', k: '''int'''):
 
     r = T.root
 
     r = T.root
     if r.n == 2t - 1
+
     '''if''' r.n == 2T.t - 1
 
         s = Allocate-Node()
 
         s = Allocate-Node()
 
         T.root = s
 
         T.root = s
         s.leaf = FALSE
+
         s.leaf = ''false''
 
         s.n = 0
 
         s.n = 0
         s.$C_1$ = r
+
         s.c[1] = r
         B-Tree-Split-Child(s, 1)
+
         B-Tree-Split-Child(s, T.t, 1)
         B-Tree-Insert-Nonfull(s, k)
+
         B-Tree-Insert-Nonfull(s, k, T.t)
     else
+
     '''else'''
         B-Tree-Insert-Nonfull(r, k)
+
         B-Tree-Insert-Nonfull(r, k, T.t)
  
  B-Tree-Insert-Nonfull(x, k)
+
  '''void''' B-Tree-Insert-Nonfull(x: '''Node''', k: '''int''', t: '''int'''):
 
     i = x.n
 
     i = x.n
     if x.leaf
+
     '''if''' x.leaf
         while i $\geqslant$ 1 && k $<$ x.$key_i$
+
         '''while''' i >= 1 '''and''' k < x.key[i]
             x.$key_{i+1}$ = x.$key_i$
+
             x.key[i+1] = x.key[i]
 
             i = i - 1
 
             i = i - 1
     x.$key_{i+1}$ = k
+
     x.key[i+1] = k
 
     x.n = x.n + 1
 
     x.n = x.n + 1
 
     Disk-Write(x)
 
     Disk-Write(x)
     else  
+
     '''else'''
         while i $\geqslant$ 1 && k < x.$key_i$
+
         '''while''' i >= 1 '''and''' k < x.key[i]
 
             i = i - 1
 
             i = i - 1
 
         i = i + 1
 
         i = i + 1
         Disk-Read(x.$c_i$)
+
         Disk-Read(x.c[i])
         if x.$c_i$.n == 2t - 1
+
         '''if''' x.c[i].n == 2t - 1
             B-Tree-Split-Child(x, i)
+
             B-Tree-Split-Child(x, t, i)
             if k > x.$key_i$
+
             '''if''' k > x.key[i]
 
                 i = i + 1
 
                 i = i + 1
         B-Tree-Insert-Nonfull(x.$c_i$, k)
+
         B-Tree-Insert-Nonfull(x.c[i], k, t)
 +
 
 +
Функция <tex>\operatorname{B-Tree-Insert-Nonfull}</tex> вставляет ключ <tex>k</tex> в узел <tex>x</tex>, который должен быть незаполненным при вызове.
 +
Использование функции <tex>\operatorname{B-Tree-Split-Child}</tex> гарантирует, что рекурсия не встретится с заполненным узлом.
 +
Ниже показана вставка ключей <tex>B</tex>, <tex>Q</tex>, <tex>L</tex> и <tex>F</tex> в дерево с <tex>t = 3</tex>, т.е. узлы могут содержать не более <tex>5</tex> ключей
 +
[[Файл:B3insa.png|550px]]
  
Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове.
 
Использование функции $\operatorname{B-Tree-Split-Child}$ гарантирует, что рекурсия не встретится с заполненным узлом.
 
</wikitex>
 
  
 
=== Разбиение узла ===
 
=== Разбиение узла ===
[[Файл:B3splt.jpg|thumb|350px|Разбиение узла B-дерева с t=4]]<wikitex>Функция $\operatorname{B-Tree-Split-Child}$ получает в качестве входного параметра незаполненный внутренний узел $x$ (находящийся в оперативной памяти), индекс $t$ и узел $y$ (также находящийся в оперативной памяти), такой что $y = c_i[x]$ является заполненным дочерним узлом $x$. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля $x$, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на 1. Отметим, что увеличить высоту B-дерева можно только разбиением.
+
Функция <tex>\operatorname{B-Tree-Split-Child}</tex> получает в качестве входного параметра незаполненный внутренний узел <tex>x</tex> (находящийся в оперативной памяти), индекс <tex>t</tex> и узел <tex>y</tex> (также находящийся в оперативной памяти), такой что <tex>y = c_i[x]</tex> является заполненным дочерним узлом <tex>x</tex>. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля <tex>x</tex>, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на <tex>1</tex>. Отметим, что увеличить высоту B-дерева можно только разбиением.
 +
 
 +
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
  
  B-Tree-Split-Child(x, i)
+
  '''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):
 
     z = Allocate-Node()
 
     z = Allocate-Node()
     y = x.$C_i$
+
     y = x.c[i]
 
     z.leaf = y.leaf
 
     z.leaf = y.leaf
 
     z.n = t - 1
 
     z.n = t - 1
     for j = 1 to t - 1
+
     '''for''' j = 1 '''to''' t - 1
         z.$key_j$ = y.$key_{j+t}$
+
         z.key[j] = y.key[j+t]
     if not y.leaf
+
     '''if''' not y.leaf
         for j = 1 to t
+
         '''for''' j = 1 '''to''' t
             z.$c_j$ = y.$c_{j+t}$
+
             z.c[j] = y.c[j+t]
 
     y.n = t - 1
 
     y.n = t - 1
     for j = x.n + 1 downto i + 1
+
     '''for''' j = x.n + 1 '''to''' i + 1
         x.$C_{j+1}$ = x.$C_j$
+
         x.c[j+1] = x.c[j]
     $x.c_{i+1}$ = z
+
     x.c[i+1] = z
     for j = x.n downto i
+
     '''for''' j = x.n '''to''' i
         x.$key_{j+1}$ = x.$key_j$
+
         x.key[j+1] = x.key[j]
     x.$key_i$ = y.$key_t$
+
     x.key[i] = y.key[t]
 
     x.n = x.n + 1
 
     x.n = x.n + 1
 
     Disk-Write(y)
 
     Disk-Write(y)
 
     Disk-Write(z)
 
     Disk-Write(z)
 
     Disk-Write(x)
 
     Disk-Write(x)
</wikitex>
 
  
 
=== Удаление ключа ===
 
=== Удаление ключа ===
<wikitex>Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. $\geqslant t$) в нем, а также возможность провести удаление, не наружив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей $t-1$, производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже.
+
Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. <tex>\geqslant t</tex>) в нем, а также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей <tex>t-1</tex>, производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже.
Для удаления требуется время $O(t \log_t n)$ и $O(h)$ дисковых операций.</wikitex>
+
Для удаления требуется время <tex>O(t \log_t n)</tex> и <tex>O(h)</tex> дисковых операций.
 +
 
 
==== Удаление ключа из листа ====
 
==== Удаление ключа из листа ====
<wikitex>Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше $t - 1$, то просто удаляем ключ. В противном случае, если существует соседний лист с тем же родителем, который содержит больше $t - 1$ ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как $k_1$. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим $k_2$. Удалим из исходного узла лист, который нужно было удалить, спустим в этот узел $k_2$, а вместо $k_2$ в родительском узле поставим $k_1$. Если все соседи содержат по $t - 1$ ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.</wikitex>
+
Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <tex>t - 1</tex>, то просто удаляем ключ.  
 +
 
 +
[[Файл:B3dell.PNG|550px|Удаление <tex>F</tex> из листа]]
 +
В противном случае, если существует соседний лист с тем же родителем, который содержит больше <tex>t - 1</tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как <tex>k_1</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим <tex>k_2</tex>. Удалим из исходного узла ключ, который нужно было удалить, спустим в этот узел <tex>k_2</tex>, а вместо <tex>k_2</tex> в родительском узле поставим <tex>k_1</tex>. Если все соседи содержат по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.
 +
 
 
==== Удаление ключа из внутреннего узла ====
 
==== Удаление ключа из внутреннего узла ====
<wikitex>Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $x$ и ключ, который нужно удалить, $k$. Если дочерний узел, предшествующий ключу $k$, содержит больше $t - 1$ ключа, то находим $k_1$ – предшественника $k$ в поддереве этого узла. Удаляем его. Заменяем $k$ в исходном узле на $k_1$. Проделываем аналогичную работу, если дочерний узел, следующий за ключом $k$, имеет больше $t - 1$ ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по $t - 1$ ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них $k$, а далее удаляем $k$ из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] 2 последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.</wikitex>
+
Рассмотрим удаление из внутреннего узла. Имеется внутренний узел <tex>x</tex> и ключ, который нужно удалить, <tex>k</tex>. Если дочерний узел, предшествующий ключу <tex>k</tex>, содержит больше <tex>t - 1</tex> ключа, то находим <tex>k_1</tex> – предшественника <tex>k</tex> в поддереве этого узла. Удаляем его. Заменяем <tex>k</tex> в исходном узле на <tex>k_1</tex>. Проделываем аналогичную работу, если дочерний узел, следующий за ключом <tex>k</tex>, имеет больше <tex>t - 1</tex> ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них <tex>k</tex>, а далее удаляем <tex>k</tex> из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] <tex>2</tex> последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.
 +
 
 +
[[Файл:B3delin.png|550px|Удаление M и G из внутренних узлов]]
 +
 
 
==== Перемещение ключа ====
 
==== Перемещение ключа ====
<wikitex>[[Файл:BTMv.png|thumb|right|350px|Перемещение ключа в B-дереве]]Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей $t-1$, и предшествующие и следующие узлы-братья имеют по меньшей мере $t$ ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска $x.c_2$ ($x.k_1<k_{delete}<x.k_2$). Этот узел имеет лишь $t-1$ ключ (красная стрелка). Так как следующий брат $x.c_3$ содержит достаточное количество ключей, самый маленький ключ $x.c_3.k_1$ может перемещаться оттуда в родительский узел, чтобы перемещать, в свою очередь, ключ $x.k_2$ как дополнительный ключ в выбранный для спуска узел. Левое поддерево $x.c_3.k_1$ — новое правое поддерево перемещённого ключа $x.k_2$. Легко убедиться в том, что эти повороты сортирующие, так как для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>
+
Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей <tex>t-1</tex>, и предшествующие и следующие узлы-братья имеют по меньшей мере <tex>t</tex> ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска <tex>x.c_2</tex> (<tex>x.k_1<k_{delete}<x.k_2</tex>). Этот узел имеет лишь <tex>t-1</tex> ключ (красная стрелка). Так как следующий брат <tex>x.c_3</tex> содержит достаточное количество ключей, самый маленький ключ <tex>x.c_3.k_1</tex> может перемещаться оттуда в родительский узел, чтобы переместить, в свою очередь, ключ <tex>x.k_2</tex> как дополнительный ключ в выбранный для спуска узел. Левое поддерево <tex>x.c_3.k_1</tex> — новое правое поддерево перемещённого ключа <tex>x.k_2</tex>.  
 +
 
 +
[[Файл:BTMv.png|450px|Перемещение ключа в B-дереве]]
 +
Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей <tex>k</tex> на отложенном поддереве до и после перенесения выполняется условие <tex>x.k_2 \leqslant k \leqslant x.c_3.k_1</tex>. Симметричная операция может производиться для перенесения ключа из предшествующего брата.
  
 
==== Слияние ====
 
==== Слияние ====
<wikitex>[[Файл:BTMg.png|thumb|right|350px|Слияние узла братом]] Если выбранное для спуска поддерево $x.c_2$ и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла $x$, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел. Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере $t$ ключей вместо требуемых условиями B-дерева $t - 1$ ключей, родительский узел $x$ содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в  том случае, если 2 ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.</wikitex>
+
Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.  
 +
 
 +
Итак, если выбранное для спуска поддерево <tex>x.c_2</tex> и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла <tex>x</tex>, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.  
 +
 
 +
[[Файл:BTMg.png|450px|Слияние узла с братом]]
 +
Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере <tex>t</tex> ключей вместо требуемых условиями B-дерева <tex>t - 1</tex> ключей, родительский узел <tex>x</tex> содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в  том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.
  
 
== Вариации B-дерева ==
 
== Вариации B-дерева ==
 
=== B+-дерево ===
 
=== B+-дерево ===
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая B+-деревом, в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
+
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
  
 
=== B*-дерево ===
 
=== B*-дерево ===
Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на 2 узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.
+
Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на <tex>2</tex> узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.
  
 
=== 2-3 дерево ===
 
=== 2-3 дерево ===
Производное от B+-дерева. Каждый узел может иметь либо 2, либо 3 ребёнка.
+
Производное от B+-дерева. Каждый узел может иметь либо <tex>2</tex>, либо <tex>3</tex> ребёнка.
==== См.также ====
+
 
:*[[2-3 дерево]]
+
== См. также ==
 +
* [[2-3 дерево]]
 +
* [[B+-дерево]]
 +
* [[Splay-дерево]]
 +
* [[АВЛ-дерево]]
 +
* [[Красно-черное дерево]]
  
== Ссылки ==
+
== Источники информации ==
 
* T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
 
* T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
 
* Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
 
* Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
 
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
 
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
* [http://habrahabr.ru/post/114154/ Хабрахабр. B-tree.]
+
* [http://habrahabr.ru/post/114154/ habrahabr.ru {{---}} B-tree]
 +
* [http://de.wikipedia.org/wiki/B-Baum Wikipedia {{---}} B-Baum]
 
* [http://citforum.ru/programming/theory/sorting/sorting2.shtml#5 Методы сортировки и поиска. Методы поиска во внешней памяти]
 
* [http://citforum.ru/programming/theory/sorting/sorting2.shtml#5 Методы сортировки и поиска. Методы поиска во внешней памяти]
 
* [http://www.ibm.com/developerworks/ru/library/l-data_structures_10/ IBM. developerWorks. «Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья»]
 
* [http://www.ibm.com/developerworks/ru/library/l-data_structures_10/ IBM. developerWorks. «Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья»]
 
* [http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf R. Bayer, E. McCreight  «Organization and Maintenance of Large Ordered Indexes», Acta Informatica, 1972]
 
* [http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf R. Bayer, E. McCreight  «Organization and Maintenance of Large Ordered Indexes», Acta Informatica, 1972]
* [http://de.wikipedia.org/wiki/B-Baum Wikipedia. B-Baum]
 
 
== См. также ==
 
* [[2-3 дерево]]
 
* [[Splay-дерево]]
 
* [[АВЛ-дерево]]
 
* [[Красно-черное дерево]]
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Структуры данных]]
 
[[Категория:Деревья поиска]]
 
[[Категория:Деревья поиска]]

Текущая версия на 19:33, 4 сентября 2022

B-дерево (англ. B-tree) — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math]. B-дерево с [math]n[/math] узлами имеет высоту [math]O(\log n)[/math]. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время [math]O(\log n)[/math]

B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в [math]1970[/math] году.

Структура

B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова. B-дерево имеет следующие свойства ([math]t[/math] — параметр дерева, называемый минимальной степенью B-дерева, не меньший [math]2[/math].):

  • Каждый узел, кроме корня, содержит не менее [math]t - 1[/math] ключей, и каждый внутренний узел имеет по меньшей мере [math]t[/math] дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.
  • Каждый узел, кроме корня, содержит не более [math]2t - 1[/math] ключей и не более чем [math]2t[/math] сыновей во внутренних узлах
  • Корень содержит от [math]1[/math] до [math]2t - 1[/math] ключей, если дерево не пусто и от [math]2[/math] до [math]2t[/math] детей при высоте большей [math]0[/math].
  • Каждый узел дерева, кроме листьев, содержащий ключи [math]k_1, ..., k_n[/math], имеет [math]n + 1[/math] сына. [math]i[/math]-й сын содержит ключи из отрезка [math][k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty[/math].
  • Ключи в каждом узле упорядочены по неубыванию.
  • Все листья находятся на одном уровне.

Структура узла

struct Node
   bool leaf    // является ли узел листом
   int  n       // количество ключей узла
   int  key[]   // ключи узла
   Node c[]     // указатели на детей узла

Структура дерева

struct BTree
   int  t       // минимальная степень дерева
   Node root    // указатель на корень дерева

Назначение

B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с [math]n[/math] узлами имеют высоту [math]O(\log n)[/math]), но они лучше минимизируют количество операций чтения-записи с диском.

Структуры данных во внешней памяти

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

Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от [math]2[/math] до [math]16[/math] КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение и запись становятся полностью электронными процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.

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

Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы. Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между [math]50[/math] и [math]2000[/math], в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и [math]t=1001[/math], то поиск ключа займёт две дисковые операции.

Высота

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

Теорема:
Если [math]n \geqslant 1[/math], то для B-дерева [math]T[/math] c [math]n[/math] узлами и минимальной степенью [math]t \geqslant 2[/math] имеется следующее неравенство:
[math]h \leqslant[/math] [math]\log_t\dfrac{n+1}{2}[/math]
Доказательство:
[math]\triangleright[/math]

Корень B-дерева [math]T[/math] содержит по меньшей мере один ключ, а все остальные узлы — хотя бы [math]t - 1[/math] ключей. Так, [math]T[/math], высота которого [math]h[/math], имеет хотя бы [math]2[/math] узла на глубине [math]1[/math], хотя бы [math]2t[/math] узла на глубине [math]2[/math], хотя бы [math]2t^2[/math] узла на глубине [math]3[/math], и так далее, до глубины [math]h[/math], оно имеет по меньшей мере [math]2t^{h-1}[/math] узлов. Так, число ключей [math]n[/math] удовлетворяет неравенству:

[math]n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} [/math]
[math]=1+2(t-1)(\dfrac{t^h-1}{t-1})[/math]
[math]=2t^h-1[/math].
Простейшее преобразование дает нам неравенство [math]t^h \leqslant (n+1)/2[/math]. Логарифмирование по основанию [math]t[/math] обеих частей неравенства доказывает теорему
[math]\triangleleft[/math]

Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как [math]O(\log t)[/math] в обоих случаях (вспомним, что [math]t[/math] — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в [math]\log t[/math] раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.

Операции

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

Поиск ключа

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

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

Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые [math]t - 1[/math] ключей, во второй — последние [math]t - 1[/math] ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу

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


Вставка ключа в B-дерево [math]T[/math] высоты [math]h[/math] за один нисходящий проход по дереву потребует [math]O(h)[/math] обращений к диску и [math]O(th)=O(t \log_t n)[/math] процессорного времени.

void B-Tree-Insert(T: BTree, k: int):
    r = T.root
    if r.n == 2T.t - 1
        s = Allocate-Node()
        T.root = s
        s.leaf = false
        s.n = 0
        s.c[1] = r
        B-Tree-Split-Child(s, T.t, 1)
        B-Tree-Insert-Nonfull(s, k, T.t)
    else
        B-Tree-Insert-Nonfull(r, k, T.t)
void B-Tree-Insert-Nonfull(x: Node, k: int, t: int):
    i = x.n
    if x.leaf
        while i >= 1 and k < x.key[i]
            x.key[i+1] = x.key[i]
            i = i - 1
    x.key[i+1] = k
    x.n = x.n + 1
    Disk-Write(x)
    else 
        while i >= 1 and k < x.key[i]
            i = i - 1
        i = i + 1
        Disk-Read(x.c[i])
        if x.c[i].n == 2t - 1
            B-Tree-Split-Child(x, t, i)
            if k > x.key[i]
                i = i + 1
        B-Tree-Insert-Nonfull(x.c[i], k, t)

Функция [math]\operatorname{B-Tree-Insert-Nonfull}[/math] вставляет ключ [math]k[/math] в узел [math]x[/math], который должен быть незаполненным при вызове. Использование функции [math]\operatorname{B-Tree-Split-Child}[/math] гарантирует, что рекурсия не встретится с заполненным узлом. Ниже показана вставка ключей [math]B[/math], [math]Q[/math], [math]L[/math] и [math]F[/math] в дерево с [math]t = 3[/math], т.е. узлы могут содержать не более [math]5[/math] ключей B3insa.png


Разбиение узла

Функция [math]\operatorname{B-Tree-Split-Child}[/math] получает в качестве входного параметра незаполненный внутренний узел [math]x[/math] (находящийся в оперативной памяти), индекс [math]t[/math] и узел [math]y[/math] (также находящийся в оперативной памяти), такой что [math]y = c_i[x][/math] является заполненным дочерним узлом [math]x[/math]. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля [math]x[/math], внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на [math]1[/math]. Отметим, что увеличить высоту B-дерева можно только разбиением.

Разбиение узла B-дерева с t=4

void B-Tree-Split-Child(x: Node, t: int, i: int):
    z = Allocate-Node()
    y = x.c[i]
    z.leaf = y.leaf
    z.n = t - 1
    for j = 1 to t - 1
        z.key[j] = y.key[j+t]
    if not y.leaf
        for j = 1 to t
            z.c[j] = y.c[j+t]
    y.n = t - 1
    for j = x.n + 1 to i + 1
        x.c[j+1] = x.c[j]
    x.c[i+1] = z
    for j = x.n to i
        x.key[j+1] = x.key[j]
    x.key[i] = y.key[t]
    x.n = x.n + 1
    Disk-Write(y)
    Disk-Write(z)
    Disk-Write(x)

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

Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. [math]\geqslant t[/math]) в нем, а также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей [math]t-1[/math], производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже. Для удаления требуется время [math]O(t \log_t n)[/math] и [math]O(h)[/math] дисковых операций.

Удаление ключа из листа

Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше [math]t - 1[/math], то просто удаляем ключ.

Удаление [math]F[/math] из листа В противном случае, если существует соседний лист с тем же родителем, который содержит больше [math]t - 1[/math] ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как [math]k_1[/math]. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим [math]k_2[/math]. Удалим из исходного узла ключ, который нужно было удалить, спустим в этот узел [math]k_2[/math], а вместо [math]k_2[/math] в родительском узле поставим [math]k_1[/math]. Если все соседи содержат по [math]t - 1[/math] ключу, то объединяем узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, переместим в новый узел.

Удаление ключа из внутреннего узла

Рассмотрим удаление из внутреннего узла. Имеется внутренний узел [math]x[/math] и ключ, который нужно удалить, [math]k[/math]. Если дочерний узел, предшествующий ключу [math]k[/math], содержит больше [math]t - 1[/math] ключа, то находим [math]k_1[/math] – предшественника [math]k[/math] в поддереве этого узла. Удаляем его. Заменяем [math]k[/math] в исходном узле на [math]k_1[/math]. Проделываем аналогичную работу, если дочерний узел, следующий за ключом [math]k[/math], имеет больше [math]t - 1[/math] ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по [math]t - 1[/math] ключу, то объединяем этих детей, переносим в них [math]k[/math], а далее удаляем [math]k[/math] из нового узла. Если сливаются [math]2[/math] последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

Удаление M и G из внутренних узлов

Перемещение ключа

Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей [math]t-1[/math], и предшествующие и следующие узлы-братья имеют по меньшей мере [math]t[/math] ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска [math]x.c_2[/math] ([math]x.k_1\lt k_{delete}\lt x.k_2[/math]). Этот узел имеет лишь [math]t-1[/math] ключ (красная стрелка). Так как следующий брат [math]x.c_3[/math] содержит достаточное количество ключей, самый маленький ключ [math]x.c_3.k_1[/math] может перемещаться оттуда в родительский узел, чтобы переместить, в свою очередь, ключ [math]x.k_2[/math] как дополнительный ключ в выбранный для спуска узел. Левое поддерево [math]x.c_3.k_1[/math] — новое правое поддерево перемещённого ключа [math]x.k_2[/math].

Перемещение ключа в B-дереве Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей [math]k[/math] на отложенном поддереве до и после перенесения выполняется условие [math]x.k_2 \leqslant k \leqslant x.c_3.k_1[/math]. Симметричная операция может производиться для перенесения ключа из предшествующего брата.

Слияние

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

Итак, если выбранное для спуска поддерево [math]x.c_2[/math] и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла [math]x[/math], который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.

Слияние узла с братом Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере [math]t[/math] ключей вместо требуемых условиями B-дерева [math]t - 1[/math] ключей, родительский узел [math]x[/math] содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.

Вариации B-дерева

B+-дерево

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

B*-дерево

Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на [math]2[/math] узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.

2-3 дерево

Производное от B+-дерева. Каждый узел может иметь либо [math]2[/math], либо [math]3[/math] ребёнка.

См. также

Источники информации