Как распределены данные в БД при использовании индекса в PostgreSQL

Как распределены данные в БД при использовании индекса в PostgreSQL

Что такое индекс

Индекс — это отдельная структура данных (обычно B-tree), которая содержит отсортированные значения колонки и указатели на строки в основной таблице.

Без индекса (❌ медленно)

Таблица users:
┌────┬───────────┬──────────┐
│ id │ email     │ username │
├────┼───────────┼──────────┤
│ 1  │ john@ex.  │ john     │
│ 2  │ alice@ex. │ alice    │
│ 3  │ bob@ex.   │ bob      │
│ 4  │ charlie@. │ charlie  │
│ 5  │ dave@ex.  │ dave     │
└────┴───────────┴──────────┘

Запрос: SELECT * FROM users WHERE email = 'bob@ex.'
PostgreSQL: Full table scan (5 операций для 5 строк)
1. Проверить id=1, email != 'bob@ex.'
2. Проверить id=2, email != 'bob@ex.'
3. Проверить id=3, email == 'bob@ex.' ✓ НАЙДЕНО!
4. Проверить id=4, email != 'bob@ex.'
5. Проверить id=5, email != 'bob@ex.'

С индексом (✓ быстро)

Таблица users (основные данные):
┌────┬───────────┬──────────┐
│ id │ email     │ username │
├────┼───────────┼──────────┤
│ 1  │ john@ex.  │ john     │
│ 2  │ alice@ex. │ alice    │
│ 3  │ bob@ex.   │ bob      │
│ 4  │ charlie@. │ charlie  │
│ 5  │ dave@ex.  │ dave     │
└────┴───────────┴──────────┘

Индекс (отдельная структура, отсортирована):
┌──────────────┬────────────────┐
│ email        │ pointer_to_row │
├──────────────┼────────────────┤
│ alice@ex.    │ → row 2        │
│ bob@ex.      │ → row 3        │
│ charlie@.    │ → row 4        │
│ dave@ex.     │ → row 5        │
│ john@ex.     │ → row 1        │
└──────────────┴────────────────┘

Запрос: SELECT * FROM users WHERE email = 'bob@ex.'
PostgreSQL: Index lookup (логарифмическое время)
1. Бинарный поиск в индексе → находит 'bob@ex.'
2. Получает pointer_to_row = row 3
3. Идет к таблице и читает row 3
→ НАЙДЕНО за 1-2 операции вместо 5!

Структура B-tree индекса в PostgreSQL

Бинарное дерево поиска:

               [b, dave]
               /         \
        [alice]         [john]
         /    \          /    \
       [ ]  [bob]   [charlie] [ ]

Поиск 'bob':
1. Начинаем с корня: b == b, dave < bob
   → Идем влево
2. Находим bob < bob (false), bob >= alice (true)
   → Листовой узел [bob]
3. Нашли!

Время поиска: O(log N)
Для 1 млн записей: ~20 сравнений вместо 1 млн

Как PostgreSQL хранит индекс на диске

1. Структура индекса

CREATE INDEX idx_users_email ON users(email);

-- PostgreSQL создает отдельный файл в базе:
-- $PGDATA/base/[database_oid]/[index_oid]

2. Файловая система PostgreSQL

$PGDATA/
├── base/
│   └── [database_oid]/
│       ├── [table_oid]        -- основная таблица users
│       ├── [index_oid]        -- индекс idx_users_email
│       ├── [index_oid].1      -- overflow страница
│       └── [index_oid].2      -- еще одна страница
├── global/
└── pg_wal/

3. Организация в памяти

ПостgreSQL работает с страницами (8KB по умолчанию):

Пэйдж (8KB):
┌─────────────────────────────────────────┐
│ Page Header (структура, метаданные)     │
├─────────────────────────────────────────┤
│ Item Pointers (указатели на записи)     │
├─────────────────────────────────────────┤
│ Free Space (свободное место)            │
├─────────────────────────────────────────┤
│ Row 1                                   │
│ Row 2                                   │
│ Row 3                                   │
└─────────────────────────────────────────┘

Как B-tree индекс хранит данные

Таблица:
users(id, email, username, created_at)

Индекс по email:

ROOT NODE (узел-корень):
┌──────────────────────────┐
│ item  │ pointer_to_child │
├──────┼──────────────────┤
│ 'm'  │ → LEFT CHILD     │
│ 's'  │ → RIGHT CHILD    │
└──────┴──────────────────┘

LEFT CHILD (emails от a-l):
┌─────────────────────────────────┐
│ email       │ pointer_to_row    │
├─────────────┼───────────────────┤
│ alice@ex.   │ → table row id=2  │
│ bob@ex.     │ → table row id=3  │
└─────────────┴───────────────────┘

RIGHT CHILD (emails от m-z):
┌─────────────────────────────────┐
│ email       │ pointer_to_row    │
├─────────────┼───────────────────┤
│ charlie@.   │ → table row id=4  │
│ dave@ex.    │ → table row id=5  │
│ john@ex.    │ → table row id=1  │
└─────────────┴───────────────────┘

Как работает поиск в индексе (Index Scan)

Запрос: SELECT * FROM users WHERE email = 'bob@ex.';

План выполнения:
EXPLAIN SELECT * FROM users WHERE email = 'bob@ex.';

                    QUERY PLAN
────────────────────────────────────────────────────
 Index Scan using idx_users_email on users
   Index Cond: (email = 'bob@ex.')
 (2 rows)

Процесс:

1. PostgreSQL смотрит на условие WHERE и видит email
2. Проверяет, есть ли индекс на email
3. Выполняет бинарный поиск в B-tree индексе
4. Находит листовой узел с 'bob@ex.'
5. Получает pointer_to_row
6. Идет в основную таблицу и читает полную строку

Кэширование индекса в памяти

BUFFER POOL (shared buffers в памяти, по умолчанию 25% RAM):

┌──────────────────────────────┐
│ Buffer (8KB page)            │ <- индекс узел
│ Buffer (8KB page)            │ <- индекс узел
│ Buffer (8KB page)            │ <- таблица страница
│ Buffer (8KB page)            │ <- свободно
├──────────────────────────────┤

Когда вы повторяете поиск, PostgreSQL часто находит данные в памяти
→ еще быстрее!

Типы индексов в PostgreSQL

-- B-tree (по умолчанию, для всех типов данных)
CREATE INDEX idx_users_email ON users(email);

-- Hash (для простого равенства)
CREATE INDEX idx_users_id ON users USING hash(id);

-- GiST (для геометрических данных, full-text search)
CREATE INDEX idx_locations_geo ON locations USING gist(location);

-- GIN (Generalized Inverted Index для массивов, JSON)
CREATE INDEX idx_tags ON articles USING gin(tags);

-- BRIN (для больших таблиц с отсортированными данными)
CREATE INDEX idx_events_created ON events USING brin(created_at);

Составной индекс (Composite Index)

-- Индекс по двум колонкам
CREATE INDEX idx_users_email_status ON users(email, status);

Этот индекс отсортирован сначала по email, потом по status:

┌──────────────┬────────┬────────────────┐
│ email        │ status │ pointer_to_row │
├──────────────┼────────┼────────────────┤
│ alice@ex.    │ active │ → row 2        │
│ bob@ex.      │ active │ → row 3        │
│ bob@ex.      │ inactive│ → row 8        │
│ charlie@.    │ active │ → row 4        │
└──────────────┴────────┴────────────────┘

Поиск: WHERE email = 'bob' AND status = 'active'
→ Очень быстро!

Поиск: WHERE status = 'active' (без email)
→ Индекс не поможет (статус второй столбец)

EXPLAIN для анализа индексов

-- Посмотреть план выполнения
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'bob@example.com';

Ответ:
Seq Scan on users  (cost=0.00..35.00 rows=1)
  Filter: (email = 'bob@example.com')
  (2 rows)

-- С индексом:
CREATE INDEX idx_email ON users(email);

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'bob@example.com';

Ответ:
Index Scan using idx_email on users (cost=0.29..8.30 rows=1)
  Index Cond: (email = 'bob@example.com')
  (2 rows)

-- Cost упал с 35.00 на 8.30! 4x быстрее

Когда индекс не помогает

-- 1. LIKE с wildcart слева
SELECT * FROM users WHERE email LIKE '%example.com';
→ Индекс на email не работает (нужен полный scan)

-- 2. Функции на индексируемой колонке
SELECT * FROM users WHERE LOWER(email) = 'bob@example.com';
→ Индекс не работает (функция изменила значение)

-- 3. OR с несвязанными колонками
SELECT * FROM users WHERE email = 'bob@ex.' OR age > 30;
→ Нужны индексы на email И age отдельно

-- 4. Очень селективный индекс
SELECT * FROM users WHERE status = 'active';  -- 99% данных
→ Full table scan быстрее чем индекс (если выборка > 5-10%)

Что происходит при вставке/удалении с индексами

Вставка: INSERT INTO users(email, name) VALUES ('new@ex.', 'New');

1. PostgreSQL создает новую строку в таблице
2. Для каждого индекса:
   a) Находит правильную позицию в B-tree индексе
   b) Вставляет новый элемент
   c) Балансирует дерево если нужно
3. Логирует изменение в WAL (Write-Ahead Log)

⚠️ Нужно пересортировать индекс!
→ Индексы замедляют INSERT/UPDATE/DELETE
→ Но ускоряют SELECT

Размер индекса

-- Посмотреть размер индекса
SELECT 
  schemaname,
  tablename,
  indexname,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_indexes
WHERE schemaname NOT IN ('pg_catalog', 'information_schema')
ORDER BY pg_relation_size(indexrelid) DESC;

-- Пример вывода:
schemaname │ tablename │ indexname          │ index_size
───────────┼───────────┼────────────────────┼───────────
public     │ users     │ idx_users_email    │ 45 MB
public     │ orders    │ idx_orders_user_id │ 120 MB

Индексы занимают место на диске!
Значительный индекс может быть несколько ГБ для больших таблиц

Резюме

1. Индекс — это отдельная отсортированная структура B-tree
2. Указывает на строки в основной таблице через pointers
3. Ускоряет поиск с O(N) до O(log N)
4. Хранится на диске отдельными файлами
5. Кэшируется в памяти в buffer pool
6. Замедляет вставки/обновления но ускоряет чтение
7. Занимает место на диске (10-50% размера таблицы)
8. Нужно правильно выбирать колонки для индексов