Все
Истории
Дизайн
Код
Геймдев
Бизнес
Маркетинг
Управление
Кино
Музыка
Проектная фотография
Развитие
Здоровье
Деньги
Образование
EdTech
Корп. обучение
Блог Skillbox
Глоссарий
Спецпроекты
Профориентация
«Добавим 2 млн статей и посмотрим, что будет»: как ускорить базу данных с помощью индексов
Разбираемся, как ускорить работу базы данных приложений и сайтов, что такое индексы и как они устроены. Пособие для начинающих backend-разработчиков.
Владислав Невзоров
эксперт
об авторе
PHP-разработчик digital-агентства “Атвинта”, в свободное время пишу на Go/C#/C++. Нравится проектировать и продумывать highload-системы.
Базы данных — это совсем не сложно, даже новички быстро вливаются в тему и начинают работать практически без проблем. А что сложного? Есть таблицы, в них записываем строки — всё просто. Да, и всё работает, никто не жалуется. Пока не наступит момент… когда данных будет много.
Тут нам и приходят на помощь индексы. Во всех базах данных они работают примерно по одному и тому же принципу. В этой статье я буду использовать MariaDB.
Запрос на выборку без индексов
Рассмотрим на простом примере. Есть таблица articles со следующей структурой:
Добавим в таблицу несколько записей:
И сделаем следующий запрос:
Ничего удивительного: простой запрос и выполняется быстро. Но что будет, если данных “чуть-чуть” больше? Давайте добавим, например, 2 млн статей.
И повторим запрос на выборку:
Как видим, время выполнения запроса увеличилось. Хоть и две секунды, но это долго. И нагрузка на диск высокая.
Две секунды на выполнение запроса — не предел; когда данных ещё больше, всё будет ещё хуже. Оптимизировать этот запрос можно с помощью индексов.
Запрос на выборку с индексом
Создаем индекс по колонке views из таблицы articles.
И повторяем запрос:
Вот! Так намного лучше. Выборка проходит так же быстро, как и с тремя записями. В чём же подвох? Как это работает и почему? Что может пойти не так?
Как устроен запрос без индекса и с ним
Запрос к выборке БД без индекса
Что происходит, когда мы запрашиваем данные? А что вы делаете, когда ищете нужную вам строку в таблице? Да, база данных сканирует всю таблицу и выбирает те записи, которые попадают под условия.
Это происходит быстро, когда у нас три записи, и долго, когда их очень много. Ведь наша таблица хранится на физическом носителе и, чтобы просмотреть её всю, нужно считать немало данных.
Запрос к выборке БД с индексом
Я часто встречаю, что индекс путают с id или уникальным идентификатором, считают, что это одно и то же. Это не так! Индекс в базах данных — это другое.
Индекс, который мы создали, представляет из себя такую структуру данных, как B-дерево. Но, например, в InnoDB используется B+-дерево. Всё зависит от подсистемы хранения, а в целом принцип их работы похож. Это дерево строится по колонке views из таблицы articles.
Чтобы понять, как происходит выборка с индексом, нужно знать, как работает B-дерево.
Перед нами B-дерево индекса. В каждом узле хранятся элементы со значениями; в нашем случае это значения из поля views. Также элементы хранят ссылку на строку в таблице.
Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:
- Если значение совпало — берём ссылку на данные и читаем их из таблицы.
- Если наше значение больше, чем значение в элементе, — идём дальше.
- Если искомое значение меньше, чем в элементе, — нам нужно перейти в поддерево, которое хранится левее от ячейки. Далее мы попадаем на следующий уровень и итерация повторяется.
Важно!
Дерево из примера выше не является копией того, которое построила БД в моём случае. Это я изобразил, чтобы показать, как проходит поиск по дереву.
Рассмотрим алгоритм на примере поиска значения 2001.
- Как и говорилось ранее, мы начинаем с корневого узла — первой ячейки со значением 1000.
- Так как 2001 больше 1000, то мы идём дальше.
- Доходим до ячейки 3000. Но 2001 меньше, чем 3000, поэтому переходим на поддерево.
- Первая ячейка идёт со значением 2200, наше значение меньше, значит снова переходим на левое поддерево.
- И сразу же находим ячейку со значением 2001.
То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.
Ещё один способ запроса с индексом
В данной структуре можно легко делать выборку по диапазонам, например views >= 1000. В случае таких запросов индекс также поможет.
Хоть поиск и значительно ускорился, есть и свои нюансы. Изменения в В-дереве — не самая быстрая операция.
Необходимо, чтобы все конечные узлы (листья) дерева находились на одном уровне, а количество элементов в узлах было одинаковым — тогда мы получим наивысшую скорость выборки.
Чтобы придерживаться этих условий, нужно постоянно проводить перебалансировку дерева. Это и замедляет работу.
Если вы используете несколько десятков индексов в одной таблице, то при вставке или удалении из неё нужно проводить такие нехитрые манипуляции с деревьями. Из этого следует вывод, что не стоит увлекаться и создавать индексы по каждому полю.
Мы рассмотрели создание индекса по одной колонке (views), но в базах данных одной колонкой не ограничишься. Можно создавать составные индексы. Например, если есть поле views и дата created_at, и вы хотите делать подобные запросы: views = 1000 and created_at = “10.10.2019”, то имеет смысл создать индекс по двум колонкам.
Заключение
Я рассказал об устройстве индексов в базах данных достаточно, чтобы новичок смог понять, насколько важны индексы в проектировании БД. Не забывайте решать, где их стоит применять, и учиться их использовать.
