Всегда ли индекс является деревом?

Индексы в БД: всегда ли это дерево?

Ответ: НЕТ, не всегда. Индекс может быть реализован различными структурами данных, и B-tree — это только один из вариантов (хотя и самый распространённый).

Основные типы структур данных для индексов

1. B-tree (B-дерево) — САМЫЙ РАСПРОСТРАНЁННЫЙ

Это иерархическая структура, которая используется в подавляющем большинстве СУБД (PostgreSQL, MySQL, SQLite).

ОСНОВА ИНДЕКСА:
        [30, 70]
        /   |   \
      /     |     \
   [10,20] [40,60] [80,90]
   /  |  \  /  |  \  /  |  \
  10 15 20 40 50 60 80 85 90

Пример в Java:

// Создаём B-tree индекс
CREATE INDEX idx_user_id ON users(id);

// СУБД организует данные в виде дерева для быстрого поиска
// Сложность: O(log n) для поиска любого элемента

Когда используется:

• Общие индексы на все типы данных
• Быстрая выборка диапазонов (BETWEEN, >, <)
• Сортировка (ORDER BY)

2. Hash index (Хеш-таблица)

Упорядочение данных по хеш-функции, а не по дереву.

Hash(key) -> Bucket (значение)

index_value(1):    -> |
index_value(5):    -> | -> 0x00001 -> [Record 1, Record 5, Record 12]
index_value(12):   -> |
index_value(22):   -> | -> 0x00010 -> [Record 22]

Пример в PostgreSQL (поддерживает Hash индексы):

// Создаём хеш-индекс вместо B-tree
CREATE INDEX idx_user_email ON users USING HASH (email);

// Хеш-индекс оптимален для равенства (=)
// Но НЕ работает для диапазонов
SELECT * FROM users WHERE email = 'john@example.com';  // ✓ Быстро с hash индексом
SELECT * FROM users WHERE email LIKE 'john%';          // ✗ Не может использовать hash индекс

Преимущества:

• Очень быстрый поиск по равенству (O(1) в среднем)
• Меньше памяти, чем B-tree

Недостатки:

• Не поддерживает диапазоны
• Не поддерживает сортировку
• Не устойчив к коллизиям при разрастании данных

3. Bitmap index (Битовый индекс)

Частая в аналитических системах и базах данных с низкой кардинальностью (мало уникальных значений).

// Пример: статус заказа (только 3 значения: pending, completed, cancelled)
CREATE BITMAP INDEX idx_order_status ON orders(status);

// Битовый индекс для статуса:
pending:    [1, 0, 1, 0, 0, 1, 1, 0, ...]
running:    [0, 0, 0, 1, 0, 0, 0, 1, ...]
completed:  [0, 1, 0, 0, 1, 0, 0, 0, ...]

// Если нужны заказы со статусом "pending":
SELECT * FROM orders WHERE status = 'pending';
// СУБД просто смотрит на битовый массив и находит все 1-цы

Когда используется:

• Низкая кардинальность (мало уникальных значений)
• Аналитические системы (OLAP)
• Быстрые И/ИЛИ операции между несколькими индексами

4. Full-text index (Полнотекстовый индекс)

Оптимизирован для поиска по текстовым данным.

// MySQL
CREATE FULLTEXT INDEX idx_post_content ON posts(content);

SELECT * FROM posts WHERE MATCH(content) AGAINST('Java programming' IN BOOLEAN MODE);

// PostgreSQL
CREATE INDEX idx_post_gin ON posts USING GIN (to_tsvector('english', content));

SELECT * FROM posts WHERE to_tsvector('english', content) @@ to_tsquery('english', 'Java & programming');

Структура: обычно инвертированный индекс (inverted index)

слово -> [документ1, документ2, документ3]

'Java' -> [doc1, doc5, doc10, ...]
'programming' -> [doc2, doc5, doc15, ...]
'database' -> [doc3, doc4, doc5, ...]

Когда используется:

• Поиск по текстам (search engines)
• Автодополнение в приложениях
• Фильтрация по ключевым словам

5. R-tree (Пространственное дерево)

Для географических и пространственных данных.

// PostgreSQL с PostGIS (для геоданных)
CREATE INDEX idx_geo_location ON locations USING GIST (coordinates);

// Запрос: найти все точки в прямоугольнике
SELECT * FROM locations
WHERE coordinates && ST_MakeBBox('((0,0),(100,100))');

// R-tree индекс очень быстро отсеивает миллионы ненужных записей

Когда используется:

• Геоданные, координаты
• Поиск в диапазоне координат
• GIS системы

6. BRIN (Block Range Index)

Последний тип индекса в PostgreSQL, занимает минимум памяти.

// Для больших таблиц с отсортированными данными
CREATE INDEX idx_timestamp ON events USING BRIN (timestamp);

// BRIN индексирует не каждую строку, а диапазоны блоков
Блок 0-999:    min=2024-01-01, max=2024-01-31
Блок 1000-1999: min=2024-02-01, max=2024-02-28
Блок 2000-2999: min=2024-03-01, max=2024-03-31

// Очень быстро исключить целые диапазоны
SELECT * FROM events WHERE timestamp BETWEEN '2024-02-01' AND '2024-02-28';

Когда используется:

• Огромные таблицы (миллиарды строк)
• Временные ряды (временные метки, логи)
• Минимальное использование памяти

Сравнительная таблица

Как выбрать тип индекса?

// 1. Индекс на числовой ID — B-tree (default)
CREATE INDEX idx_user_id ON users(id);  // B-tree

// 2. Индекс на статус (low cardinality) — Bitmap для OLAP или B-tree для OLTP
CREATE INDEX idx_status ON orders(status);  // B-tree (OLTP) или Bitmap (OLAP)

// 3. Индекс на текстовое поле (поиск) — Full-text
CREATE FULLTEXT INDEX idx_search ON articles(content);

// 4. Индекс на координаты — R-tree
CREATE INDEX idx_location ON places USING GIST (geo_point);

// 5. Индекс на timestamp в большой таблице — BRIN
CREATE INDEX idx_timestamp ON events USING BRIN (created_at);

Как проверить тип индекса?

-- PostgreSQL
SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'users';
-- Пример: CREATE INDEX idx_user_id ON users USING btree (id)
-- Видно USING btree — это B-tree индекс

-- MySQL
SHOW INDEX FROM users;
-- Колонка Seq_in_index показывает тип индекса

Итог

1. B-tree — самый распространённый тип (90% случаев)
2. Hash — для равенства на небольших данных
3. Bitmap — для аналитики с низкой кардинальностью
4. Full-text — для поиска по текстам
5. R-tree — для геоданных
6. BRIN — для огромных таблиц с временными рядами

Главное: не все индексы — это деревья. Тип индекса выбирается в зависимости от типа данных и типа запросов. В большинстве случаев СУБД создаёт B-tree индекс по умолчанию, но для специальных случаев используются другие структуры.