Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
# B-дерево (B-tree)
Определение
B-дерево — это сбалансированная структура данных, оптимизированная для работы с дисковой памятью. Оно используется в базах данных и файловых системах для эффективного поиска, вставки и удаления данных на больших объёмах.
В отличие от обычных бинарных деревьев, B-дерево может иметь много потомков (не только 2) и хранить несколько значений в одном узле.
Проблема без B-дерева
Бинарное дерево поиска (BST)
Обычное BST:
50
/ \
30 70
/ \ / \
20 40 60 80
Проблемы:
1. Дисбаланс (худший случай O(n))
2. Много дисковых операций (каждый уровень = дисковый доступ)
3. Неэффективно для больших данных на диске
B-дерево
B-дерево порядка 3:
[30, 70]
/ | \
[10,20] [40,60] [80,90]
Преимущества:
1. Всегда сбалансировано
2. Меньше уровней (логарифмическое)
3. Оптимально для дисковых операций
4. Целые узлы читаются за один диск-доступ
Структура B-дерева
Свойства B-дерева порядка m
- Каждый узел содержит до m-1 значений
- Каждый внутренний узел имеет до m потомков
- Все листья на одном уровне (сбалансированность гарантирована)
- Значения в узле отсортированы
- Корень содержит хотя бы 1 значение
- Внутренний узел содержит хотя бы ceil(m/2) потомков
Пример B-дерева порядка 4
Количество ключей на узел: 1-3
Количество потомков: 2-4
Уровень 0: [25, 50, 75]
/ | | \
/ | | \
Уровень 1: [10,15,20] [30,40] [60,70] [80,90]
/| | | / | | / | | / | |
Уровень 2: листья с отдельными значениями
Почему B-дерево используется в БД
1. Дисковая оптимизация
Про: Узел B-дерева = один блок диска (обычно 4KB)
Бинарное дерево:
- Найти значение: 20 дисковых операций
- 20 операций × 10ms = 200ms
B-дерево (порядок 256):
- Найти значение: ~3 дисковых операции
- 3 операции × 10ms = 30ms
- Это 6-7x быстрее!
2. Минимизация уровней
BST с 1 000 000 элементов: до 20 уровней
B-дерево порядка 256 с 1 000 000 элементов: ~4 уровней
Разница в дисковых операциях: 20 vs 4 доступов
3. Последовательный доступ
// B-дерево позволяет эффективно получить диапазон значений
// SELECT * FROM users WHERE age BETWEEN 20 AND 30
// В B-дереве все листья связаны (linked list)
// Быстрый диапазонный запрос без поиска каждого значения
Операции в B-дереве
1. Поиск
public class BTreeNode {
int[] keys; // Значения в узле
BTreeNode[] children; // Потомки
boolean isLeaf;
int n; // Текущее количество ключей
// Поиск значения
public BTreeNode search(int key) {
int i = 0;
// Найти позицию
while (i < n && key > keys[i]) {
i++;
}
// Найдено
if (i < n && key == keys[i]) {
return this;
}
// Лист достигнут
if (isLeaf) {
return null;
}
// Рекурсивный поиск в потомке
return children[i].search(key);
}
}
// Сложность: O(log n)
2. Вставка
public class BTree {
private BTreeNode root;
private int order; // m
public void insert(int key) {
// Если корень полон, создаём новый корень
if (root.n == order - 1) {
BTreeNode newRoot = new BTreeNode();
newRoot.isLeaf = false;
newRoot.children[0] = root;
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key);
}
private void insertNonFull(BTreeNode node, int key) {
int i = node.n - 1;
if (node.isLeaf) {
// Сдвигаем элементы и вставляем
while (i >= 0 && key < node.keys[i]) {
node.keys[i + 1] = node.keys[i];
i--;
}
node.keys[i + 1] = key;
node.n++;
} else {
// Находим нужного потомка
while (i >= 0 && key < node.keys[i]) {
i--;
}
i++;
// Если потомок полон, делим его
if (node.children[i].n == order - 1) {
splitChild(node, i);
if (key > node.keys[i]) {
i++;
}
}
insertNonFull(node.children[i], key);
}
}
private void splitChild(BTreeNode parent, int i) {
// Разделяем переполненного потомка
BTreeNode fullChild = parent.children[i];
BTreeNode newChild = new BTreeNode();
newChild.isLeaf = fullChild.isLeaf;
newChild.n = order / 2 - 1;
// Копируем вторую половину ключей
for (int j = 0; j < order / 2 - 1; j++) {
newChild.keys[j] = fullChild.keys[j + order / 2];
}
// Если не лист, копируем потомков
if (!fullChild.isLeaf) {
for (int j = 0; j < order / 2; j++) {
newChild.children[j] = fullChild.children[j + order / 2];
}
}
fullChild.n = order / 2 - 1;
// Сдвигаем потомков родителя
for (int j = parent.n; j > i; j--) {
parent.children[j + 1] = parent.children[j];
}
parent.children[i + 1] = newChild;
// Сдвигаем ключи родителя
for (int j = parent.n - 1; j >= i; j--) {
parent.keys[j + 1] = parent.keys[j];
}
parent.keys[i] = fullChild.keys[order / 2 - 1];
parent.n++;
}
}
// Сложность вставки: O(log n)
3. Удаление
// Удаление сложнее, требует балансировки
// Может быть из листа или внутреннего узла
// Требует слияния/перемещения соседних узлов
public void delete(int key) {
delete(root, key);
// Если корень пуст, делаем его единственным потомком новым корнем
if (root.n == 0) {
if (!root.isLeaf && root.children[0] != null) {
root = root.children[0];
}
}
}
// Сложность удаления: O(log n)
Использование в базах данных
MySQL (InnoDB)
-- InnoDB использует B+-дерево для индексов
CREATE TABLE users (
id INT PRIMARY KEY, -- Индекс на B-дереве
name VARCHAR(100),
age INT
);
-- Индекс на B-дереве
CREATE INDEX idx_age ON users(age);
-- Быстрый поиск благодаря B-дереву
SELECT * FROM users WHERE age = 25;
-- 3-4 дисковых доступа вместо full table scan
PostgreSQL
-- PostgreSQL использует B+-дерево по умолчанию
CREATE INDEX idx_users_age ON users USING btree(age);
-- Диапазонный запрос эффективен
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
-- Быстрый поиск левой границы, затем линейный проход
JDBC пример
public class UserRepository {
public User findById(Long id) {
// БД использует B-дерево для PRIMARY KEY индекса
// Это позволяет найти запись за ~3 дисковых доступа
String sql = "SELECT * FROM users WHERE id = ?";
// ...
}
public List<User> findByAgeRange(int minAge, int maxAge) {
// БД использует B-дерево для индекса на age
// Диапазонный поиск эффективен
String sql = "SELECT * FROM users WHERE age BETWEEN ? AND ?";
// ...
}
}
B+ дерево (расширение B-дерева)
Разница от B-дерева:
- Только листья содержат полные данные
- Внутренние узлы содержат только ключи для навигации
- Листья связаны (linked list) для быстрого диапазонного поиска
Преимущества:
- Ещё лучше для диапазонных запросов
- Используется в большинстве БД (MySQL, PostgreSQL, SQLite)
Пример:
[30, 70]
/ | \
[10,20] [40,60] [80,90]
|| || ||
листья с данными, связаны в список
Практический пример: когда B-дерево критично
// Сценарий: 10 миллионов записей
// БЕЗ индекса (полный скан)
SELECT * FROM orders WHERE customer_id = 12345;
// 10,000,000 проверок
// ~100 секунд на жёстком диске
// С B-дереве индексом
SELECT * FROM orders WHERE customer_id = 12345;
// ~4 дисковых доступа
// ~40 миллисекунд на жёстком диске
// 2500x БЫСТРЕЕ!
Резюме
B-дерево нужно для:
- Оптимизации дисковых операций — узел B-дерева = один блок диска
- Гарантированной балансировки — все листья на одном уровне
- Эффективного поиска — O(log n) дисковых операций
- Диапазонного поиска — благодаря отсортированным ключам
- Масштабируемости — работает с миллиардами записей
Это основа всех современных баз данных. Без B-деревьев работа с большими объёмами данных была бы невозможна.