Заметки MySQL — типы индексов

написать впереди

Это просто примечание к чтению "Высокопроизводительный MySQL". Я чувствую, что студенты, которые думают, что вода проблематична, закрывают верхний правый угол, спасибо~

Типы индексов включают B-дерево, хэш-индекс, R-дерево, полнотекстовый индекс и т. д. Здесь мы в основном суммируем B-дерево и хэш-индекс.

B-Tree

Прежде чем говорить об индексе, мы должны поговорить о B-Tree.

B-Tree — это сбалансированное дерево поиска, структура которого аналогична обычному бинарному дереву, разница в том, что каждый узел допускает больше дочерних узлов.

Структура B-дерева

B-Tree, изображение здесь напрямую относится к изображению первой статьи в справочнике~ Если есть какие-либо нарушения, пришлите мне личное сообщение~

B+древовидная структура

B+Tree — это вариант B-Tree, а также сбалансированное бинарное дерево. , пожалуйста, пришлите мне личное сообщение~

Определение B-дерева

Эта часть относится к методу определения руководства по расчету ~

B-дерево T обладает следующими свойствами:

Каждый узел x имеет следующие свойства:
- x.n, указывающее количество ключевых слов, хранящихся в узле x
- Сами ключевые слова x.n хранятся в порядке неубывания
- x.leaf указывает, является ли x конечным узлом
Внутренний узел содержит указатели x.n+1 на своих дочерних элементов.
Каждый листовой узел имеет одинаковую глубину, которая является высотой дерева. $h=log_t \frac{n+1}{2}$
Количество ключевых слов в каждом узле имеет верхнюю и нижнюю границы, которые представлены минимальной степенью B-дерева, а именно t,
- За исключением корневого узла и конечного узла, количество дочерних узлов каждого узла равно $t \leq n \leq 2t$
- За исключением корневого узла и конечного узла, количество ключевых слов каждого узла равно $t-1 \leq n \leq 2t-1$
Количество дочерних узлов нелистовых узлов в B+Tree такое же, как и количество ключевых слов.

B-Tree vs B+Tree

Прочитав картинку, подведем итог~

B-дерево,

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

Б+Дерево,

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

Преимущества B+Tree,

Поскольку нелистовые узлы не хранят фактических данных, в памяти хранится больше ключевых слов, а это означает, что объем информации в одном дисковом вводе-выводе будет больше, чем у B-Tree.
Листовой узел добавляет последовательный связанный список, который больше подходит для интервального запроса.

Why B-Tree

На самом деле, красно-черные деревья также могут использоваться в качестве индексов.Почему дерево B/B+ используется в MySQL для реализации индексов? Поскольку MySQL является базой данных на дисках, процесс поиска по индексу неизбежно будет включать дисковый ввод-вывод, поэтому производительность индекса зависит от двух ключевых моментов:

Количество дисковых операций ввода-вывода
Скорость вычислений процессора

Поэтому при проектировании индекса необходимо максимально сократить количество дисковых операций ввода-вывода, а MySQL управляет записями в виде страниц.Когда B-Tree создает новый узел, он напрямую обращается к пространству страницы, которое гарантирует, что узел также физически хранится на странице, а выделение компьютерной памяти выравнивается по страницам, поэтому для узла требуется только один ввод-вывод. Поиск в дереве требует не более h - 1 операций ввода-вывода, поскольку корневой узел находится в памяти, а B-дерево может иметь большое количество узлов, поэтому h очень мало, а количество узлов связано с размером Очевидно, что для тех же данных h красно-черного дерева намного глубже, поэтому в качестве структуры индекса обычно используется B/B+Tree.

Асимптотическая временная сложность B-Tree равна, здесь N — количество ключевых слов, d — 1/2 исходящей степени внутреннего узла, O(h)=O(log_dN)O(h)=O(log_dN)

Асимптотическая временная сложность красно-черного дерева равна O(h)

Поэтому самоочевидно, почему MySQL использует B/B+Tree для реализации индексов.

Работа с B-деревом

Некоторые операции B-Tree здесь не показаны, потому что в руководстве по расчетам приведен псевдокод и очень подробные диаграммы.

Вставить ключевое слово: сначала найдите конечный узел, в который следует вставить ключевое слово, если узел заполнен, то есть количество ключевых слов, в это время он должен быть разделен в соответствии со средним ключевым словом ключевого слова в конечном узле, а среднее ключевое слово будет перемещено в родительский узел узла.Если родительский узел также заполнен, повторите описанную выше операцию. до корневого узла, если доходит до корневого узла, значит высота увеличилась на один слой
Удаление ключевых слов: Удаление ключевых слов сложнее, чем вставка ключевых слов, потому что удаляются не только листовые узлы, но и внутренние узлы.В это время нам нужно рассмотреть, как разместить дочерние элементы внутренних узлов, а также убедиться, что удаленные B- Дерево соответствует требованиям, поэтому существует несколько ситуаций для удаления ключевых слов.
- Если k находится в узле x, а x является конечным узлом, то удалите k непосредственно из x.
- Если количество ключевых слов в узле u1 перед k в x равно t, то найдите наибольший ключ ключевого слова в u1, удалите ключ в u1 и замените k на ключ в x.
- Если количество ключевых слов в узле u1 до k в x меньше t, то найти узел u2 после k в x, если количество ключевых слов в u2 равно t, то найти наименьший ключевой ключ в u2, удалить ключ в u2 и замените k ключом в x
- Если количество ключевых слов двух узлов до и после равно t-1, то объедините u1 и u2, удалите k в x и укажите указатель в x на новый узел
- Если k не находится в текущем внутреннем узле, после нахождения внутреннего узла, в котором находится k, выполните указанные выше операции.

Индекс B-дерева

Индекс со структурой B-Tree является наиболее распространенным типом индекса. Например, InnoDB и MyISAM — это индексы со структурой индекса B-Tree. На самом деле дерево B+ — это структура индекса. Tree и B+Tree заключается в том, что B+ Tree добавляет последовательные указатели доступа к листовым узлам, чтобы облегчить обход диапазона конечных узлов. Здесь мы в основном вводим два разных индекса, InnoDB и MyISAM.

InnoDB

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

Вторичный индекс кластеризованного индекса хранит не указатель на физическое расположение строки, а значение первичного ключа строки, поэтому, если вы ищете строку через вторичный индекс, вам нужно найти конечный узел вторичного index для получения соответствующего значения первичного ключа, а затем перейти к поиску соответствующей строки. Для InnoDB адаптивные хэш-индексы могут уменьшить такое дублирование работы.

MyISAM

MyISAM поддерживает некластеризованные индексы, а отличие от InnoDB в том, что физические адреса, указывающие на соответствующие строки, хранятся на листовых узлах, а это означает, что индексы и данные фактически хранятся отдельно.

MyISAM использует технологию префиксного сжатия, поэтому в память можно поместить больше индексов.По умолчанию сжимаются только строки, но целые числа также могут быть сжаты с помощью настройки параметра. Метод сжатия заключается в том, чтобы полностью сохранить первый IE в индексном блоке, а затем сравнить остальные значения с первым значением, чтобы получить количество байтов с тем же префиксом и оставшимися разными частями суффикса, и сохранить эту часть. Например, если первое значение в индексном блоке — «выполнение», а второе — «производительность», то префикс второго значения сжимается и сохраняется в виде «7,ance». MyISAM использует аналогичное сжатие префикса для указателей строк.

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

Замок

InnoDB использует блокировки строк, поэтому транзакции поддерживаются, в то время как MyISAM использует блокировки таблиц и не поддерживает транзакции.

Область применения

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

хэш-индекс

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

преимущество

Сам индекс хранит только хэш-код, поэтому структура очень компактная, а скорость поиска высокая.

ограничение

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

Адаптивные хэш-индексы для InnoDB

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

Когда InnoDB замечает, что значение индекса используется очень часто, она создает хэш-индекс на основе индекса B-дерева в памяти, так что B-дерево также может иметь некоторые преимущества хэш-индекса, такие как быстрый поиск хэша.

Конечно, если движок хранилища не поддерживает хэш-индекс, пользователь также может настроить хеш-индекс, поэтому производительность будет выше, но недостатком является то, что вам нужно поддерживать хеш-значение самостоятельно.SHA1()иMD5()В качестве хэш-функции, поскольку эти две функции являются надежными функциями шифрования, цель разработки состоит в том, чтобы максимально устранить конфликты.Сгенерированный хэш-код представляет собой очень длинную строку, которая занимает много места.Требования к конфликту для индекса в хэш-индекс не так высок.

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

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

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

Reference

B-деревья и B+ деревья

От дерева B, дерева B+, дерева B* к дереву R

«Введение в алгоритмы»

«Высокопроизводительный MySQL»