Детали индекса MySQL

MySQL

предисловие

Поскольку наиболее важной структурой данных в индексе MySQL является дерево B+, давайте сначала поговорим о принципе дерева B+.

Принцип дерева B+

1. Структура данных

B-дерево относится к дереву баланса, которое является сбалансированным деревом. Сбалансированное дерево — это дерево поиска, в котором все листовые узлы находятся на одном уровне.

Дерево B+ реализовано на основе указателей последовательного доступа дерева B и конечных узлов, имеет баланс дерева B и повышает производительность интервальных запросов за счет последовательных указателей доступа.

В дереве B+ ключи в узле располагаются не по убыванию слева направо.Если левый и правый соседние ключи указателя равны keyi и keyi+1 соответственно и не равны нулю, то все ключи, на которые указатель больше или равен keyi и меньше или равен keyi+1.


2. Операция

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

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

3. Сравнение с красно-черными деревьями

Сбалансированные деревья, такие как красно-черные деревья, также могут использоваться для реализации индексов, но файловые системы и системы баз данных обычно используют дерево B+ в качестве структуры индекса по следующим двум причинам:

(1) Меньше поисков

Временная сложность операции поиска сбалансированного дерева равна высоте дерева h, а высота дерева примерно равна O(h)=O(logdN), где d — исходящая степень каждого узла.
Степень исхода красно-черного дерева равна 2, а степень исхода дерева B+ обычно очень велика, поэтому высота дерева h красно-черного дерева, очевидно, намного больше, чем у дерева B+, и количество поисков больше.

(2) Использование функции упреждающего чтения с диска

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

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

индексы MySQL

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

1. Индекс B+дерева

является типом индекса по умолчанию для большинства механизмов хранения MySQL.

Поскольку полное сканирование таблицы больше не требуется, требуется только поиск по дереву, поэтому поиск выполняется намного быстрее.

Помимо поиска, его также можно использовать для сортировки и группировки.

Несколько столбцов могут быть указаны как столбцы индекса, и несколько столбцов индекса вместе образуют ключ.

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

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


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


2. Хэш-индекс

Хэш-индекс можно искать за время O(1), но теряется порядок:
  • Нельзя использовать для сортировки и группировки;
  • Поддерживает только точный поиск, не может использоваться для частичного поиска и поиска по диапазону.
Механизм хранения InnoDB имеет специальную функцию, называемую «адаптивный хеш-индекс».Когда значение индекса используется очень часто, хэш-индекс будет создан поверх индекса B+Tree, так что будет создан индекс B+Tree. Индексы обладают некоторыми преимуществами хеш-индексов, такими как быстрый поиск хэшей.

3. Полнотекстовое индексирование

Механизм хранения MyISAM поддерживает полнотекстовое индексирование, которое используется для поиска ключевых слов в тексте, а не для прямого сравнения на равенство.
Условия поиска используют MATCH AGAINST вместо простого WHERE.
Полнотекстовое индексирование с использованием инвертированного индекса для достижения записи ключевых слов, с которыми оно сопоставлено в документе.
Механизм хранения InnoDB также поддерживает полнотекстовое индексирование в MySQL 5.6.4.

4. Индекс пространственных данных

Механизм хранения MyISAM поддерживает индексацию пространственных данных (R-Tree), которую можно использовать для хранения географических данных. Пространственные данные индексируют данные из всех измерений и могут эффективно использовать любое измерение для комбинированных запросов.
Данные должны поддерживаться с использованием функций, связанных с ГИС.

Оптимизация индекса

1. Отдельные столбцы

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

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

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;

2. Многоколоночный индекс

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

SELECT film_id, actor_ id FROM sakila.film_actor WHERE actor_id = 1 AND film_id = 1;

3. Порядок столбцов индекса

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

Селективность индекса относится к отношению уникальных значений индекса к общему количеству записей. Максимальное значение равно 1, после чего каждая запись имеет соответствующий ей уникальный индекс. Чем выше избирательность, тем выше эффективность запроса.

Например, в приведенных ниже результатах столбец customer_id является более избирательным, чем staff_id, поэтому лучше поместить столбец customer_id перед многостолбцовым индексом.

SELECT COUNT(DISTINCT staff_id)/COUNT(*) AS staff_id_selectivity,
COUNT(DISTINCT customer_id)/COUNT(*) AS customer_id_selectivity,
COUNT(*)
FROM payment;
   staff_id_selectivity: 0.0001
customer_id_selectivity: 0.0373
               COUNT(*): 16049

4. Индекс префикса

Для столбцов BLOB, TEXT и VARCHAR необходимо использовать индекс префикса, чтобы индексировать только начальную часть символа.

Выбор длины префикса должен определяться в соответствии с избирательностью индекса.

5. Индекс покрытия

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

Имеет следующие преимущества:

  • Индекс обычно намного меньше размера строки данных, и только чтение индекса может значительно сократить объем доступа к данным.
  • Некоторые механизмы хранения (такие как MyISAM) кэшируют только индексы в памяти, а кэширование данных зависит от операционной системы. Таким образом, просто получить доступ к индексу можно без использования системных вызовов (которые часто занимают много времени).
  • Для механизма InnoDB нет необходимости обращаться к первичному индексу, если вторичный индекс может покрыть запрос.

6. Принцип самого левого префикса

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

Суть совместного индекса:

При создании объединенного указателя (a,b,c) это эквивалентно созданию (a) одностолбцового указателя, (a,b) объединенного указателя и (a,b,c) объединенного указателя.
Если вы хотите, чтобы индекс вступил в силу, вы можете использовать только три комбинации a и a, b и a, b и c.

Преимущества индексации

  • Значительно сокращает количество строк данных, которые сервер должен сканировать.
  • Помогите серверу избежать сортировки и группировки, а также избежать создания временных таблиц (индексы B+Tree упорядочены и могут использоваться для операций ORDER BY и GROUP BY. Временные таблицы в основном создаются в процессе сортировки и группировки, поскольку сортировка и группировка не выполняются). требуется группировка, нет необходимости создавать временную таблицу).
  • Превратите случайный ввод-вывод в последовательный ввод-вывод (индексы B+Tree упорядочены и хранят смежные данные вместе).

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

  • Для очень маленьких таблиц в большинстве случаев простое полное сканирование таблицы более эффективно, чем индексация;
  • Для средних и больших таблиц индексы очень эффективны;
  • Но для очень больших таблиц стоимость создания и обслуживания индексов соответственно возрастет. В этом случае необходимо использовать технологию, которая может напрямую различать набор запрашиваемых данных, вместо сопоставления запись за записью, например, можно использовать технологию секционирования.

резюме

Индекс — очень важная функция в MySQL.Если вы сможете правильно использовать индекс в повседневной разработке, это может значительно улучшить производительность выполнения операторов SQL, поэтому необходимо понять принцип.


Большая часть статьи ссылается на

GitHub.com/CY C2018/CS-…


Категории