B-деревья

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

Древовидные структуры и деревья всё еще удобны и для внешнего поиска. Надо только выбрать способ правильно представить дерева и максимально эффективно использовать оперативную память.

Давайте рассмотрим довольно простую идею, которая открывает нам практически безграничные просторы внешнего поиска. Место нашего поиска буду дальше называть диском. Вот пусть для поиска в диске мы используем бинарное дерево. Записей у нас $1\,000\,000$ . Если наше дерево идеально сбалансировано, то при поиске нам понадобится сделать $\log_2 1\,000\,000 \approx 20$ обращений к диску.

Разделим наши данные в древесной структуре на страницы фиксированного размера, как на рисунке. Будем из диска запрашивать не по одному значению, а сразу по страницам. Тогда наш поиск ускорится в $\log_2 (\text{высота страницы})$ раз!

...

B-дерево порядка $m$ — сильноветвящиеся дерево, у которого

у каждого узла максимум $m$ детей
у каждого узла, кроме корня и листов, минимум $\lceil m/2 \rceil$ детей
корневой узел, если не является листом, имеет минимум $2$ ребенка
все листья находятся на одном уровне
любой узел с $k$ детьми содержит $k-1$ ключ

B-деревьев порядка $1$ не бывает, а B-деревья порядка $2$ — это простые бинарные деревья. Поэтому будем рассматривать только B-деревья порядка $3$ и больше, $m \ge 3$ .

Каждый узел B-дерева можно представить как массив из $2m-1$ элементов. На нечётных позициях стоят ссылки на детей. На чётных позициях находятся ключи.

\Big( P_1 \quad K_1 \quad P_2 \quad K_2 \quad P_3 \quad K_3 \quad \cdots \quad P_{m-1} \quad K_{m-1} \quad P_m \Big)

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

В узлах ключи упорядочены: $K_1 < K_2 < \dotsb < K_{m-1}$ , а каждая ссылка $P_i$ указывает на узел, в котором все ключи находятся между ключами $K_{i-1}$ и $K_i$ родительского узла.

Ключевой характеристикой для B-дерева является высота. От нее зависит и временная сложность операций, и количество обращений к диску. Пусть в B-дереве хранится $n$ ключей. Оценим высоту дерева — $h$ .

В корне минимум $1$ ключ и минимум $2$ ребёнка. В остальных узлах минимум $\lceil m/2 \rceil - 1$ ключей и минимум $\lceil m/2 \rceil$ детей. Получаем формулу для подсчёта минимального количества ключей в B-дереве высоты $h$ :

n_{\mathrm{min}}(h) = 1 + 2 \cdot n_{\mathrm{min}}(h-1) \implies n_{\mathrm{min}}(h) = 2 \cdot \lceil m/2 \rceil^h - 1

Аналогично, для максимального количества ключей

n_{\mathrm{max}}(h) = (m-1) + m \cdot n_{\mathrm{max}}(h) \implies n_{\mathrm{max}}(h) = m^{h+1} - 1

Тогда из общего неравенства

2 \cdot \lceil m/2 \rceil^h - 1 \le n \le m^{h+1} - 1

можно получить неравенство для высоты дерева

\lfloor \log_m n \rfloor - 1 \le h \le \left\lceil \log_{\lceil m/2 \rceil} \frac{n+1}{2} \right\rceil

В целом операция поиска в B-дереве аналогична операции поиска в бинарном дереве.

Пусть нам нужно найти ключ $K$ в B-дереве. Обращаемся к диску, получаем узел и сохраняем его в оперативную память. Ищем в этом узле ключ $K$ , или ссылку $P_i$ , где $K_{i-1} < K < K_i$ . Переходим по этой ссылке, получаем новый узел, и продолжаем наш поиск. Если мы дошли до листа и не нашли узел $K$ , значит его в B-дереве нет.

В целом нам потребуется максимум

B-деревья

B-деревья

Высота B-дерева

Поиск