В MySQL существует множество типов индексов, которые могут обеспечить более высокую производительность для различных сценариев. Индекс B-Tree является наиболее распространенным типом индекса MySQL.Когда речь идет об индексе MySQL, если нет специального описания, он относится к индексу B-Tree. В этой статье подробно объясняется базовая структура индекса B-Tree, принципы и характеристики его использования. В целях экономии вашего времени основное содержание этой статьи выглядит следующим образом:
- Базовая структура индекса B-дерева
- Правила использования индексов B-Tree
- кластеризованный индекс
- Различия между индексами движка InnoDB и MyISAM
- свободный индекс
- индекс покрытия
Индекс B-дерева
Индекс B-Tree использует B-Tree для хранения данных, конечно, разные механизмы хранения реализуются по-разному. B-Tree обычно означает, что все значения хранятся по порядку, и каждая конечная страница находится на одинаковом расстоянии от корня.На рисунке 1 показано абстрактное представление индекса B-Tree, из которого вы можете увидеть индекс B-Tree MySQL. Общий рабочий механизм.
Базовая структура данных индекса B-дерева обычно представляет собой дерево B+, и его конкретная структура данных и преимущества здесь подробно не описываются.На следующем рисунке показано абстрактное представление индекса B-дерева, которое приблизительно отражает то, как MyISAM индексы работают, в то время как InnoDB использует другую структуру.
MySQL может добавить индекс B-дерева к одному столбцу или добавить индекс B-дерева к нескольким столбцам данных. Данные нескольких столбцов объединяются в порядке добавления объявления индекса и сохраняются на странице B-дерева. Предположим, у вас есть следующая таблица данных:
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
birthday date not null,
gender enum('m','f') not null
key(last_name, first_name, birthday)
);
Для каждой строки данных в таблице индекс содержит значения столбцов last_name, first_name и Birthday.На следующем рисунке показано, как индекс организует хранение данных.
Индекс B-Tree использует B-Tree в качестве своей структуры данных для хранения данных, и используемые им правила запросов также определяются этим. Вообще говоря, индексы B-Tree подходят для поиска полного значения ключа, диапазона значений ключа и префикса ключа, где поиск префикса ключа подходит только для поиска по крайнему левому префиксу. Принципы запросов, поддерживаемые индексами B-Tree, следующие:
-
Сопоставление полного значения: Сопоставление полного значения означает сопоставление всех столбцов в индексе,
-
Совпадение с крайним левым префиксом: Упомянутый ранее индекс можно использовать для поиска всех людей с фамилией Аллен, т.е. используется только первый столбец индекса.
-
Соответствие префиксу столбца: вы также можете сопоставить только начало значения столбца. Например, индекс, упомянутый ранее, может быть использован для поиска всех людей с фамилией, начинающейся с J. Здесь тоже используется только первый столбец индекса.
-
Значения диапазона соответствия: например, индекс, упомянутый ранее, можно использовать для поиска людей с фамилиями между Алленом и Бэрримором. Здесь также используется только первый столбец индекса.
-
Точное соответствие одному столбцу, а диапазон соответствует другому столбцу. Упомянутый ранее индекс также можно использовать для поиска всех людей, чья фамилия Аллен и чье имя начинается с буквы К (например, Ким, Карл и т. д.). То есть первый столбец last_name соответствует всем, а второй столбец first_name соответствует диапазону.
Поскольку узлы индексного дерева упорядочены, помимо поиска по значению индекс также может использоваться для операций ORDER BY в запросах (поиск по порядку), если предложение ORDER BY удовлетворяет нескольким перечисленным выше типам запросов, то этот индекс также может соответствовать соответствующим требованиям сортировки.
Вот некоторые ограничения для индексов B-Tree:
- Индекс нельзя использовать, не начав поиск по крайнему левому столбцу индекса. Например, индекс в приведенном выше примере не может найти ни человека по имени Билл, ни день определенного дня рождения, потому что ни один из этих двух столбцов не является крайним левым столбцом данных.
- Если в запросе есть запрос диапазона для столбца, все столбцы справа от него не могут использовать индекс для оптимизации поиска.
кластеризованный индекс
Кластерный индекс — это не отдельный тип индекса, а метод хранения данных. Точные детали зависят от того, как это реализовано, но кластеризованные индексы InnoDB фактически хранят индексы B-Tree и строки данных в одной и той же структуре.
Когда таблица имеет кластеризованный индекс, ее строки данных фактически хранятся на листовых страницах индекса, а это означает, что строки данных и значения смежных ключей компактно хранятся вместе.
На следующем рисунке показано, как хранятся записи в кластеризованном индексе. Обратите внимание, что конечные страницы содержат все строки данных для строки, а узловые страницы содержат только индексные столбцы.
Кластеризованные индексы могут повысить производительность, но также могут вызвать серьезные проблемы с производительностью. Кластерные данные имеют ряд важных преимуществ:
- Доступ к данным быстрее, а кластеризованный индекс хранит индекс и данные в одном B-дереве, поэтому выборка данных из кластеризованного индекса обычно выполняется быстрее, чем поиск в некластеризованном индексе.
- Запросы, использующие сканирование покрывающего индекса, могут напрямую использовать значение первичного ключа в узле страницы.
Если вы сможете в полной мере воспользоваться перечисленными выше преимуществами при разработке таблиц и запросов, вы сможете значительно повысить производительность. В то же время у кластерных индексов есть и недостатки:
- Порядок вставки сильно зависит от порядка вставки. Вставка в порядке первичного ключа — это самый быстрый способ вставки данных в таблицу InnoDB.Необходимо избегать случайного (прерывистого и полезного для большого диапазона распределения) кластеризованного индекса значения первичного ключа, такого как использование UUID в качестве первичного key, но следует использовать что-то вроде автоинкрементного столбца AUTO_INCREMENT.
- Обновление столбца кластеризованного индекса обходится дорого, поскольку InnoDB вынуждена перемещать каждую обновленную строку в новое место.
- Таблица, основанная на кластеризованном индексе, может столкнуться с «разделением страниц» при вставке новой строки или при обновлении первичного ключа и необходимости перемещения строки. Когда значение первичного ключа строки требует, чтобы строка была вставлена в полную страницу, механизм хранения разделит страницу на две страницы, чтобы разместить строку, что является операцией разделения страницы. Разделение страниц приводит к тому, что таблицы занимают больше места на диске
- Вторичные индексы могут быть больше, чем ожидалось, поскольку конечные узлы во вторичном индексе содержат столбцы первичного ключа строки, на которую ссылаются.
- Для доступа к вторичному индексу требуется два поиска по индексу вместо одного.
Разница индексов между InnoDB и MyISAM
Распределение данных кластеризованного индекса и некластеризованного индекса отличается, и распределение данных соответствующего индекса первичного ключа и вторичного индекса также отличается, что обычно сбивает с толку и неожиданно. На следующем рисунке показаны различные индексы и методы хранения данных MyISAM и InnoDB.
Распределение данных MyISAM очень простое.Они хранятся на диске в порядке вставки данных.Листовые узлы индекса первичного ключа и вторичного индекса хранят указатели на соответствующие строки данных.
InnoDB, кластеризованный индекс — это «просто» таблица, поэтому он не требует отдельного хранилища строк, как MyISAM. Каждый конечный узел кластеризованного индекса содержит значение первичного ключа и все остальные столбцы (в данном случае col2).
Вторичный индекс InnoDB и кластеризованный индекс сильно отличаются. Листовой узел вторичного индекса InnoDB — это не «указатель строки», а значение первичного ключа, которое используется в качестве «указателя» на строку.
свободное сканирование индекса
MySQL не поддерживает свободное сканирование индекса, то есть не может сканировать индекс прерывистым образом. Обычно при сканировании индекса MySQL необходимо сначала определить начальную и конечную точки.Даже если требуются данные лишь в небольшой части индекса, MySQL все равно должен сканировать каждую запись в индексе.
Ниже мы проиллюстрируем это на примере, предполагая, что у нас есть следующий индекс (a,b) со следующим запросом:
mysql>SELECT * FROM tb1 WHERE b BETWEEN 2 AND 3;
Поскольку ведущим полем индекса является столбец a, но в запросе указано только поле b, MySQL не может использовать этот индекс, поэтому он может найти совпадающие строки только путем полного сканирования таблицы, как показано на следующем рисунке.
Если вы понимаете физическую структуру индекса, нетрудно найти более быстрый способ выполнения вышеуказанного запроса. Физическая структура индекса (а не API механизма хранения) заключается в том, что вы можете сначала просмотреть диапазон столбца b, соответствующий первому значению столбца a, а затем перейти ко второму отличному значению столбца a, чтобы сканировать соответствующий диапазон столбца b. На приведенной ниже диаграмме показано, как выглядел бы этот процесс, если бы он был реализован MySQL.
Обратите внимание, что в настоящее время нет необходимости использовать предложение WHERE для фильтрации, поскольку сканирование свободного индекса уже пропустило все ненужные записи.
MySQL 5.0 и более поздние версии могут использовать сканирование свободного индекса в некоторых специальных сценариях, например, в групповом запросе вам нужно найти максимальное и минимальное значения группы:
mysql> EXPLAIN SELECT actor_id, MAX(film_id)
-> FROM sakila.film.film_actor
-> GROUP BY actor_id;
********************************************* 1. row ***********************************
id: 1
select_type: SIMPLE
table: film_actor
type: range
possible_keys: NULL
key: PRIMARY
key_len: 2
ref: NULL
rows: 396
Extra: Using index for group-by
В поле «Дополнительно» в EXPLAIN отображается «Использование индекса для группировки», что означает, что здесь будет использоваться сканирование свободного индекса.
индекс покрытия
Индекс — это не только эффективный способ поиска данных, но и прямой способ получения данных столбца. MySQL может использовать индексы для прямой выборки данных для столбцов, поэтому нет необходимости читать строки данных. Если индекс содержит значения всех полей, которые необходимо запросить, мы называем его «покрывающим индексом». Покрывающие индексы — очень полезные инструменты, которые могут значительно повысить производительность. SQL-запросы должны только сканировать индекс без возврата к таблице, что принесет много преимуществ:
- Количество и размер записей индекса обычно намного меньше, чем записей и размеров строк данных, поэтому, если нужно читать только индекс, MySQL может значительно сократить объем доступа к данным.
- Поскольку индексы хранятся в порядке столбцов, поиск по диапазону с интенсивным вводом-выводом требует гораздо меньшего количества операций ввода-вывода, чем случайное чтение каждой строки с диска.
- Покрывающие индексы особенно полезны для таблиц InnoDB из-за кластерных индексов InnoDB. Вторичный индекс InnoDB хранит первичный ключ строки в конечном узле.Если вторичный первичный ключ индекса может покрыть запрос, второй запрос индекса первичного ключа избегается.
Когда инициируется запрос с покрываемым индексом (также называемый запросом покрывающего индекса), информация «Использование индекса» отображается в столбце «Дополнительно» EXPLAIN. Например, таблица sakila.inventory имеет многоколоночный индекс (store_id, film_id). Если MySQL нужен доступ только к этим двум столбцам, он может использовать этот индекс в качестве покрывающего индекса следующим образом:
mysql> EXPLAIN SELECT store_id, film_id FROM sakila.inventory
*********************************1.row***************************************
id:1
select_type:SIMPLE
table:inventory
type:index
possible_keys:NULL
key:idx_store_id_film_id
key_len:3
ref:NULL
rows:4673
Extra:Using Index
Подпишитесь на последние статьи, добро пожаловать в мою публичную учетную запись WeChat
Ссылаться на:
- Структура данных и принцип алгоритма индекса MySQL
- «Высокопроизводительный MySQL»