B+ дерево — это сбалансированное дерево поиска, оптимизированное для работы с блочными устройствами (дисками) и используемое в качестве основного механизма индексации в реляционных базах данных и файловых системах.
Ключевые свойства:
- Все элементы (ключ + данные) хранятся только в листьях.
- Внутренние узлы содержат только ключи-разделители и указатели на дочерние узлы.
- Листья связаны в двусвязный список, что позволяет быстро выполнять диапазонные запросы (BETWEEN, сканирование по индексу).
- Дерево всегда идеально сбалансировано по высоте: все листья находятся на одном уровне.
- Каждый узел (кроме корня) гарантированно заполнен как минимум наполовину: при максимальном количестве ключей M минимальное — ⌈M/2⌉ - 1. Это обеспечивает высоту O(log n) и эффективное использование памяти/диска.
m-1 ключей и m указателей на детей. Для ключей k₁ < k₂ < … < kₙ выполнено: child[0] < k₁; i = 1..n-1: kᵢ ≤ все ключи в child[i] < kᵢ₊₁; child[n] ≥ kₙ. m-1 записей (ключ → значение), а также ссылки next и prev для обхода диапазона. Параметр m (степень ветвления) выбирается так, чтобы один узел помещался в страницу диска или кэш-линию.
i, что keys[i] ≤ target < keys[i+1]; переходим в children[i]. O(log_m n) чтений блоков.m, создаём новый лист L', перемещаем в него правую половину. Копируем первый ключ из L' (или минимальный разделитель) в родительский узел. ⌈m/2⌉ - 1 записей (underflow), пытаемся занять одну запись у левого или правого соседнего листа (если у него достаточно). В родителе обновляется соответствующий разделитель. Ниже — учебная реализация B+ дерева с порядком order=3 (макс. ключей = 2), поддерживающая insert, search и delete. Код содержит подробные комментарии на русском.
from bisect import bisect_left, bisect_right
class Node:
"""Базовый класс узла B+ дерева."""
def __init__(self, is_leaf=False):
self.keys = [] # ключи (для листа – вместе с данными)
self.children = [] # для внутреннего узла – ссылки на детей
self.is_leaf = is_leaf
self.next = None # для связного списка листьев
self.prev = None
class Leaf(Node):
"""Листовой узел: хранит данные как словари {key: value}."""
def __init__(self):
super().__init__(is_leaf=True)
self.data = [] # значения, соответствующие ключам
class InternalNode(Node):
"""Внутренний узел."""
pass
class BPlusTree:
def __init__(self, order=3):
self.root = Leaf() # изначально корень – пустой лист
self.order = order # максимальное количество детей
@property
def max_keys(self):
return self.order - 1
@property
def min_keys(self):
# минимальное число ключей для не-корневого узла
return (self.order + 1) // 2 - 1 # ceil(order/2) - 1
# ---------- ПОИСК ----------
def search(self, key):
"""Возвращает значение по ключу или None."""
leaf = self._find_leaf(key)
idx = bisect_left(leaf.keys, key)
if idx < len(leaf.keys) and leaf.keys[idx] == key:
return leaf.data[idx]
return None
def _find_leaf(self, key):
"""Ищет лист, в котором должен находиться ключ."""
node = self.root
while not node.is_leaf:
# для внутреннего узла: keys[i] – разделители, children[i] указывает на поддерево с ключами < keys[i]
# обычно нужно найти последний индекс i, где key >= keys[i]
i = bisect_right(node.keys, key)
node = node.children[i]
return node
# ---------- ВСТАВКА ----------
def insert(self, key, value):
"""Вставляет ключ и значение."""
leaf = self._find_leaf(key)
self._insert_into_leaf(leaf, key, value)
def _insert_into_leaf(self, leaf, key, value):
idx = bisect_left(leaf.keys, key)
# если ключ уже есть, обновляем значение
if idx < len(leaf.keys) and leaf.keys[idx] == key:
leaf.data[idx] = value
return
leaf.keys.insert(idx, key)
leaf.data.insert(idx, value)
if len(leaf.keys) > self.max_keys:
self._split_leaf(leaf)
def _split_leaf(self, leaf):
"""Разделяет переполненный лист на два."""
mid = len(leaf.keys) // 2
new_leaf = Leaf()
# переносим правую половину в новый лист
new_leaf.keys = leaf.keys[mid:]
new_leaf.data = leaf.data[mid:]
leaf.keys = leaf.keys[:mid]
leaf.data = leaf.data[:mid]
# перелинковываем связный список листьев
new_leaf.next = leaf.next
new_leaf.prev = leaf
if leaf.next:
leaf.next.prev = new_leaf
leaf.next = new_leaf
# новый ключ-разделитель – первый ключ нового листа
separator = new_leaf.keys[0]
# вставляем разделитель в родительский узел
if leaf is self.root:
# создаём новый корень, если разбивается корень-лист
new_root = InternalNode()
new_root.keys = [separator]
new_root.children = [leaf, new_leaf]
self.root = new_root
else:
self._insert_into_parent(leaf, separator, new_leaf)
def _insert_into_parent(self, left_child, key, right_child):
"""Вставляет ключ-разделитель и правого ребёнка в узел-родитель."""
parent = self._find_parent(self.root, left_child)
idx = parent.children.index(left_child)
# вставляем ключ и указатель на нового ребёнка после позиции left_child
parent.keys.insert(idx, key)
parent.children.insert(idx + 1, right_child)
if len(parent.keys) > self.max_keys:
self._split_internal(parent)
def _split_internal(self, node):
"""Разделяет переполненный внутренний узел."""
mid = len(node.keys) // 2
mid_key = node.keys[mid]
new_node = InternalNode()
# правую половину ключей и детей переносим в новый узел
new_node.keys = node.keys[mid+1:]
new_node.children = node.children[mid+1:]
node.keys = node.keys[:mid]
node.children = node.children[:mid+1]
if node is self.root:
new_root = InternalNode()
new_root.keys = [mid_key]
new_root.children = [node, new_node]
self.root = new_root
else:
parent = self._find_parent(self.root, node)
self._insert_into_parent(node, mid_key, new_node)
def _find_parent(self, node, child):
"""Поиск родителя узла child, начиная с node (обычно корень)."""
if node.is_leaf or child is self.root:
return None
for c in node.children:
if c is child:
return node
if not c.is_leaf:
p = self._find_parent(c, child)
if p:
return p
return None
# ---------- УДАЛЕНИЕ ----------
def delete(self, key):
"""Удаляет ключ из дерева, если он существует."""
leaf = self._find_leaf(key)
idx = bisect_left(leaf.keys, key)
if idx >= len(leaf.keys) or leaf.keys[idx] != key:
return False
leaf.keys.pop(idx)
leaf.data.pop(idx)
if leaf is self.root:
return True # корень-лист может быть пустым
if len(leaf.keys) < self.min_keys:
self._handle_underflow(leaf)
return True
def _handle_underflow(self, node):
"""Обработка недостатка ключей в узле (leaf или internal)."""
parent = self._find_parent(self.root, node)
if parent is None:
# node – корень?
return
idx = parent.children.index(node)
left_sibling = parent.children[idx - 1] if idx > 0 else None
right_sibling = parent.children[idx + 1] if idx < len(parent.children) - 1 else None
# 1. Перераспределение (занять у соседа)
if left_sibling and len(left_sibling.keys) > self.min_keys:
self._borrow_from_left(node, left_sibling, parent, idx)
elif right_sibling and len(right_sibling.keys) > self.min_keys:
self._borrow_from_right(node, right_sibling, parent, idx)
else:
# 2. Слияние с соседом
if left_sibling:
self._merge(left_sibling, node, parent, idx - 1)
elif right_sibling:
self._merge(node, right_sibling, parent, idx)
def _borrow_from_left(self, node, left, parent, idx_in_parent):
"""Перемещает запись/ключ из левого брата в текущий узел."""
if node.is_leaf:
# берём последнюю запись левого листа
moved_key = left.keys.pop()
moved_val = left.data.pop()
# вставляем в начало текущего листа
node.keys.insert(0, moved_key)
node.data.insert(0, moved_val)
# обновляем разделитель в родителе (теперь первый ключ текущего листа)
parent.keys[idx_in_parent - 1] = node.keys[0]
else:
# для внутреннего узла: переносим ключ из родителя в узел,
# а последний ключ левого брата – в родитель
# (сложнее, но для краткости опустим – в учебном примере удаление внутренних проще
# реализовать без полной поддержки underflow внутренних узлов,
# т.к. наша реализация не позволяет внутреннему узлу иметь min_keys > 0
# при стандартной настройке)
pass
def _borrow_from_right(self, node, right, parent, idx_in_parent):
"""Перемещает запись/ключ из правого брата в текущий узел."""
if node.is_leaf:
moved_key = right.keys.pop(0)
moved_val = right.data.pop(0)
node.keys.append(moved_key)
node.data.append(moved_val)
parent.keys[idx_in_parent] = right.keys[0]
else:
pass
def _merge(self, left, right, parent, idx_of_left):
"""Слияние левого и правого узлов. left поглощает right."""
if right.is_leaf:
left.keys.extend(right.keys)
left.data.extend(right.data)
left.next = right.next
if right.next:
right.next.prev = left
else:
# для внутренних узлов: ключ из родителя (разделитель) опускается в объединённый узел
sep_key = parent.keys.pop(idx_of_left)
left.keys.append(sep_key)
left.keys.extend(right.keys)
left.children.extend(right.children)
# удаляем правый узел из списка детей родителя
parent.children.remove(right)
# обновляем ссылки, если узел был корнем
if parent is self.root and not parent.keys:
# корень стал пустым – понижаем дерево
self.root = left
# если после удаления родитель сам испытывает underflow
if parent is not self.root and len(parent.keys) < self.min_keys:
self._handle_underflow(parent)
# ---------- Пример использования ----------
if __name__ == "__main__":
tree = BPlusTree(order=4) # max keys = 3, min keys = 1
# вставка
pairs = [(10, "A"), (20, "B"), (5, "C"), (15, "D"), (25, "E"), (6, "F"), (12, "G")]
for k, v in pairs:
tree.insert(k, v)
# поиск
print(tree.search(15)) # D
print(tree.search(30)) # None
# удаление
tree.delete(20)
print(tree.search(20)) # None
# обход диапазона (через связный список листьев)
leaf = tree.root
while not leaf.is_leaf:
leaf = leaf.children[0] # самый левый путь
while leaf:
for k, d in zip(leaf.keys, leaf.data):
print(f"{k}: {d}", end=" | ")
leaf = leaf.next
Что делает этот код:
- Порядок order=4 означает максимум 3 ключа в узле (как в листе, так и во внутреннем).
- Вставка автоматически разбивает узлы, обновляет связный список листьев и правильно поднимает разделители.
- Удаление обрабатывает underflow путём перераспределения от левого/правого соседа или слияния, понижая дерево в случае пустого корня.
Важно: В этом упрощённом варианте перераспределение для внутренних узлов (borrow_from_left/right для is_leaf=False) не реализовано полностью, чтобы не перегружать пример. В реальном коде для внутренних узлов при underflow сначала пробуют забрать один ключ у брата через родительский разделитель, а только потом сливают. Полную реализацию можно найти в open-source библиотеках, например py-bplustree.
[deepseek-v4-pro]