Индексы баз данных и оптимизация производительности: B-Tree, Hash, Fulltext и Clustered

Эта статья представляет собой полный справочник по индексам баз данных и оптимизации производительности, включая B-Tree, Hash, Fulltext и Clustered индексы с практическими примерами.

Вкратце

Индексы баз данных существенно ускоряют выполнение запросов, обеспечивая быстрый доступ к данным. Различные типы индексов оптимизированы для конкретных сценариев использования.

Краткое техническое описание

Индексы баз данных представляют собой специализированные структуры данных, улучшающие скорость операций извлечения данных из таблиц. Они работают подобно предметному указателю в книге.

Типы индексов и их характеристики:

B-Tree индекс (сбалансированное дерево)

Структура: сбалансированное дерево с отсортированными значениями
Применение: поиск по равенству, диапазонные запросы, сортировка
Производительность: O(log n) для поисковых операций
Примеры: первичные ключи, внешние ключи, стандартные индексы

Hash индекс

Структура: хеш-таблица с прямой адресацией
Применение: только поиск по равенству (=)
Производительность: O(1) для точного совпадения
Примеры: табличные структуры в памяти, точный поиск

Fulltext индекс

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

Clustered индекс

Структура: физическая сортировка таблицы
Применение: первичный ключ, частые диапазонные запросы
Производительность: быстрый доступ по первичному ключу
Примеры: временные ряды, логи

Ключевые моменты

B-Tree индекс: сбалансированное дерево для поиска по равенству и диапазонных запросов
Hash индекс: прямая адресация для точного совпадения
Fulltext индекс: текстовый поиск с морфологией и релевантностью
Clustered индекс: физическое расположение данных по индексу
Производительность: оптимизация запросов с помощью индексов
Компромиссы: объем памяти против скорости
Значимость: важно для администрирования и оптимизации БД

Основные компоненты

Структура индекса: дерево, хеш, инвертированный индекс
Тип индекса: B-Tree, Hash, Fulltext, Clustered
Тип запроса: равенство, диапазон, полнотекстовый
Метрики производительности: время чтения, время записи, память
Стратегия индексирования: по одной колонке, по нескольким, covering индекс
Оптимизация: анализ EXPLAIN, туинг индексов
Обслуживание: перестроение, фрагментация, статистика

Практические примеры

1. Примеры B-Tree индекса

-- MySQL создание B-Tree индекса
CREATE INDEX idx_kunden_name ON kunden(name);
CREATE INDEX idx_bestellungen_datum ON bestellungen(bestelldatum);

-- Составной B-Tree индекс
CREATE INDEX idx_kunden_stadt_name ON kunden(stadt, name);

-- Уникальный B-Tree индекс
CREATE UNIQUE INDEX idx_email_unique ON kunden(email);

-- Запрос с использованием B-Tree индекса
EXPLAIN SELECT * FROM kunden WHERE name = 'Mustermann';
EXPLAIN SELECT * FROM bestellungen WHERE bestelldatum BETWEEN '2024-01-01' AND '2024-12-31';

-- Сравнение производительности
-- Без индекса: полное сканирование таблицы
SELECT * FROM grosse_tabelle WHERE spalte_x = 'wert';

-- С B-Tree индексом: поиск по индексу
SELECT * FROM grosse_tabelle WHERE spalte_x = 'wert';

2. Примеры Hash индекса

-- MySQL Hash индекс (только для Memory Engine)
CREATE TABLE user_sessions (
    session_id VARCHAR(255) PRIMARY KEY,
    user_id INT,
    created_at TIMESTAMP,
    data TEXT,
    INDEX ((session_id)) USING HASH
) ENGINE=MEMORY;

-- PostgreSQL Hash индекс
CREATE INDEX idx_hash_email ON benutzer USING HASH (email);

-- Запрос с Hash индексом (только равенство)
SELECT * FROM benutzer WHERE email = 'user@example.com';

-- Hash индекс НЕ используется для:
SELECT * FROM benutzer WHERE email LIKE 'user%';  -- Диапазонный поиск
SELECT * FROM benutzer WHERE email > 'a';        -- Операция сравнения

3. Примеры Fulltext индекса

-- MySQL Fulltext индекс
CREATE TABLE artikel (
    id INT PRIMARY KEY,
    titel VARCHAR(255),
    inhalt TEXT,
    FULLTEXT KEY ft_inhalt (titel, inhalt)
);

-- Полнотекстовый поиск
SELECT titel, inhalt 
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE);

-- С показателем релевантности
SELECT titel, 
       MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE) AS score
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE)
ORDER BY score DESC;

-- Boolean режим для сложных поисков
SELECT titel, inhalt
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('+datenbank +performance -mysql' IN BOOLEAN MODE);

-- PostgreSQL Fulltext индекс
CREATE TABLE dokumente (
    id SERIAL PRIMARY KEY,
    titel VARCHAR(255),
    inhalt TEXT
);

-- Fulltext индекс с tsvector
ALTER TABLE dokumente ADD COLUMN searchable_text tsvector;
UPDATE dokumente SET searchable_text = to_tsvector('german', titel || ' ' || inhalt);
CREATE INDEX idx_fulltext ON dokumente USING GIN(searchable_text);

-- Полнотекстовый поиск в PostgreSQL
SELECT titel, ts_rank(searchable_text, plainto_tsquery('german', 'datenbank performance')) AS rank
FROM dokumente 
WHERE searchable_text @@ plainto_tsquery('german', 'datenbank performance')
ORDER BY rank DESC;

4. Примеры Clustered индекса

-- SQL Server Clustered индекс
CREATE TABLE log_daten (
    log_id INT IDENTITY(1,1),
    zeitstempel DATETIME NOT NULL,
    nachricht VARCHAR(1000),
    level VARCHAR(10)
);

-- Clustered индекс по временной метке (физическая сортировка)
CREATE CLUSTERED INDEX idx_log_zeitstempel ON log_daten(zeitstempel);

-- PostgreSQL Clustered индекс (CLUSTER)
CREATE TABLE messwerte (
    id SERIAL PRIMARY KEY,
    sensor_id INT,
    zeitpunkt TIMESTAMP NOT NULL,
    wert DECIMAL(10,4)
);

-- Clustered индекс по первичному ключу (стандартно)
CREATE INDEX idx_messwerte_zeitpunkt ON messwerte(zeitpunkt);

-- Кластеризация таблицы по индексу
CLUSTER messwerte USING idx_messwerte_zeitpunkt;

-- MySQL InnoDB Clustered индекс (автоматически по первичному ключу)
CREATE TABLE transaktionen (
    id BIGINT PRIMARY KEY,  -- Автоматически clustered
    konto_id INT,
    betrag DECIMAL(12,2),
    datum DATETIME,
    INDEX idx_konto_datum (konto_id, datum)  -- Вторичный индекс
);

5. Анализ производительности с EXPLAIN

-- MySQL EXPLAIN анализ
EXPLAIN FORMAT=JSON
SELECT k.name, b.bestelldatum, b.gesamtbetrag
FROM kunden k
JOIN bestellungen b ON k.id = b.kunden_id
WHERE k.stadt = 'Berlin'
  AND b.bestelldatum >= '2024-01-01'
ORDER BY b.gesamtbetrag DESC;

-- PostgreSQL EXPLAIN ANALYZE
EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON)
SELECT k.name, b.bestelldatum, b.gesamtbetrag
FROM kunden k
JOIN bestellungen b ON k.id = b.kunden_id
WHERE k.stadt = 'Berlin'
  AND b.bestelldatum >= '2024-01-01'
ORDER BY b.gesamtbetrag DESC;

-- Проверка использования индексов
-- MySQL: SHOW INDEX FROM tabelle;
SHOW INDEX FROM kunden;

-- PostgreSQL: \d tabelle
-- или представление pg_indexes
SELECT indexname, indexdef 
FROM pg_indexes 
WHERE tablename = 'kunden';

6. Оптимизация индексов и лучшие практики

-- Covering индекс (все необходимые столбцы в индексе)
CREATE INDEX idx_kunden_covering ON kunden(stadt, name, id);

-- Запрос использует только индекс (Index-Only Scan)
SELECT id, name FROM kunden WHERE stadt = 'Berlin';

-- Частичный индекс (только для части данных)
CREATE INDEX idx_aktive_kunden ON kunden(id) WHERE status = 'aktiv';

-- Индекс на основе функции (PostgreSQL)
CREATE INDEX idx_kunden_name_lower ON kunden(LOWER(name));

-- Запрос использует индекс на основе функции
SELECT * FROM kunden WHERE LOWER(name) = 'mustermann';

-- Составной индекс с правильным порядком столбцов
CREATE INDEX idx_bestellungen_optimal ON bestellungen(kunden_id, bestelldatum, status);

-- Хороший запрос (полностью использует индекс)
SELECT * FROM bestellungen 
WHERE kunden_id = 123 
  AND bestelldatum >= '2024-01-01' 
  AND status = 'completed';

-- Плохой запрос (не может использовать индекс)
SELECT * FROM bestellungen 
WHERE status = 'completed' 
  AND bestelldatum >= '2024-01-01';  -- Первый столбец не в WHERE

7. Обслуживание и мониторинг индексов

-- Обновление статистики индексов
-- MySQL
ANALYZE TABLE kunden;

-- PostgreSQL
ANALYZE kunden;

-- Проверка фрагментации индексов
-- SQL Server
SELECT * FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('kunden'), NULL, NULL, 'DETAILED');

-- PostgreSQL
SELECT schemaname, tablename, attname, n_distinct, correlation 
FROM pg_stats 
WHERE tablename = 'kunden';

-- Перестройка индексов при фрагментации
-- SQL Server
ALTER INDEX ALL ON kunden REBUILD;

-- MySQL (InnoDB)
ANALYZE TABLE kunden;  -- Обновление статистики
OPTIMIZE TABLE kunden;  -- Оптимизация таблицы

-- PostgreSQL
REINDEX INDEX idx_kunden_name;

Сравнение производительности типов индексов

Тип индекса	Тип поиска	Производительность	Память	Применение
B-Tree	Равенство, диапазон	O(log n)	Средняя	Стандартные индексы
Hash	Только равенство	O(1)	Низкая	Таблицы в памяти
Fulltext	Полнотекстовый	Переменная	Высокая	Поиск по тексту
Clustered	Первичный ключ	O(log n)	Таблица	Частые обращения

Стратегии индексирования

Индекс на одну колонку

-- Простой индекс для одной колонки
CREATE INDEX idx_kunden_email ON kunden(email);

Составной индекс

-- Композитный индекс с оптимальным порядком колонок
CREATE INDEX idx_kunden_stadt_name ON kunden(stadt, name);

Покрывающий индекс

-- Индекс содержит все необходимые колонки
CREATE INDEX idx_bestellungen_covering ON bestellungen(kunden_id, bestelldatum, gesamtbetrag);

Частичный индекс

-- Индекс только для части данных
CREATE INDEX idx_aktive_kunden ON kunden(id) WHERE status = 'aktiv';

Функциональный индекс

-- Индекс на вычисляемые значения
CREATE INDEX idx_kunden_name_lower ON kunden(LOWER(name));

Оптимизация запросов

Максимизация использования индексов

-- ХОРОШИЕ запросы (используют индексы)
SELECT * FROM kunden WHERE stadt = 'Berlin';                    -- Индекс на одну колонку
SELECT * FROM bestellungen WHERE kunden_id = 123 AND datum > '2024-01-01'; -- Составной индекс
SELECT * FROM artikel WHERE MATCH(titel) AGAINST('suchbegriff');    -- Полнотекстовый индекс

-- ПЛОХИЕ запросы (не используют индексы)
SELECT * FROM kunden WHERE LOWER(name) = 'mustermann';           -- Нет функционального индекса
SELECT * FROM bestellungen WHERE YEAR(datum) = 2024;            -- Функция на колонке
SELECT * FROM kunden WHERE name LIKE '%mustermann%';             -- Подстановочный символ в начале

Анализ с помощью EXPLAIN

-- MySQL
EXPLAIN SELECT * FROM kunden WHERE stadt = 'Berlin';

-- Важные колонки:
-- type: ALL (плохо), ref, range, index (хорошо)
-- key: Используемый индекс
-- rows: Оценка количества строк
-- Extra: Using index (хорошо), Using filesort (плохо)

-- PostgreSQL
EXPLAIN ANALYZE SELECT * FROM kunden WHERE stadt = 'Berlin';

-- Важная информация:
-- Seq Scan vs Index Scan
-- Index-Only Scan (очень хорошо)
-- Фактическое время выполнения

Преимущества и недостатки

Преимущества индексов

Производительность: Значительное ускорение запросов
Сортировка: ORDER BY без дополнительной обработки
Уникальность: UNIQUE-индексы гарантируют целостность данных
Объединения: Индексы на внешних ключах ускоряют JOINs

Недостатки

Место на диске: Индексы требуют дополнительную память
Производительность записи: INSERT/UPDATE/DELETE становятся медленнее
Обслуживание: Индексы нужно периодически оптимизировать
Издержки: Слишком много индексов может привести к противоположному эффекту

Лучшие практики

Когда создавать индексы

Частые условия WHERE
Условия для JOIN
Клаузулы ORDER BY
Клаузулы GROUP BY
UNIQUE-ограничения

Когда избегать индексов

Редко используемые колонки
Таблицы с малым количеством строк
Колонки с высокой кардинальностью и низкой избирательностью
Таблицы с частыми операциями UPDATE/DELETE

Проектирование индексов

Порядок колонок: По убыванию избирательности
Ширина индекса: Как можно уже
Покрывающий индекс: Включите все нужные колонки
Частичный индекс: Только для релевантных данных

Типичные вопросы на собеседовании

В чём разница между B-Tree и Hash индексом? B-Tree поддерживает поиск по равенству и диапазону, Hash только по равенству.
Когда использовать полнотекстовый индекс? Для поиска по тексту в больших текстовых полях с учётом морфологии и релевантности.
Объясните разницу между Clustered и Non-Clustered индексом! Clustered: физическое расположение данных, Non-Clustered: отдельная структура индекса.
Как проверить, используется ли индекс? С помощью EXPLAIN/EXPLAIN ANALYZE для анализа плана выполнения запроса.

Основные источники

Рекомендуемая литература: Базы данных

Keine Bücher für Kategorie "datenbanken" gefunden.

Täglicher Artikel