Зачем нужны индексы в базах данных: тест на SQLite с таблицей из 10 000 записей

Как база данных ищет данные без индекса

Когда таблица создаётся без явных указателей, записи в ней хранятся в порядке добавления. В реляционной теории это называется неупорядоченной кучей страниц на накопителе. Если выполнить запрос с фильтрацией по столбцу, где индекса нет, системе приходится читать с диска абсолютно все блоки таблицы подряд.

Такой процесс в терминах систем управления базами данных называется полным сканированием таблицы или Full Table Scan. В плане выполнения SQLite этот шаг обозначается как SCAN TABLE. СУБД загружает страницу памяти с диска, проверяет каждую строчку на соответствие условию в блоке WHERE и переходит к следующей странице. Сложность подобного перебора линейная — O(N). Если строк десять тысяч, движок проверит десять тысяч значений, а если строк сто миллионов, сервер сделает сто миллионов чтений.

Внутреннее устройство индекса и B-Tree

Индекс представляет собой отдельную вспомогательную структуру данных, чаще всего сбалансированное дерево поиска B-Tree или его разновидность B+Tree. В этой структуре значения индексируемой колонки заранее отсортированы по возрастанию или убыванию, а к каждому значению привязан физический адрес строки — ROWID в случае SQLite или первичный ключ.

Поиск по такому дереву кардинально отличается от перебора. Движок базы данных начинает с корневого узла, сравнивает искомое значение с разделителями и спускается по ветвям к листьям. На каждом шаге алгоритм отсекает подавляющую часть вариантов. В результате сложность поиска падает с линейной O(N) до логарифмической O(log N). Для нахождения одной строки среди миллиона записей движку требуется прочитать всего три или четыре страницы дерева вместо десятков тысяч страниц таблицы.

Практический тест на SQLite с таблицей на 10 000 записей

Проверить разницу в производительности можно на практике с помощью встроенного в Python модуля sqlite3 или консольного клиента SQLite. Для наглядности эксперимента создадим синтетическую базу данных пользователей с десятью тысячами строк.

Шаг 1. Создание таблицы и генерация данных

Создадим таблицу users со случайными адресами электронной почты. Чтобы генерация десяти тысяч строк не упёрлась в операции дискового ввода-вывода, выполним вставку данных единой транзакцией.

• Создание схемы: CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, age INTEGER, created_at TEXT);
• Наполнение: запускаем скрипт, который генерирует 10 000 уникальных записей вида user1234@example.com с произвольным возрастом от 18 до 70 лет;
• Фиксация транзакции: выполняем команду COMMIT, сохраняя массив строк на диск в файл базы данных.

Шаг 2. Замер выборки без индекса

Выполним поиск конкретного пользователя по почтовому адресу: SELECT * FROM users WHERE email = 'user9541@example.com'. Чтобы нивелировать погрешности таймера операционной системы, запустим этот запрос в цикле 1000 раз и посчитаем суммарное время.

Команда EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = 'user9541@example.com' возвращает результат SCAN users. Это подтверждает, что движок SQLite добросовестно сканирует всю таблицу от первой до последней записи на каждый запрос. Суммарное время тысячи повторений на обычном офисном компьютере составляет около 1.8–2.2 секунды.

Шаг 3. Добавление индекса и повторный замер

Теперь построим индекс по целевой колонке: CREATE INDEX idx_users_email ON users(email). Движок создаёт структуру B-Tree, считывая текущие строки таблицы и раскладывая их по ветвям дерева.

Повторим диагностику плана выполнения через EXPLAIN QUERY PLAN. Теперь консоль выведет строку SEARCH users USING INDEX idx_users_email (email=?). Слово SEARCH указывает на точечную выборку по дереву вместо сквозного просмотра. Запуск того же цикла из 1000 запросов занимает около 0.02 секунды. Производительность поиска выросла примерно в сто раз даже на столь скромном объёме в десять тысяч строк.

Обратная сторона индексов

Ускорение выборки влечёт за собой плату системными ресурсами. Индекс занимает дополнительное физическое место на диске. В нагруженных базах данных суммарный объём файлов индексов нередко превышает размер самих сырых данных таблицы.

Вторая проблема касается операций модификации данных: INSERT, UPDATE и DELETE. При добавлении новой строки в таблицу СУБД обязана не только записать саму строку, но и найти правильное место в каждом существующем B-Tree, вставить ссылку и при необходимости выполнить балансировку узлов дерева. Чем больше индексов навешано на таблицу, тем медленнее в неё вставляются новые записи.

Когда создавать индексы

• Колонки регулярно участвуют в секциях WHERE с операторами точного сравнения или диапазонов;
• Поля используются для объединения таблиц через конструкции JOIN;
• По столбцам регулярно выполняется сортировка через ORDER BY или группировка через GROUP BY;
• Столбец имеет высокую селективность, то есть содержит множество уникальных значений вроде телефонных номеров, адресов почты или артикулов товаров.