Принцип работы индексов

Введение: Как искать информацию без индекса

Представьте, что вы пришли в библиотеку, где книги лежат на стеллажах в случайном порядке. Вам нужно найти книгу “Война и мир”. Как вы будете это делать?

Единственный способ – пройти вдоль всех стеллажей, посмотреть каждую книгу, прочитать ее название и сравнить с тем, что вы ищете. Если в библиотеке 10 книг, это займет пару минут. А если 100 000 книг? Вы будете искать несколько часов. А если вам нужно найти все книги определенного автора? Придется снова перебирать все книги.

База данных без индексов работает точно так же. Когда вы просите найти запись с определенным значением, база данных вынуждена просматривать каждую строку таблицы, пока не найдет нужную. Этот процесс называется полным сканированием таблицы (full table scan).

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

Простыми словами: Индекс – это как алфавитный указатель в конце книги или как оглавление. Вы не листаете всю книгу в поисках нужного слова – вы открываете указатель, находите страницу и сразу переходите к ней.

Как работает индекс: Двоичный поиск

Чтобы понять принцип работы индексов, нужно знать, как работает двоичный поиск (binary search). Это алгоритм, который многократно делит отсортированный массив пополам, чтобы найти нужный элемент.

Пример двоичного поиска

У вас есть отсортированный список чисел: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. Вам нужно найти число 13.

Как работает двоичный поиск:

1. Смотрите на средний элемент. Длина списка – 10. Средний элемент – между 5-м и 6-м. Возьмем 6-й элемент: 11.
2. Сравниваете: 13 > 11. Значит, нужное число находится в правой половине. Левую половину можно больше не смотреть.
3. Остался список: [13, 15, 17, 19]. Средний элемент – 15 (или 17).
4. 13 < 15. Значит, число в левой половине.
5. Остался список: [13]. Это искомое число.

Вы нашли число за 4 шага. А при линейном поиске (переборе всех элементов) вам могло потребоваться 10 шагов. Для 10 элементов разница незаметна. А для 10 миллионов элементов разница колоссальная.

Как это связано с индексами?

Индекс в базе данных хранит значения выбранного столбца в отсортированном порядке. Когда вы делаете запрос WHERE age = 25, база данных использует индекс (если он создан по полю age), чтобы найти нужные строки с помощью двоичного поиска. Ей не нужно просматривать все строки таблицы.

Структура индекса: Дерево (B-Tree)

На практике базы данных используют для индексов структуру, которая называется B-Tree (сбалансированное дерево). Не пугайтесь названия. Принцип тот же, что и у двоичного поиска, но организованный в виде дерева.

Визуальное представление B-Tree

Представьте дерево, где:

• Корень (root) – верхний уровень. Это начальная точка поиска.
• Ветви (branches) – промежуточные уровни. Они направляют поиск в нужную сторону.
• Листья (leaves) – нижний уровень. Они содержат сами значения и указатели (ссылки) на строки в таблице.

                      [50]
                     /    \
                  [30]    [70]
                 /   \   /   \
              [20] [40] [60] [80]
               |    |    |    |
            (строка) (строка) (строка) (строка)

Как выполняется поиск по B-Tree:

Допустим, вы ищете запись со значением 40 по индексированному столбцу.

1. Начинаете с корня: 40 < 50 → идете в левую ветку.
2. Попадаете на узел [30]. 40 > 30 → идете в правую ветку.
3. Попадаете на лист [40]. Нашли нужное значение.
4. Из листа берете указатель (ссылку) и переходите к полной строке в таблице.

Вы спустились по дереву за 3 шага, независимо от того, сколько всего строк в таблице — тысяча или десять миллионов.

Почему B-Tree такой эффективный?

Потому что высота дерева растет очень медленно. Даже для таблицы с миллиардом строк глубина B-Tree будет всего около 4-5 уровней. Это означает, что для поиска любого значения базе данных нужно сделать всего 4-5 операций чтения с диска.

Индекс как указатель: Таблица и индекс отдельно

Важно понимать: индекс существует отдельно от таблицы. Это дополнительная структура данных, которая занимает дополнительное место на диске.

Представьте, что у вас есть книга (таблица) и отдельно от нее – алфавитный указатель (индекс). Книга и указатель – это разные объекты. Указатель помогает быстро находить страницы в книге, но он не заменяет книгу.

То же самое в базе данных:

Как это выглядит на практике:

Таблица “Пользователи” (данные могут быть не отсортированы):

Индекс по полю “city” (хранится отдельно, отсортирован):

Когда вы делаете запрос SELECT * FROM Пользователи WHERE city = "Москва", база данных:

1. Идет в индекс по полю city.
2. Быстро находит в отсортированном индексе все записи со значением “Москва”.
3. Получает указатели на строки (id 101 и 89).
4. По указателям переходит к полным строкам в таблице.

Почему индексы ускоряют поиск: Сравнение подходов

Давайте сравним поиск с индексом и без индекса на реальных цифрах.

Предположим:

• В таблице 1 000 000 строк.
• База данных может читать 10 000 строк в секунду с диска.

Поиск без индекса (полное сканирование таблицы)

База данных читает каждую строку подряд, пока не найдет нужные.

• В худшем случае: нужно прочитать все 1 000 000 строк.
• В среднем: нужно прочитать 500 000 строк.
• Время: 1 000 000 / 10 000 = 100 секунд (больше полутора минут).

Поиск с индексом (B-Tree)

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

• Глубина B-Tree для 1 000 000 строк: около 3-4 уровней.
• Количество операций чтения: 3-4 для поиска в индексе + количество найденных строк.
• Если мы ищем одного пользователя: 3-4 + 1 = 5 операций чтения.
• Время: 5 / 10 000 = 0,0005 секунды (практически мгновенно).

Разница колоссальная: 100 секунд против 0,0005 секунды. Вот почему индексы так важны.

Цена индексов: Плата за скорость

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

Что вы платите за индекс

1. Дополнительное место на диске

Индекс – это отдельная структура данных. Он дублирует значения столбца (или столбцов), по которым создан. Если у вас большая таблица и много индексов, они могут занимать столько же места, сколько и сама таблица (а иногда и больше).

2. Замедление операций изменения

Когда вы добавляете, обновляете или удаляете строки в таблице, база данных должна обновить все индексы, которые есть на этой таблице.

• INSERT: База данных добавляет строку в таблицу, а затем добавляет новые записи в каждый индекс (в правильное отсортированное место).
• UPDATE: Если обновляется столбец, по которому есть индекс, база данных должна удалить старую запись из индекса и вставить новую.
• DELETE: База данных удаляет строку из таблицы, а затем удаляет соответствующие записи из всех индексов.

Пример:

У вас есть таблица с 5 индексами. Вы вставляете одну строку.

• Без индексов: 1 операция записи (в таблицу).
• С 5 индексами: 1 операция в таблицу + 5 операций в индексы = 6 операций записи.

Вставка строки будет медленнее в 6 раз.

Когда индексы полезны, а когда нет

Не на все столбцы нужно создавать индексы. Иногда индекс не помогает или даже вредит.

Когда индекс полезен (создавайте индекс)

Когда индекс бесполезен (не создавайте)

Когда индекс может навредить

Что такое составной индекс (кратко)

Иногда индекс создают не по одному столбцу, а по нескольким сразу. Например, индекс по полям (last_name, first_name).

Зачем это нужно?

Представьте, что вы часто ищете людей по фамилии и имени: WHERE last_name = “Петров” AND first_name = “Иван”.

Если у вас два отдельных индекса (один по фамилии, один по имени), база данных найдет всех Петровых (много) и всех Иванов (много), а потом пересечет результаты. Это может быть неэффективно.

Если у вас составной индекс (last_name, first_name), база данных может найти точную комбинацию за один проход по дереву.

Важное правило для составных индексов: Порядок столбцов имеет значение. Индекс (last_name, first_name) помогает при поиске по фамилии, но НЕ помогает при поиске только по имени. Это как телефонная книга: она помогает найти человека по фамилии и имени, но не помогает найти всех Иванов, если вы не знаете фамилию.

Индекс и первичный ключ: Особая связь

Когда вы создаете первичный ключ (PRIMARY KEY) в таблице, база данных автоматически создает индекс по этому столбцу.

Почему? Потому что первичный ключ нужен для быстрого поиска строки. Если бы индекса не было, каждая операция поиска по первичному ключу требовала бы полного сканирования таблицы. Это было бы катастрофой.

Например:

CREATE TABLE Users (
    id INT PRIMARY KEY,
    name VARCHAR(100)
);

База данных автоматически создаст индекс по столбцу id. Когда вы пишете SELECT * FROM Users WHERE id = 5, поиск происходит по этому индексу и занимает доли секунды.

Визуальное сравнение: С индексом и без

Запрос: найти пользователя с email = “ivan@mail.ru”

Без индекса по полю email:

С индексом по полю email:

Разница в 100 000 раз. Для пользователя запрос без индекса – это ожидание. Запрос с индексом – это мгновенный ответ.

Таблица сравнения: Чтение против записи

Типичные ошибки в работе с индексами

Ошибка 1: Создавать индексы на все столбцы подряд

Заблуждение: “Если индекс ускоряет поиск, пусть индексы будут на всех столбцах!”. В результате каждая вставка данных становится очень медленной, а индексы занимают огромное место.

Как исправить: Индексируйте только те столбцы, по которым вы реально часто ищете, сортируете или объединяете таблицы.

Ошибка 2: Не создавать индексы совсем

Противоположная крайность. В результате даже простые запросы выполняются минутами.

Как исправить: Создавайте индексы на первичные ключи (это автоматически), на внешние ключи, на столбцы в условиях WHERE частых запросов.

Ошибка 3: Создавать индекс на столбец с низкой избирательностью

Например, индекс на поле пол (всего два значения). Такой индекс почти не помогает, потому что после поиска в индексе все равно придется прочитать половину строк.

Как исправить: Индексируйте столбцы с высоким разнообразием значений (уникальные идентификаторы, email, номера).

Ошибка 4: Использовать функцию в WHERE при наличии индекса

SELECT * FROM Users WHERE UPPER(email) = 'IVAN@MAIL.RU'

Даже если есть индекс по email, он не будет использован, потому что значения в индексе хранятся в исходном виде, а вы ищете по UPPER(email).

Как исправить: Храните данные в том виде, в котором ищете. Или создайте индекс по выражению (но это сложнее).

Ошибка 5: Игнорировать составные индексы

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

Как исправить: Для часто встречающихся комбинаций создавайте составные индексы в правильном порядке.

Резюме для системного аналитика

1. Индекс – это структура данных для быстрого поиска. Работает как алфавитный указатель или как оглавление. Основан на двоичном поиске и B-Tree.

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

3. Индекс полезен для: поиска по точному значению, поиска по диапазону, сортировки, объединения таблиц (JOIN), полей с высоким разнообразием значений.

4. Индекс бесполезен или вреден для: очень маленьких таблиц, полей с низкой избирательностью (например, “пол”), часто обновляемых полей, таблиц с очень частыми вставками.

5. Первичный ключ (PRIMARY KEY) всегда индексируется автоматически. Это сделано для того, чтобы поиск по ключу был быстрым.

6. Составной индекс – это индекс по нескольким столбцам. Помогает при поиске по комбинации полей. Порядок столбцов в индексе имеет значение.