Ранее в курсе мы уже познакомились со сбалансированными деревьями поиска — это АВЛ-деревья или красно-черные деревья.
Они способны организовать эффективный поиск элементов за время . Но чтобы совершить этот поиск, потребуется выполнить операций. Со временем число данных, которые нужно хранить в дереве, будет расти. Дерево потребуется сохранять на более дешевых хранилищах данных вроде жестких дисков, а не хранить в оперативной памяти.
Это ведет к тому, что для поиска элемента в дереве нам придется раз обратиться к жесткому диску. При больших это число операций остается существенным. Операции над жестким диском гораздо медленнее, чем над оперативной памятью. Значит, оборудование будет быстро изнашиваться, а само приложение будет работать медленнее.
Ученым предстояло решить, как организовать эффективный поиск в древовидных структурах, которые должны храниться в постоянной памяти. Чтобы решить эту задачу, они придумали новый вид деревьев — сильноветвящиеся B-деревья и их производные: B+ деревья, B*-деревья, 2-3 деревья.
В этом уроке мы детально познакомимся с видами сильноветвящихся деревьев и особенностями реализации операций поиска, вставки и удаления узлов.
Устройство B-деревьев
Рассмотрим дерево, которое состоит из миллиона элементов. Если хранить данные в сбалансированном бинарном дереве поиска, то поиск элемента займет двадцать операций:
Если разбить дерево на страницы, в каждой из которых будет по семь узлов дерева, поиск поддерева с нужным элементом будет выполнен за семь обращений к диску:
Рассмотрим пример такого разбиения:
Такая группировка узлов на страницах превращает бинарное дерево в октарное — с восемью дочерними узлами. Число дочерних узлов у страницы может и дальше увеличиваться, например, до 128 элементов. Это приведет к тому, что поиск элемента будет выполнен всего за три обращения к диску:
Таким образом, нам достаточно выбрать оптимальный размер страницы, который удовлетворяет нашим ограничениям по оперативной памяти. Также мы можем хранить в оперативной памяти ссылку на корневой элемент дерева, а сам вид дерева можно привести к виду на рисунке:
В этом случае в узлах располагается несколько ключей в порядке возрастания слева направо. Дочерние узлы содержат ключи, которые находятся в промежутке между значениями родительского узла.
Помимо особенности расположения ключей стоит отметить, что B-дерево со степенью обладает следующими свойствами:
-
Глубина всех листьев одинакова
-
Каждый узел имеет не более потомков
-
Каждый узел кроме корневого и листовых имеют не менее потомков
-
Если высота дерева больше единицы, то у корневого узла не менее двух дочерних узлов
-
Нелистовой узел с потомками имеет ключей
Представим узел B-дерева в виде кода на JavaScript:
class BTreeNode {
constructor(value, parent) {
this.leaf = false; // Флаг, который показывает, что текущий узел является листовым
this.keys = [value]; // Массив ключей (полезной нагрузки) узла
this.parent = parent; // Cсылка на родителя
this.children = new Array(); // Массив дочерних узлов
}
}Java
public class BTreeNode {
public boolean leaf; // Флаг показывает, что текущий узел является листовым
public List<Integer> keys; // Массив ключей (полезной нагрузки) узла
public BTreeNode parent; // Cсылка на родителя
public List<BTreeNode> children; // Массив дочерних узлов
public BTreeNode(int value, BTreeNode parent) {
this.leaf = false;
this.keys = new ArrayList<>();
this.keys.add(value);
this.parent = parent;
this.children = new ArrayList<>();
}
}Python
class BTreeNode:
def __init__(self, value, parent=None):
self.leaf = False # Флаг, который показывает, что текущий узел является листовым
self.keys = [value] # Массив ключей (полезной нагрузки) узла
self.parent = parent # Cсылка на родителя
self.children = [] # Массив дочерних узловPHP
<?php
class BTreeNode
{
public $leaf = false; // Флаг показывает, что текущий узел является листовым
public $keys = []; // Массив ключей (полезной нагрузки) узла
public $parent; // Cсылка на родителя
public $children = []; // Массив дочерних узлов
public function __construct($value, $parent = null)
{
$this->keys = [$value];
$this->parent = $parent;
}
}Над B-деревьями выполняются все классические операции:
-
Поиск узла
-
Добавление узла
-
Удаление узла
Однако сложная организация ветвления узлов вносит свои реализации. Далее рассмотрим эти операции подробнее.
Операции над B-деревьями
Поиск узлов в случае работы с B-деревом отличается от аналогичной операции над бинарным деревом только порядком действий во время проверки ключей узла. Он будет выглядеть следующим образом:
class BTreeNode {
// ...
findNode(value) {
let node = this;
while (node) { // Проходимся по всем узлам
for (let i = 0; i < node.keys.length; i++) { // Проверяем ключи
if (value === node.keys[i]) {
return node;
}
if (value < node.keys[i]) {
if (!node.leaf) {
if (i < node.children.length) {
node = node.children[i];
} else {
return null;
}
break;
} else {
return null;
}
} else if (i === node.keys.length - 1 && !node.leaf) {
if (i + 1 < node.children.length) {
node = node.children[i + 1];
} else {
return null;
}
break;
}
}
}
return null;
}
}https://replit.com/@hexlet/algorithms-trees-btrees-js#index.js
Java
class BTreeNode {
// ...
public BTreeNode findNode(int value) {
BTreeNode node = this;
while (node != null) {
for (int i = 0; i < node.keys.size(); i++) {
if (value == node.keys.get(i)) {
return node;
}
if (value < node.keys.get(i)) {
if (!node.leaf) {
if (i < node.children.size()) {
node = node.children.get(i);
} else {
return null;
}
break;
} else {
return null;
}
} else if (i == node.keys.size() - 1 && !node.leaf) {
if (i + 1 < node.children.size()) {
node = node.children.get(i + 1);
} else {
return null;
}
break;
}
}
}
return null;
}
}https://replit.com/@hexlet/algorithms-trees-btrees-java#src/main/java/BTreeNode.java
Python
class BTreeNode:
## ...
def find_node(self, value):
node = self
while node:
for i in range(len(node.keys)):
if value == node.keys[i]:
return node
if value < node.keys[i]:
if not node.leaf:
if i < len(node.children): # Проверяем, что индекс i не выходит за пределы массива
node = node.children[i]
else:
return None
break
else:
return None
elif i == len(node.keys) - 1 and not node.leaf:
if i + 1 < len(node.children): # Проверяем, что индекс i + 1 не выходит за пределы массива
node = node.children[i + 1]
else:
return None
break
else:
break
return Nonehttps://replit.com/@hexlet/algorithms-trees-btrees-python#main.py
PHP
<?php
class BTreeNode
{
// ...
public function findNode($value) {
$node = $this;
while ($node != null) {
for ($i = 0; $i < count($node->keys); $i++) {
if ($value == $node->keys[$i]) {
return $node;
}
if ($value < $node->keys[$i]) {
if (!$node->leaf) {
if ($i < count($node->children)) {
$node = $node->children[$i];
} else {
return null;
}
break;
} else {
return null;
}
} elseif ($i == count($node->keys) - 1 && !$node->leaf) {
if ($i + 1 < count($node->children)) {
$node = $node->children[$i + 1];
} else {
return null;
}
break;
}
}
if ($node === null) {
break;
}
}
return null;
}
}https://replit.com/@hexlet/algorithms-trees-btrees2-php#main.php
В этом примере можно заметить пересечение с логикой поиска в бинарном дереве поиска. Если искомое значение меньше текущего значения узла, мы переходим по левой от него ветке. Если больше всех ключей узла — переходим на правое поддерево.
Вставка новых элементов в B-дерево разрешается только в листовые узлы. Это приводит к необходимости следить за заполненностью узлов. Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.
Чтобы разделить узел, создается два новых листовых узла, которые содержат половину значений из существующего узла, и переносится среднее значение в родительский узел.
Если заполнен и корневой узел, то мы разбиваем его на два новых: выбираем среднее значение, создаем для него новый узел, который станет новым корнем всего дерева:
В данном примере мы вставляем ключ 3 в дерево с одним заполненным корневым узлом. Вставка ключа приводит к переполнению корневого узла. Чтобы решить эту ситуацию, мы разбиваем корневой узел на две части, создаем новый узел со средним значением и делаем его корнем всего дерева.
Аналогично изменение структуры узлов может возникнуть, когда узел удаляется. Если в соседних узлах слишком мало ключей — занятость узлов падает ниже значения — и эти узлы находятся на одном родственном уровне, то такие узлы необходимо слить. Данная ситуация называется антипереполнением.
Существует два способа объединения узлов:
-
Если у двух смежных узлов общий предок, и их содержимые помещаются в один узел, их следует объединить
-
Если содержимое смежных узлов не помещается в одном узле, то ключи перераспределяются между ними, чтобы восстановить баланс
Операции слияния и расщепления достаточно дорогостоящие. Чтобы оптимизировать данный процесс, были придуманы специальные подвиды B-деревьев.
Производные виды деревьев
К производным видам B-деревьев чаще всего относят следующие три вида:
-
B⁺-деревья
-
B*-деревья
-
2-3-деревья
B⁺-деревья
В B⁺-деревьях данные ключей хранятся только в листовых узлах, а в промежуточных хранятся копии значений ключей. Это помогает эффективно организовывать поиск в блочных средах хранения. Например, в файловых системах, где B⁺-деревья применяют, чтобы хранить каталоги.
Также реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle, поддерживают этот тип деревьев, чтобы организовывать табличные индексы.
B*-деревья
B*-дерево ориентировано на более плотное хранение ключей во внутренних узлах. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на две трети от вместо половины от .
B*-деревья используются для того, чтобы вызывать дорогостоящую операцию разделения как можно реже. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи «переливаются» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на три новых узла.
2-3-деревья
2-3 деревья — частный случай B⁺-деревьев с сокращенным количеством элементов на страницах. Каждый узел 2-3-дерева, кроме листовых, может содержать только один ключ и два потомка, либо два ключа и три потомка.
Выводы
Способ хранения деревьев может оказывать существенное влияние на организацию структуры узлов и входящих в них ключей. Например, хранение классических бинарных деревьев поиска на жестком диске может привести к многократному росту числа операций над диском.
Для оптимизации хранения и поиска данных в таких условиях были предложены B-деревья. Они помогают сократить нагрузку на диск. Это возможно, если увеличить количество веток в узлах и хранить несколько ключей полезной нагрузки.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
