← Назад к вопросам
Какую структуру данных использует индекс в базе данных?
2.0 Middle🔥 181 комментариев
#Базы данных (SQL)
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Структуры данных для индексов в базах данных
Индекс — это структура данных, которая позволяет быстро найти нужные строки без сканирования всей таблицы. Используются различные структуры данных в зависимости от типа индекса и БД.
1. B-tree (B-дерево) — самый популярный индекс
# B-tree используется в PostgreSQL, MySQL, SQLite
# Дерево сбалансировано, глубина логарифмична
# Структура B-tree для индекса на поле age:
# [30]
# / \
# [10, 20] [40, 50, 60]
# / | \ / | | \
# 5 15 25 35 45 55 65
# Вставка индекса
CREATE INDEX idx_users_age ON users(age);
# Поиск быстрый: O(log n)
SELECT * FROM users WHERE age = 30; # ~ 3-4 обращения к диску
# Диапазонные запросы эффективны
SELECT * FROM users WHERE age BETWEEN 25 AND 35; # Линейное в диапазоне
Характеристики:
- Поиск: O(log n)
- Вставка: O(log n)
- Удаление: O(log n)
- Диапазонные запросы: ✅ Эффективны
- Сортировка: ✅ Естественная сортировка
# Визуализация высоты B-tree
# 1 миллион записей:
# B-tree(100) - глубина ~3-4
# Линейный поиск - 1,000,000 операций
# B-tree поиск - ~4 операции (+ 4 чтения с диска)
2. Hash Index — для точного совпадения
# Hash используется в памяти и в некоторых БД
# Структура: hash_table[hash(key)] -> значение
hash_table = {}
hash_table[hash("alice@example.com")] = 1 # user_id
hash_table[hash("bob@example.com")] = 2
# Поиск за O(1) в среднем
CREATE INDEX idx_users_email ON users(email) USING HASH;
SELECT * FROM users WHERE email = 'alice@example.com'; # O(1)
# Но диапазонные запросы НЕ эффективны
# SELECT * FROM users WHERE email LIKE 'alice%'; # Полное сканирование!
Характеристики:
- Точный поиск: O(1) в среднем
- Диапазонные запросы: ❌ Не эффективны
- Сортировка: ❌ Не помогает
- Память: Меньше чем B-tree
3. Bitmap Index — для категориальных данных
# Bitmap используется для столбцов с малым числом значений
# gender, status, is_active и т.д.
# Структура (для gender)
value = 'male'
bitmap: 1011001010101... (1 = мужчина, 0 = не мужчина)
value = 'female'
bitmap: 0100110101010... (1 = женщина, 0 = не женщина)
# Поиск очень быстрый и компактный
SELECT COUNT(*) FROM users WHERE gender = 'male'; # Считает единицы в bitmap
# Особенно эффективны для COUNT и HAVING
SELECT status, COUNT(*) FROM users GROUP BY status; # Использует bitmap
Характеристики:
- Поиск: O(1)
- Занимает памяти: Очень мало
- Для: Категориальные данные (enum-like)
- Неэффективны для: Уникальные значения
4. Inverted Index (Full-Text Index)
# Используется для полнотекстового поиска
# Структура (для полей text)
slovo: [doc1, doc3, doc5] # Документы содержащие слово
krasota: [doc2, doc4]
mir: [doc1, doc2, doc3]
# Поиск очень быстрый для текста
CREATE INDEX idx_articles_text ON articles USING GIN(content);
SELECT * FROM articles
WHERE content @@ plainto_tsquery('english', 'красота мира');
# Без индекса пришлось бы сканировать все документы
Характеристики:
- Полнотекстовый поиск: ✅ Очень быстро
- Фильтрация: ✅ Эффективна
- Занимает памяти: Много
- Обновления: Медленнее чем B-tree
5. R-tree Index — для геопространственных данных
# Для koordinat (x, y) или полигонов
# Структура (иерархия прямоугольников)
# +--------+
# | Region |
# +---+----+
# / | \
# +--+ +-+-+ +--+
# |NW| |NE| |SE|
# +--+ +-+-+ +--+
# Поиск близких точек
CREATE INDEX idx_locations_geo ON locations USING GIST(coordinates);
SELECT * FROM locations
WHERE coordinates <@ 'circle((55.75,37.62),1km)'::circle; # В радиусе 1км
# Без индекса пришлось бы проверять расстояние для каждой точки
Характеристики:
- Поиск по области: ✅ O(log n)
- Ближайший сосед (KNN): ✅ Быстро
- Диапазонные запросы: ✅ По координатам
6. Trie (Prefix Tree) — для префиксного поиска
# Структура (для поиска по префиксу)
# root
# / | \
# a b c
# | | |
# l o a
# | | |
# i b t
# | |
# c (cat)
# |
# (alic)
#
# Вставка: alice, alic, bob, bob, cat
# Поиск по префиксу: O(m) где m длина префикса
def find_by_prefix(trie, prefix):
node = trie.root
for char in prefix:
node = node.children.get(char)
if not node:
return [] # Нет совпадений
return node.get_all_words() # Все слова с этим префиксом
# SQL (PostgreSQL с расширением)
CREATE INDEX idx_email_prefix ON users USING GIST(email gist_trgm_ops);
SELECT * FROM users WHERE email LIKE 'alice%'; # Быстро!
Характеристики:
- Префиксный поиск: ✅ O(m)
- Частичный поиск: ✅ Эффективен
- Память: Много (для больших наборов)
7. GiST (Generalized Search Tree) — универсальная структура
# Используется в PostgreSQL для расширяемых индексов
# Может использоваться для:
# - JSON документов
# - Текста (полнотекстовый поиск)
# - Геопространственных данных
# - Диапазонов
CREATE INDEX idx_json_data ON documents USING GiST(data);
CREATE INDEX idx_text_full ON articles USING GiST(content);
CREATE INDEX idx_geometry ON locations USING GiST(geom);
# GiST можно расширять под свои типы данных
8. BRIN (Block Range Index) — для больших таблиц
# Компактный индекс для очень больших таблиц
# Занимает мало памяти
# Структура: делит таблицу на блоки и хранит диапазоны значений
# Блок 1 (rows 1-10000): age [18, 65]
# Блок 2 (rows 10001-20000): age [20, 70]
# Блок 3 (rows 20001-30000): age [19, 68]
CREATE INDEX idx_logs_timestamp ON logs USING BRIN(created_at);
SELECT * FROM logs WHERE created_at > '2024-01-01'; # Быстро
# Идеален для временных рядов (logx, sensors, events)
Характеристики:
- Размер индекса: Очень маленький
- Скорость запроса: Хорошая
- Идеально для: Временные ряды, логи
9. Композитные индексы (Composite Indexes)
# Индекс на нескольких полях одновременно
# Порядок очень важен!
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at DESC);
# Хороший индекс для:
SELECT * FROM orders WHERE user_id = 1 ORDER BY created_at DESC;
# Плохой индекс для (не может использовать порядок):
SELECT * FROM orders WHERE created_at > '2024-01-01' ORDER BY user_id;
# Правило: WHERE поля в начале, ORDER BY в конце
# WHERE user_id = 1 AND status = 'done' ORDER BY created_at
# CREATE INDEX idx ON orders(user_id, status, created_at DESC)
10. Сравнение структур индексов
| Структура | Точный поиск | Диапазон | Префикс | Текст | Память | Обновления |
|---|---|---|---|---|---|---|
| B-tree | ✅ O(log n) | ✅ O(log n) | ❌ | ❌ | Средняя | Быстро |
| Hash | ✅ O(1) | ❌ | ❌ | ❌ | Малая | Быстро |
| Bitmap | ✅ O(1) | ❌ | ❌ | ❌ | Очень малая | Медленно |
| Trie | ❌ | ❌ | ✅ O(m) | ❌ | Много | Быстро |
| Inverted | ❌ | ❌ | ❌ | ✅ | Много | Медленно |
| R-tree | ❌ | ✅ (2D) | ❌ | ❌ | Много | Медленно |
| GiST | Variable | ✅ | ✅ | ✅ | Много | Медленно |
| BRIN | ❌ | ✅ | ❌ | ❌ | Очень малая | Быстро |
Когда какой индекс использовать
# Уникальный поиск по email
CREATE INDEX USING HASH; # или UNIQUE B-tree
# Диапазонные запросы по датам
CREATE INDEX USING B-tree;
# Поиск по статусу (мало уникальных значений)
CREATE INDEX USING BITMAP;
# Полнотекстовый поиск
CREATE INDEX USING GIN;
# Геопространственный поиск
CREATE INDEX USING GIST;
# Очень большая таблица логов
CREATE INDEX USING BRIN;
# Поиск по префиксу (начало строки)
CREATE INDEX USING GiST (... gist_trgm_ops);
Правила создания индексов
# 1. Индекс на часто используемые WHERE поля
SELECT * FROM users WHERE status = 'active'; # Нужен индекс
# 2. Индекс на ORDER BY и GROUP BY
SELECT * FROM orders ORDER BY created_at DESC; # Индекс помогает
# 3. Чем больше таблица, тем больше пользы от индекса
# На 100 строк: O(100) vs O(log 100) ~ 7 - не значительно
# На 1 000 000 строк: O(1000000) vs O(log 1000000) ~ 20 - очень значительно
# 4. Индекс замедляет вставки и обновления
# Баланс: индексы ускоряют чтение, замедляют запись
# 5. Не переусложняй
# 1-2 индекса на таблицу в простых случаях
# Сложные приложения: 5-10 индексов на таблицу
Заключение
Выбор структуры индекса критически важен для производительности. B-tree — универсальный выбор, но для специальных случаев (текст, геометрия, большие таблицы) нужны специализированные индексы. Профессиональные разработчики анализируют EXPLAIN PLAN и выбирают индексы на основе реальных запросов.