Индекс — это структура данных, используемая для быстрого запроса строк, точно так же, как оглавление книги — это индекс.Если вы хотите найти определенную тему в книге, вы обычно сначала найдете соответствующий номер страницы. В MySQL механизм хранения использует индекс аналогичным образом, сначала находя соответствующее значение в индексе, а затем находя соответствующую строку в соответствии с соответствующей записью индекса.
Давайте сначала рассмотрим несколько типов индексов и структуру индексов.
тип индекса
B-дерево
Большинство механизмов хранения поддерживают индексы B-tree. B-дерево обычно означает, что все значения хранятся по порядку и что каждый листовой узел находится на одинаковом расстоянии от корня. Индексы B-дерева могут ускорить доступ к данным, поскольку подсистеме хранения больше не нужно выполнять полное сканирование таблицы для получения данных. На рисунке ниже показано простое B-дерево.
Процесс запроса B-дерева:
Как показано на рисунке выше, я хочу найти букву E. Процесс поиска выглядит следующим образом:
(1) Получите ключевое слово корневого узла для сравнения Текущее ключевое слово корневого узла — M, E
(4) Выньте всю информацию этой записи через информацию указателя;
В+ дерево
На следующем рисунке показана структура дерева B+.Дерево B+ является обновленной версией дерева B. Мы можем наблюдать, в чем разница между деревом B и деревом B+?
Разница между деревом B+ и деревом B заключается в следующем:
- В узлах B-дерева нет повторяющихся элементов, а в B+-дереве есть.
- Информация об указателе данных B-дерева промежуточного узла сохраняется, сохраняется только дерево B+ до конечного узла.
- Каждый листовой узел дерева B+ имеет указатель на следующий узел, связывающий все листовые узлы вместе.
На рисунке ниже мы можем интуитивно увидеть разницу между деревом B и деревом B+: фиолетовая стрелка — это указатель на проиндексированные данные, а большая красная стрелка — указатель на следующий конечный узел.Мы предполагаем, что проиндексированный столбец является первичным ключом, и теперь ищем запись с первичным ключом 5 и моделируем процесс поиска:
B-дерево: Найдя 5 в узле предпоследнего слоя, можно сразу получить указатель на получение данных строки и прекратить поиск.
В+ дерево: После нахождения 5 в узле предпоследнего слоя, поскольку в промежуточном узле нет информации об указателе, продолжайте поиск вниз, найдите 5 в конечном узле, получите указатель для получения данных строки и остановите поиск.
Элемент каждого родительского узла дерева B+ появится в дочернем узле и будет самым большим (или самым маленьким) элементом дочернего узла. Конечные узлы хранят все данные индексированного столбца.
Каковы преимущества дерева B+ перед деревом B?
- Поскольку в промежуточном узле нет указателя, страница диска того же размера может вместить больше элементов узла, а высота дерева меньше. (В случае того же объема данных дерево B+ более «короткое», чем дерево B), и поиск выполняется быстрее.
- Дерево B+ должно обращаться к листовому узлу для получения данных каждый раз при поиске, в то время как дерево B не обязательно, дерево B может получать данные на нелистовых узлах. Таким образом, время поиска дерева B+ более стабильно.
- Каждый листовой узел B+-дерева имеет указатель на следующий листовой узел, что удобно для запроса диапазона и запроса полной таблицы: нужно только просканировать указатель от первого листового узла, в то время как B-дерево нужно сделать в - обход порядка.
Разобравшись со структурой дерева B+, анализируем конкретную таблицу:
create table Student(
last_name varchar(50) not null,
first_name varchar(50) not null,
birthday date not null,
gender int(2) not null,
key(last_name, first_name, birthday)
);
Для каждой строки данных в таблице индекс содержитname,birthdayзначение столбца. На следующем рисунке показана структура этого индекса:
Индекс сортирует несколько значений поcreate tableПорядок столбцов при индексе определен в выписке, то есть, если имена совпадают, они сортируются по дню рождения.
Структура дерева B+ определяет, что этот индекс эффективен для следующих типов запросов:
полное соответствие стоимости
Сопоставьте все столбцы в индексе, например, найдите имена, имена которыхCuba AllenДень рождения1960-01-01люди.
соответствует крайнему левому префиксу
Найти фамилиюAllenлюдей, т. е. использовать только первый столбец индекса.
соответствие префиксу столбца
Соответствует началу значения столбца, например, поиск всех людей с фамилией, начинающейся с J.
значение диапазона соответствия
Найдите фамилию вAllenиBarrymoreлюди между ними.
Совпадение ровно с одним столбцом, а диапазон совпадет с другим столбцом
Найти фамилиюAllen, чье имя начинается на букву К. то есть первый столбецlast_nameСовпадение со всеми, второй столбецfirst_nameАссортимент совпадает.
Запросы, которые обращаются только к индексу
Запросу нужен доступ только к индексу, а не к строке данных. Этот тип индекса называется индексом покрытия.
Некоторые ограничения:
- Индекс нельзя использовать, если поиск не начинается с крайнего левого столбца индекса. Например, индекс в приведенном выше примере нельзя использовать для поиска людей с определенным днем рождения, потому что день рождения не является крайним левым столбцом данных. не могу найти
last_nameЛицо, оканчивающееся на определенную букву. - Индексированные столбцы нельзя пропускать. Указанный выше индекс нельзя использовать для поиска
last_nameзаSmithИ человек с конкретным днем рождения. Если не указаноfirst_name, MySQL может использовать только первый столбец индекса. - Если в запросе есть запрос диапазона для столбца, поиск во всех столбцах справа невозможен с помощью оптимизации индекса. Например запрос
WHERE last_name='Smith' AND first_name LIKE 'J%' AND birthday='1996-05-19', этот запрос может использовать только первые два столбца индекса.
хэш-индекс
Хэш-индекс, допустимы только запросы, которые точно соответствуют всем столбцам индекса. Для каждой строки данных механизм хранения вычисляет хэш-код для всех индексированных столбцов. Хэш-индекс хранит все хэш-коды в индексе, сохраняя при этом указатель на каждую строку данных в хэш-таблице. Если хэш-значения нескольких столбцов одинаковы, индекс будет хранить несколько записей-указателей в одной и той же хеш-записи в связанном списке. Поскольку сам индекс хранит только соответствующее хэш-значение, структура индекса очень компактна, а скорость поиска хэш-индекса очень высока. Но хэш-индексы также имеют свои ограничения:
- Хэш-индексы не хранятся в порядке индексов и не могут использоваться для сортировки.
- Поиск частичного совпадения столбца индекса не поддерживается.
- Поиск диапазона не поддерживается.
кластеризованный индекс
Каждая таблица, механизмом хранения которой является InnoDB, имеет специальный индекс, называемый кластерным индексом. Кластерный индекс — это не отдельный тип индекса, а способ хранения данных. Когда таблица имеет кластеризованный индекс, ее строки данных фактически хранятся на листовых страницах. В таблице не может быть двух мест для хранения данных, поэтому таблица может иметь только один кластеризованный индекс.
Поскольку механизм хранения отвечает за реализацию индекса, не все механизмы хранения поддерживают кластеризованные индексы. Столбец индекса кластеризованного индекса в таблице InnoDB является первичным ключом, поэтому кластеризованный индекс также называется индексом первичного ключа.
Например, следующая таблица InnoDB:
create table Student(
id int(11) primary key auto_increment,
last_name varchar(50) not null,
first_name varchar(50) not null,
birthday date not null
);
Структура кластеризованного индекса (индекса первичного ключа) выглядит следующим образом:Это дерево класса B+, его листовая страница содержит все данные строки, а узловая страница содержит только столбец индекса (т. е. первичный ключ).
Вторичные индексы
Для таблиц InnoDB индексы, построенные на других столбцах, которые не являются столбцами первичного ключа, являются вторичными индексами (поскольку имеется только один кластеризованный индекс). Вторичных индексов может быть 0, 1 или более. В чем разница между вторичным индексом и кластеризованным индексом? Страница узла вторичного индекса, как и кластеризованный индекс, хранит только значение индексированного столбца, в то время как конечная страница вторичного индекса также хранит значение первичного ключа, соответствующего этому столбцу, в дополнение к значению столбца индекса.
Сравнение распределения данных между InnoDB и MyISAM
Возьмите следующую таблицу в качестве примера, давайте посмотрим, как InnoDB и MyISAM хранят эту таблицу:
create table layout_test(
col1 int(11) primary key,
col2 int(11) not null,
key(col2)
);
Распределение данных таблиц InnoDB
Кластерные индексы (индексы первичного ключа) распределяются следующим образом:Как видите, конечные узлы хранят данные всей таблицы, а не только столбцы индекса.Каждый конечный узел содержит значение первичного ключа, идентификатор транзакции, указатель отката для транзакции и MVCC, а также все остальные столбцы (col2).
Распределение вторичного индекса выглядит следующим образом:Листовой узел вторичного индекса хранит не «указатель строки», а значение первичного ключа, которое используется как «указатель» на строку. Такая стратегия снижает необходимость обслуживания вторичных индексов при перемещении строк или разделении страниц данных. Использование первичного ключа в качестве указателя приведет к тому, что вторичный индекс займет больше места, но преимущество состоит в том, что InnoDB не нужно обновлять указатель во вторичном индексе при перемещении строк.
Распределение данных таблиц MyISAM
Индекс столбца col1:Индекс столбца col2:
На самом деле индекс первичного ключа в MyISAM по структуре ничем не отличается от других индексов.
На рисунке ниже вы можете увидеть разницу между сохранением данных и индексов InnoDB и MyISAM.
Преимущества кластерных индексов:
- Связанные данные могут быть сохранены вместе.Например, при реализации почтового ящика данные агрегируются в соответствии с идентификатором пользователя, и все электронные письма пользователя могут быть получены путем чтения нескольких страниц данных.
- Кластеризованный индекс хранит индекс и данные в одном B-дереве, поэтому выборка данных из кластеризованного индекса выполняется немного быстрее, чем из некластеризованного индекса.
Недостатки кластерных индексов:
- Скорость вставки сильно зависит от порядка вставки. Вставка в порядке первичного ключа — самый быстрый способ загрузить данные в таблицу InnoDB. Если один из дисков заполнен, но в эту страницу должна быть вставлена новая строка, механизм хранения разделит строку на две страницы, чтобы разместить строку, что является операцией разделения страницы. Разделение страниц приводит к тому, что таблицы занимают больше места на диске.
- Обновление столбца кластеризованного индекса требует больших затрат и заставляет InnoDB перемещать каждую обновленную строку в новое место.
- Для доступа к данным с помощью вторичного индекса требуется два поиска по индексу, а не один. Поскольку необходимо получить значение первичного ключа из конечного узла вторичного индекса, а затем найти соответствующую строку в кластеризованном индексе в соответствии с первичным ключом, требуются два поиска B-дерева.
Стратегии для последовательных первичных ключей:
Использование автоматического увеличения первичных ключей в таблицах InnoDB — это простая и высокопроизводительная стратегия, обеспечивающая упорядоченную запись данных. Лучше избегать случайных кластеризованных индексов, так как с точки зрения производительности использование UUID в качестве кластеризованного индекса — это плохо, не только дольше вставляется строка, но и сам индекс занимает больше места.
Использованная литература:
«Высокопроизводительный MySQL (третье издание)»
stackoverflow.com/questions/8…
Dev.MySQL.com/doc/Furious/…
Woohoo Краткое описание.com/fear/1 2560 0 ой...