Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Структура данных индекса: B-Tree
Индекс в базе данных — это структура данных, которая ускоряет поиск записей в таблице. Основная структура, используемая почти во всех современных базах данных для индексов — это B-Tree (Balanced Tree).
Что такое B-Tree?
B-Tree (B-дерево) — это самобалансирующееся дерево поиска, которое оптимизировано для дисковых операций и используется в базах данных.
Примеры B-дерева (порядок 3):
[30, 70]
/ | \
[10,20] [40,60] [80,90]
Каждый узел может содержать до n-1 ключей и n детей
Характеристики B-Tree
Свойства B-Tree:
├─ Самобалансирующееся (self-balancing)
├─ Все листья на одной глубине
├─ Узлы содержат несколько ключей (не как в бинарном дереве)
├─ Все операции O(log n)
├─ Оптимизировано для дисковых операций
├─ Каждый узел соответствует блоку на диске
└─ Минимизирует количество дисковых обращений
Структура узла B-Tree
Узел B-Tree (порядка m):
[Key1] [Key2] [Key3] ... [Keyn]
| | | |
*------*------*----------*
| | | |
Ptr0 Ptr1 Ptr2 Ptr3
Примечание:
- Ключи отсортированы
- Pointers (указатели) на дочерние узлы
- Если узел содержит k ключей, он имеет k+1 указателей
Пример реального B-Tree из индекса базы данных
Индекс таблицы users по полю user_id:
[100, 300, 500]
/ | |\
[50] [150,200] [400] [700]
/ \ / | \ / \ / \
[10] [60] [110] [160] [250] [350] [600] [800]
Поиск user_id = 250:
1. Начинаем с корня [100, 300, 500]
2. 250 < 300, ищем во втором поддереве
3. Смотрим [150, 200] → 250 > 200
4. Ищем в третьем поддереве [250]
5. Найдено! Одно дисковое обращение, несколько сравнений в памяти
Преимущества B-Tree для баз данных
1. ЭФФЕКТИВНОСТЬ ДИСКОВЫХ ОПЕРАЦИЙ
├─ Каждый узел = блок на диске (обычно 4KB)
├─ Одно прочтение узла = одно дисковое обращение
├─ B-Tree минимизирует глубину → минимизирует обращения
└─ Поиск в миллионе записей = 3-4 дисковых обращения
2. ЛОГАРИФМИЧЕСКАЯ СЛОЖНОСТЬ
├─ Поиск: O(log n)
├─ Вставка: O(log n)
├─ Удаление: O(log n)
└─ n = количество записей в таблице
3. ДИАПАЗОННЫЕ ЗАПРОСЫ
├─ SELECT * WHERE id BETWEEN 100 AND 200
├─ Просто идти от листа к листу
└─ Всё отсортировано в естественном порядке
4. СОРТИРОВКА
├─ Индекс уже отсортирован
├─ SELECT * FROM users ORDER BY id
└─ Просто итерируем листья слева направо
5. БАЛАНСИРОВАНИЕ
├─ Автоматическое при вставках и удалениях
├─ Гарантирует O(log n) всегда
└─ Нет деградации производительности
Отличие B-Tree от других структур
B-Tree B+Tree Hash Red-Black
────────────────────────────────────────────────────────────────────────
Поиск O(log n) O(log n) O(1) O(log n)
Диапазон ✓ отлично ✓ отлично ✗ плохо ✓ хорошо
Сортировка ✓ есть ✓ есть ✗ нет ✓ есть
Сканирование Средне ✓ отлично ✓ плохо Средне
Мемория Меньше Больше Средне Среднее
Вставка O(log n) O(log n) O(1) O(log n)
Удаление O(log n) O(log n) O(1) O(log n)
✓ = хорошо ✗ = плохо
B+Tree (вариант B-Tree)
B+Tree используется в большинстве СУБД (MySQL, PostgreSQL) для индексов.
Отличие от B-Tree:
B-Tree:
[30, 70] ← данные в узлах
/ | \
[10,20] [40,60] [80,90]
B+Tree:
[30, 70] ← только ключи
/ | \
[10,20] [40,60] [80,90] ← листья, они связаны
| | | ↓
leaf → leaf → leaf → null
Данные хранятся ТОЛЬКО в листьях!
Преимущества B+Tree:
1. Полное сканирование листьев (очень быстро)
2. Диапазонные запросы (всё рядом в листьях)
3. Кеширование (внутренние узлы всегда в памяти)
4. Лучше для SSD (последовательный доступ)
Примеры индексов в разных базах данных
MySQL (InnoDB)
-- Первичный индекс (Primary Key) — B+Tree
CREATE TABLE users (
id INT PRIMARY KEY, -- B+Tree индекс
email VARCHAR(255) UNIQUE, -- B+Tree индекс
name VARCHAR(100),
age INT
);
-- Просмотр индексов
SHOW INDEXES FROM users;
/*
Table | Non_unique | Key_name | Seq_in_index | Column_name | Index_type
------+------------+----------+--------------+-------------+-----------
users | 0 | PRIMARY | 1 | id | BTREE
users | 0 | email | 1 | email | BTREE
*/
-- Составной индекс (Composite Index)
CREATE INDEX idx_name_age ON users(name, age);
-- Запрос использует индекс
EXPLAIN SELECT * FROM users WHERE id = 123;
/*
id | select_type | table | type | possible_keys | key | rows | Extra
1 | SIMPLE | users | const | PRIMARY | PRIMARY | 1 | NULL
*/
PostgreSQL
-- B-Tree индекс (по умолчанию)
CREATE INDEX idx_users_id ON users(id);
-- Hash индекс (для равенства)
CREATE INDEX idx_users_status ON users(status) USING HASH;
-- GiST индекс (для geometric data)
CREATE INDEX idx_geo ON locations USING GIST(point);
-- GIN индекс (для полнотекстового поиска)
CREATE INDEX idx_search ON documents USING GIN(to_tsvector('russian', body));
-- BRIN индекс (для больших таблиц)
CREATE INDEX idx_big_table ON big_table USING BRIN(timestamp);
Как работает поиск в B-Tree индексе
// Симуляция поиска в B-Tree
public class BTreeSearch {
public static void main(String[] args) {
// Таблица: 1 млн пользователей
// Индекс по user_id (B-Tree, порядка ~100)
// Запрос: SELECT * FROM users WHERE id = 500000;
// Шаги:
// 1. Прочитать корневой узел (1 дисковое обращение)
// Узел содержит ~100 ключей
// 500000 → идём вправо
// 2. Прочитать узел-потомок (1 дисковое обращение)
// Узел содержит ~100 ключей
// 500000 → идём вправо
// 3. Прочитать узел-потомок (1 дисковое обращение)
// Узел содержит ~100 ключей
// 500000 → идём вправо
// 4. Прочитать листовой узел (1 дисковое обращение)
// Нашли 500000!
// ИТОГО: 4 дисковых обращения для 1 млн записей
// БЕЗ индекса: полное сканирование таблицы = 10000+ обращений!
}
}
Вставка в B-Tree
Вставка значения 25 в B-Tree (порядка 3):
До вставки:
[30, 70]
/ | \
[10,20] [40,60] [80,90]
Вставляем 25:
[30, 70] ← 25 идёт сюда? Нет, в левое поддерево
/ | \
[10,20,25] [40,60] [80,90] ← узел заполнен! (3 элемента в узле порядка 3)
Вот и всё! Узел имеет ≤ 2 элемента, 3 элемента — это критично для порядка 3
Когда индексы помогают
-- ✅ ХОП-НО ИЩИТЕ ИНДЕКС
SELECT * FROM users WHERE id = 123; -- точный поиск
SELECT * FROM users WHERE email = 'a@b.c'; -- точный поиск
SELECT * FROM users WHERE id BETWEEN 1 AND 100; -- диапазон
SELECT * FROM users WHERE id > 500 ORDER BY id; -- сортировка
SELECT COUNT(*) FROM users WHERE age < 30; -- подсчёт
-- ❌ ИНДЕКС НЕ ПОМОГАЕТ
SELECT * FROM users WHERE age < 30; -- нужен индекс по age
SELECT * FROM users WHERE name LIKE '%john%'; -- нужен FULLTEXT индекс
SELECT * FROM users WHERE UPPER(email) = 'A@B.C'; -- функции
Размер индекса
Таблица: 10 млн пользователей
Каждая строка: ~200 байт
Общий размер таблицы: 2 GB
Индекс по id (8 байт):
├─ Листья B+Tree: ~80 MB (10M * 8 байт)
├─ Внутренние узлы: ~1 MB
└─ Итого: ~81 MB (4% от таблицы)
Индекс по email (256 байт):
├─ Листья B+Tree: ~2.5 GB (10M * 256 байт)
├─ Внутренние узлы: ~50 MB
└─ Итого: ~2.5 GB (125% от таблицы!) ← слишком большой
Виды индексов в Java/Spring приложениях
// В JPA/Hibernate
@Entity
@Table(
name = "users",
indexes = {
@Index(name = "idx_email", columnList = "email", unique = true),
@Index(name = "idx_status", columnList = "status"),
@Index(name = "idx_created", columnList = "created_at")
}
)
public class User {
@Id
private Long id; // Автоматический индекс (PRIMARY KEY)
@Column(unique = true)
private String email; // Уникальный индекс
@Indexed // Из Hibernate Search
private String name;
}
// В Java Collections
// HashMap использует Hash таблицу (O(1) поиск)
Map<String, User> users = new HashMap<>();
// TreeMap использует Red-Black Tree (O(log n), отсортирована)
Map<String, User> users = new TreeMap<>();
Выводы
Индекс — это B-Tree или B+Tree структура данных, которая:
✅ Ускоряет поиск с O(n) до O(log n) ✅ Оптимизирован для диска (каждый узел = блок) ✅ Самобалансирующийся (гарантирует O(log n)) ✅ Поддерживает диапазонные запросы (благодаря сортировке) ✅ Использует немного памяти (обычно 5-10% от таблицы)
⚠️ Но есть недостатки: ❌ Замедляет вставки и обновления (нужно обновлять индекс) ❌ Занимает место на диске ❌ Нужно поддерживать (ANALYZE, VACUUM) ❌ Неправильный индекс хуже, чем его отсутствие
Когда использовать индексы:
- Первичные ключи → всегда!
- Уникальные поля → всегда!
- Часто используемые WHERE условия → да
- ORDER BY поля → да
- Foreign keys → обычно да
- Редко используемые поля → нет
- Очень широкие колонки (VARCHAR(1000)) → нет
Правило 80/20:
- 80% производительности даст правильный индекс по 1 полю
- 20% приносят составные индексы и оптимизация запросов