Сбалансированное дерево, как пример индекса РСУБД.

В реляционных СУБД большие таблицы могут содержать тысячи записей, поиск элемента без индекса стоит O(n). Из-за этого используют индексы, сбалансированное дерево является одним из самых популярных индексов

Сбалансированное дерево - структура данных, в которой высота левого и правого поддерева каждого узла отличается не более чем на единицу.

Основные свойства

Высота дерева минимальна
Все листьях находятся примерно на одном уровне
При вставке или удалении структура автоматически перестраивается

Сложность в сбалансированном дереве всегда составляет O(log(n))

Сбалансированные деревья не используются напрямую, в базах данных(postgresql, mysql, oracle) используются B-Tree или B+Tree

Особенности

Каждый узел хранит несколько ключей
Каждый узел может иметь множество потомков
Дерево получается низким( 3-4 уровня для миллиона записей)

B-Tree

Пример B-Tree

Количество узлов выходящих из родителя равно количество узлов родителя + 1

Поиск выполняется следующим образом - B-Tree начинает с верхнего узла и сравнивает значения(сначала меньше/больше, а потом равно ли оно), например возьмем 7. B-Tree начинает слева направо и смотрит:

7<3 - нет, значит идем дальше направо

7>3 - да, значит идем дальше направо

7>6 - да, значит идем дальше направо

7>10 - нет, значит нужная нам ветка между 6 и 10, т.к. 6<7<10

также смотрим в узле между 6 и 10(789), слева направо

7=7 - да, нашли

Пример использования

Пользователь делает поле, например name, индексом
B-Tree записывает в себя отсортированный список имён и распределяет их по дереву
При запросе вида SELECT * FROM users WHERE name='hyilo' происходит следующее
1. B-Tree смотрит на верхний узел и сравнивает то, что мы хотим найти с записями
2. До того момента пока B-Tree не найден элемент он будет проходить по узлам
  
  ВАЖНО! B-Tree оперирует знаками <,>,= это значит что индексироваться могут и строки, и числа

B+Tree работает почти также, как и B-Tree, но у него значения находятся только на листьях, на верхних узлах значений нет - только промежутки

       [30 | 50]
      /    |    \
[10 | 20] [35 | 40] [55 | 60]

Поиск выполняется следующим образом - B+Tree начинает с верхнего узла и сравнивает значения меньше/больше, например возьмем 27. B+Tree начинает слева направо и смотрит:

27<30 - да, значит идем ниже

27<10 - нет, значит проверяем дальше этот узел

10<27<20 - нет, значит точно верно что 20<27

дальше идут такие же проверки, пока не найдем значение

Сложности

Операция	Без индекса	С B-Tree
Поиск	O(n)	O(log n)
Вставка	O(n)	O(log n)
Удаление	O(n)	O(log n)

Вставка нового значения

У дерева есть строгие правила по узлам, для разных структур данных оно может иметь разный порядок(m), в большинстве случаях берется m=4

B-Tree порядка m означает, что в одном узле:

минимум ⌈m/2⌉ − 1 ключей
максимум m − 1 ключей

Количество детей:

от ⌈m/2⌉ до m

Пример

m	Кол-во узлов	Кол-во детей
4	1-3	2-4
6	2-5	3-6
8	3-7	4-6

B-Tree

1. Поиск листа

Новое значение всегда вставляется в листовой узел.

Начинает поиск с корня
Сравнивает вставляемый ключ с ключами в узле
По диапазону выбирает нужную ветку
Повторяет, пока не дойдёт до листа

2. Вставка в лист

Ключ вставляется в отсортированном порядке
Структура дерева не меняется

Пример: Лист [10, 20, 40], вставляем 30 → [10, 20, 30, 40]

3. Переполнение узла

Если после вставки в узле стало слишком много ключей

Узел делится на два
Средний ключ поднимается в родительский узел
Левые ключи остаются в левом узле, правые — в правом

Пример:

[10 | 20 | 30 | 40 | 50]   ← переполнение

Средний ключ 30 поднимается вверх:

          [30]
         /    \
   [10 | 20]  [40 | 50]

Если родительский узел тоже переполняется после добавления среднего ключа, то операция повторяется рекурсивно вверх.

Если переполняется корень:

Создаётся новый корень
Высота дерева увеличивается на 1

B+Tree

Работает практически также

Средний ключ копируется в родителя
Все реальные данные остаются в листьях