Подробное описание индекса базы данных — как на самом деле работает индекс? медленный индекс?

Эта серия вдохновлена сутью книги — Объяснение производительности SQL Маркуса Винанда, вы можете узнать больше, перейдя по ссылкам с сайта авторов.

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

Недостаточно знать, что индекс делает поиск быстрым. Чтобы оптимизировать более сложный SQL, важно знать, как на самом деле работает индекс.

Индекс базы данных

Индекс — это специальная структура в базе данных, построенная с использованием операторов CREATE INDEX. Он создает новую структуру данных, которая ссылается на определенную таблицу.

CREATE INDEX index_users_on_age ON users (age);

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

Почему индекс ускоряет поиск?

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

Вызов

Сложность индекса базы данных заключается в том, что он должен быстро обрабатывать операторы insert , delete и update, сохраняя порядок индекса и не перемещая большие объемы данных.

Как мы знаем, вставка данных в массив выполняется МЕДЛЕННО, потому что невозможно хранить данные последовательно, не перемещая следующие элементы, чтобы освободить место для нового. А перемещение большого количества элементов занимает очень много времени.

Как база данных преодолевает?

Для решения этой задачи база данных объединяет две структуры данных — двухсвязный список и дерево поиска.

Почему дерево является хорошей структурой данных для базы данных?

Поиск определенного значения выполняется быстро (логарифмическое время)
Вставка/удаление значения, которое вы уже нашли, выполняется быстро (постоянное время на перебалансировку)
Быстрое перемещение по диапазону значений

Почему связанный список?

позволяет базе данных читать индекс вперед и назад
сделать INSERT очень быстрым — нужно только изменить несколько указателей

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

Отмечено, что индексы могут быть реализованы с использованием различных структур данных. Не существует стандарта, определяющего, как создать индекс. — смотрите больше в Википедии

Архитектура индекса

Ниже приведена иллюстрация индексации столбца age в таблице users, созданной с помощью следующих команд SQL:

CREATE INDEX index_users_on_age ON users (age);

Допустим, мы хотим найти всех пользователей, которым исполнилось 16 лет:

SELECT * FROM users 
WHERE users.age = 16;

Желтый путь, выделенный на иллюстрации, — это путь поиска с использованием index search. Сначала мы можем сосредоточиться на ключевых фрагментах и структурах графика:

Balanced Search Tree — строится из users.age столбца в отсортированном порядке на каждом уровне узлов, который, как упоминалось выше, способен осуществлять поиск за логарифмическое время.
Double Linked List— Как мы знаем, в WHERESQL может быть несколько результатов. Помимо поиска в сбалансированном дереве на разных уровнях, база данных также должна будет перемещаться, так называемое, Index Leaf Nodes, чтобы найти каждое значение совпадения. Он построен как Double Linked List, что позволяет очень легко путешествовать вперед и назад.

RowID — после поиска внутри индекса базе данных по-прежнему требуется доступ к фактической таблице, чтобы получить значения строк, перечисленные в запросе SELECT. База данных заставляет его работать, сохраняя RowID или RID в индексе, который относится к фактической позиции записи в таблице.

Процесс поиска

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

① Поиск в дереве индексов — обход B-дерева

Следуйте по желтому пути на рисунке, количество шагов для обхода дерева в этом индексе равно 3, что связано с глубиной B-дерева. Это дерево содержит 4 записи на узел, что означает, что оно может содержать до 64 (4³) записей.

В реальном мире базы данных могут максимизировать количество записей на узел, часто сотни. Обычно индекс имеет глубину дерева 4 или 5, редко 6. Это означает, что вы можете хранить 100⁵=10000000000 записей и выполнять поиск всего за 5 шагов. Разве это не безумие?

Обход дерева настолько эффективен и работает почти мгновенно даже на огромном столе, как уже упоминалось.

② Поиск в связанном списке — следование по цепочке конечных узлов

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

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

Это один из факторов, замедляющих поиск даже при использовании индекса.

③ Доступ (нажатие) к фактической таблице

После поиска в дереве база данных получит набор RowID, который указывает на позицию строки фактической таблицы. Базе данных необходимо получить доступ к фактической таблице, чтобы получить фактические данные.

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

Если вы запрашиваете 98% данных в пользовательской таблице, весьма вероятно, что полное сканирование таблицы будет быстрее, чем использование индекса, поскольку доступ к таблице занимает больше времени. Это еще одна операция, которая может замедлить поиск в индексе.

Заворачивать

В реальном мире существует множество различных типов индексов. Каждая база данных обрабатывает индексы по-разному. Однако концепция у всех одинаковая — попытка создать творческую структуру, которая соответствует потребностям быстрого поиска и чтения/записи.

Фактически, мы можем исследовать, как база данных использует индекс. Вы можете узнать больше, выполнив поиск по ключевым словам — планы выполнения для разных баз данных. Например, Postgres использует оператор EXPLAIN для получения фактических планов выполнения и предполагаемых затрат.

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