Принципы работы индексов: структура данных и алгоритмы поиска

Сегодня мы нырнем глубже в архитектуру индексов и рассмотрим, как они на самом деле работают под капотом. Ведь знание устройства индекса помогает не только понимать, почему запросы работают быстрее, но и как выбирать оптимальные индексы для разных задач.

Когда мы говорим о структуре индекса, речь идет о том, как данные организованы внутри индекса для обеспечения быстрого поиска. Представьте себе шкаф с документами. Если документы просто свалены в одну стопку, найти нужный будет сложно. Но если шкаф организован в алфавитном порядке, поиск становится значительно проще. Индексы работают именно так: они упорядочивают данные таким образом, чтобы поиск нужной информации происходил максимально быстро.

Структура B-TREE индекса

B-TREE (balanced tree — сбалансированное дерево) — это наиболее часто используемый тип индекса в PostgreSQL. По сути, это древовидная структура, где данные организованы в узлы, а поиск осуществляется через навигацию от корня дерева к листам.

Как это выглядит:

         Корень
          /       |       \
      Узел 1    Узел 2    Узел 3
     /   \       |       /   \
Лист1 Лист2   Лист3  Лист4 Лист5

Каждый узел содержит ключевые значения, которые позволяют направлять поиск. Например, если корневой узел содержит значения [10, 20, 30], то:

• Все данные меньше 10 находятся в Листе 1.
• Все данные между 10 и 20 — в Листе 2, и так далее.

Преимущества B-TREE индекса:

• Быстрый поиск данных: сложность поиска составляет O(log n), что значительно быстрее, чем линейный поиск.
• Подходит для поиска по диапазонам (например, найти все значения между 10 и 50).

Пример: допустим, у нас есть таблица students с колонкой age. Когда мы создаем B-TREE индекс на этой колонке:

CREATE INDEX age_idx ON students (age);

PostgreSQL создает сбалансированное дерево для значений возраста, что позволяет быстро находить студентов определенного возраста или диапазона возрастов.

Алгоритм поиска в B-TREE

Когда вы выполняете запрос, PostgreSQL использует индекс для поиска данных следующим образом:

1. Определяет ключ поиска (например, возраст 25).
2. Начинает с корневого узла.
3. Сравнивает ключ с диапазонами значений узла и переходит в соответствующий дочерний узел.
4. Повторяет шаг 3, пока не дойдет до листа.
5. Возвращает данные из листа, соответствующие ключу.

Пример запроса:

SELECT * FROM students WHERE age = 25;

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

Алгоритмы поиска и производительность

Индексы ускоряют поиск за счет уменьшения количества строк, которые нужно просканировать. Без индекса PostgreSQL сканирует всю таблицу (это называется последовательный скан, или Seq Scan). С индексом же выполняется индексный скан (Index Scan), что намного быстрее.

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

• Последовательный скан (Seq Scan):

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

• Индексный скан (Index Scan):

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

Пример: без индекса поиск возрастов

SELECT * FROM students WHERE age = 25;

результат может потребовать чтения 1 миллиона строк. С индексом B-TREE система, например, читает только 100 строк.

Влияние структуры индекса на производительность

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

Очень важно понимать структуру индекса. Знание, как именно работают индексы, помогает понять, почему некоторые запросы медленные и как их ускорить.

Кроме того важно понимать, какие индексы нужно использовать. Для поиска по диапазонам подходит B-TREE. Для массивов или JSONB — GIN. Неправильный выбор индекса может замедлить работу базы.

Реальные примеры

Давайте посмотрим, как индексы помогают нам в работе.

Индекс для сортировки

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

С индексом B-TREE PostgreSQL может вернуть отсортированные данные напрямую из индекса, без дополнительной сортировки.

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

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

Индекс B-TREE позволяет быстро находить строки, попадающие в заданный диапазон.

Частые вопросы и подводные камни

Почему не всегда стоит использовать индексы? Индексы занимают место на диске и замедляют операции вставки, обновления и удаления, так как нужно обновлять структуру индекса. Поэтому важно создавать индексы только для часто используемых колонок.

Когда индексы не помогают? Для запросов, охватывающих большую часть таблицы (например, WHERE true), PostgreSQL предпочтет Seq Scan, так как чтение индексных узлов не дает выигрыша.

2

Задача

SQL SELF, 37 уровень, 4 лекция

Недоступна

Создание простого индекса

Создание простого индекса

Открыть

1

Опрос

Введение в индексы, 37 уровень, 4 лекция

Недоступен

Введение в индексы

Введение в индексы

Открыть