Хотя двоичное дерево — отличная структура данных для упорядоченных словарей, хранящихся в основной памяти, эти структуры данных действительно не подходят для данных, хранящихся во внешних системах памяти, таких как диски. При доступе к данным на диске задержка (задержка ожидания начала передачи) значительна, но сразу вводится весь блок (или страница) памяти.

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

B-дерево: дерево многоканального поиска. Он достигает баланса, ограничивая «ширину» каждого узла. Существует множество модификаций и адаптаций B-деревьев, например, дерево 2–3 является частным случаем B-дерева.

Для любого целого числа m ≥ 3 B-дерево порядка m — это многоходовое дерево поиска со свойствами:

  1. Корень либо является листом, либо имеет от 2 до m дочерних элементов.
  2. Каждый узел, кроме корня, имеет от ⌈m/2⌉ дочерних узлов. Узел с j дочерними элементами содержит j — 1 ключ.
  3. Все листья находятся на одном уровне дерева.

Дерево 2–3 является примером B-дерева порядка 3. Типичные B-деревья довольно большие, например, B-деревья порядка 100 распространены на практике. Узел в таком дереве имеет от 50 до 100 потомков и содержит от 49 до 99 ключей.

По мере роста разветвленного B-дерева высота дерева уменьшается. B-дерево порядка m, содержащее n ключей, имеет высоту не более lg(n)/γ, где γ = lg(m/2).

int M = xxx //order of the B-tree

class BTreeNode {
    int nChildren; //current number of children (from M/2 to M)
    BTreeNode child[M]; //children pointers
    Key key[M-1];
    Value value[M-1];
}

Поиск: поиск ключа в B-дереве является прямым обобщением поиска по бинарному дереву. Когда вы доберетесь до внутреннего узла с ключами a1 ‹ a2 ‹ … ‹ a{j-1}, найдите x в этом списке. Если вы найдете x в списке, то мы возвращаем значение. В противном случае определите индекс i такой, что a{i-1} ‹ x ‹ a{i}. Затем выполните рекурсивный поиск в поддереве T{i}. Когда вы доберетесь до листа, найдите все ключи в этом узле. Если его здесь нет, то x не находится в B-дереве.

Поскольку узлы довольно широкие, следует ли нам использовать какой-либо алгоритм поиска, например бинарный поиск? Что ж, обычно время задержки обычно настолько превышает время обработки, что простой линейный поиск достаточно быстр.

Подобно 2–3 деревьям, B-деревья имеют три механизма реструктуризации: разделение узлов, слияние узлов и принятие поддерева. (нажмите здесь, чтобы увидеть 2–3 дерева)

Скажем, у нас есть B-дерево порядка 5, тогда m = 5.

Принятие (ротация ключей): помните, что узел в B-дереве может иметь от ⌈m/2⌉до m дочерних элементов, и количество ключей меньше на один. В результате вставки или удаления узел может получить на один слишком много (m + 1 потомков и m ключей) или на один слишком мало (⌈m/2⌉ — 1 потомок и ⌈m/2⌉ — 2 ключа). Самый простой способ решить проблему дисбаланса — переместить ребенка к одному из ваших братьев и сестер или от него, предполагая, что у вас есть брат или сестра, которые могут поглотить это изменение.

Разделение: после того, как мы вставили ключ в B-дерево, узел может получить слишком много дочерних элементов (m + 1 дочерний элемент). Когда это происходит, а ротация ключей недоступна, мы разделяем узел на два узла, один из которых имеет m'=⌈m/2⌉ дочерних элементов, а другой имеет оставшиеся m'' = m + 1 — ⌈м/2⌉ детей. Для всех m ≥ 2 ⌈m/2⌉ ≤ m + 1 — ⌈m/2⌉ ≤ m.

Слияние: в результате удаления узел может иметь слишком мало дочерних узлов (⌈m/2⌉ — 1 дочерний узел и ⌈m/2⌉ — 2 ключа). Когда это происходит и ротация ключей недоступна, мы можем сделать вывод, что его братья и сестры имеют минимальное число ⌈m/2⌉ дочерних элементов. Мы объединяем этот узел с любым из его братьев и сестер в один узел, имеющий в общей сложности m'=(⌈m/2⌉— 1) + ⌈m/2⌉ = 2 * ⌈m/2⌉ — 1 дет. Для всех m ≥ 2 ⌈m/2⌉ ≤ 2 * ⌈m/2⌉ — 1 ≤ m.

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

Чтобы вставить ключ, мы находим правильный лист, в который вставляем наш ключ. Если лист не заполнен ( ≤ m — 1 ключей), то вставляем наш ключ. Сделанный. Это потребует перемещения ключей внутри конечного узла, чтобы освободить место для новой записи, но такие затраты можно игнорировать.

Удаление: как и при удалении двоичного дерева, мы находим заменяющий ключ, находя самый большой ключ в левом дочернем элементе, который называется неупорядоченным предшественником (или самый маленький ключ в правом дочернем элементе, называемый неупорядоченным преемником), и перемещая этот ключ. ключ вверх, чтобы заполнить отверстие. Заменяющий ключ всегда будет на уровне листа. Это создает отверстие в листовом узле. если в этом листовом узле все еще есть хотя бы ⌈m/2⌉ — 1 ключей, то мы закончили.

В противном случае мы имеем ситуацию с недостаточным потоком. Поэтому после того, как мы удалили ключ замены, мы сначала проверяем, возможна ли ротация ключа. Если у одного из двух братьев и сестер есть хотя бы один ключ больше минимального, то мы поворачиваем дополнительный ключ в этот узел, и все готово. Если это невозможно, то любой из наших братьев и сестер должен иметь минимальное количество ⌈m/2⌉ дочерних элементов, и поэтому мы можем выполнить слияние узлов. Процесс рекурсивный.

Вот еще пример при удалении ключа в листовом узле:

— Конец моих учебных заметок —