Что такое индекс и сколько он стоит в обмен на более быстрое чтение?

Question

Accepted Answer

Отдельная упорядоченная структура сопоставляет значения столбцов с местоположениями строк, превращая сканирование таблицы `O(n)` в поиск в дереве `O(log n)`. Цена: каждый индекс должен синхронизироваться при каждой записи, и для этого требуется дополнительное дисковое пространство — компромисс между чтением и записью, а не бесплатное обновление.

## Пример

```sql
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

--                                     QUERY PLAN
-- Index Scan using idx_orders_customer_id on orders
--   (cost=0.29..8.31 rows=1 width=48) (actual time=0.02..0.03 rows=3 loops=1)
--   Index Cond: (customer_id = 42)
```

## Итог

Отдельная упорядоченная структура сопоставляет значения столбцов с местоположениями строк, превращая сканирование таблицы `O(n)` в поиск в дереве `O(log n)`.