«MySQL» раскрывает тайну индекса

Диаграмма картирования знаний MySQL, смотрите всю статью на одной картинке:

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

1. Что такое индекс?

Что такое индекс доступа к официальным документам. Роль официальных документов, написанных указателем, и отсутствие указателя принесет полное сканирование таблицы, очень трудоемко.Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.Проще говоря, индекс предназначен для повышения скорости запросов. Это легко понять, как и словарь английского языка в прошлом: если нет предыдущего каталога для поиска слов, эффективность очень низкая, и вам нужно искать полный текст.

2. Принцип реализации индекса

Чтобы понять принцип реализации индекса, сначала посмотрите на базовую реализацию индекса.Большинство индексов MySQL реализованы B-Tree, а B-Tree имеет B-дерево и дерево B+. А некоторые используют хэш-индексы. В этой статье в основном представлено B-дерево (дерево баланса).

2.1 Бинарное дерево поиска

Прежде чем говорить о B-дереве, давайте кратко разберемся с бинарными деревьями поиска.

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

2.2 b-дерево

Вообще говоря, B-дерево, вообще относится к B-дереву, его также можно назвать сбалансированным многоходовым деревом поиска.Смысл баланса можно понимать как сбалансированное бинарное дерево (это пустое дерево или разница высот между его левое и правое поддеревья). Абсолютное значение не больше 1, а левое и правое поддеревья представляют собой сбалансированное бинарное дерево.), многоходовость означает наличие не менее 2 дочерних узлов нелистовых узлов. Характеристики B-Tree также очень утомительны, и я долго размышлял после проверки введения в алгоритмы. Картинка ниже — это картинка из введения в алгоритмы, а светло заштрихованная часть — это узел, который проверялся при поиске буквы R.

Следующие особенности B-деревьев во введении в алгоритмы:

1. Каждый узел x имеет следующие свойства:
   1. х.н. Он представляет количество ключевых слов, хранящихся в x;
   2. x.key1,x.key2,...,x.keyn. Они представляют собой n ключей x, хранящихся в неубывающем порядке, то есть x.key1≤x.key2≤...≤x.keyn;
   3. х.лист. Это логическое значение, которое равно TRUE, если x является конечным узлом, иначе FALSE;
2. х.с1,х.с2,...,х.сп+1. Они указатели на собственных детей. Если узел является конечным узлом, эти свойства отсутствуют.
3. Ключ x.keyi разделяет диапазон ключей, хранящийся в каждом поддереве, то есть k1≤x.key1≤k2≤x.key2≤...≤x.keyn≤kn+1. Среди них ki(i=1,2,....,n+1) представляет собой любое ключевое слово, хранящееся в поддереве с корнем x.ci.
4. Каждый листовой узел имеет одинаковую глубину, которая равна высоте h листа.
5. Количество ключей, содержащихся в каждом узле, имеет верхнюю и нижнюю границы. Эти границы представлены фиксированным целым числом t (t ≥ 2), называемым минимальной степенью:
   1. Нижняя граница: каждый узел, кроме корня, должен иметь не менее t−1 ключей. Следовательно, каждый внутренний узел, кроме корня, имеет не менее t потомков.
   2. Верхняя граница: каждый узел содержит не более 2t−1 ключевых слов. Следовательно, внутренний узел может иметь не более 2t потомков. Говорят, что узел заполнен, если он имеет ровно 2t−1 ключей.

Пока еще запутался, тогда по схеме объясните все про эти особенности.

пункт 1Это означает информацию, содержащуюся в каждом узле: n представляет количество ключевых слов, хранящихся в узле.Например, левый дочерний элемент M на приведенном выше рисунке имеет 2 ключевых слова, D и H; x.key, который является конкретной информацией о ключевом слове, например, D, D на самом деле состоит из двух частей, которые можно понимать как карту, {ключ: данные}, x.key представляет эту карту в широком смысле, включая конкретный ключ и сохраненные данные данных. Обычно это запись; x.leaf должен сказать, является ли весь узел листовым узлом.

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

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

пункт 4Это означает, что высота каждого листового узла одинакова, вы можете понять это, взглянув на картинку, которая также является источником слова баланс.

пункт 5Говоря об ограничении количества ключевых слов на узел, невозможно, чтобы каждый узел мог хранить неограниченное количество ключевых слов. t — минимальная степень. Чтобы понять это, вы можете поискать в Google определение степени и порядка. На приведенном выше рисунке показано B-дерево порядка 4. На приведенном выше рисунке t=2, тогда у каждого внутреннего узла может быть 2, 3 и 4 потомка. Диапазон количества дочерних элементов равен [t, 2t], а диапазон ключей каждого узла — [t-1, 2t-1]. Это чтобы различать.

Ниже более наглядно показано B-дерево 4-го порядка.

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

2,3 Б + дерево

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

Дерево B+, используемое в общей системе баз данных, было оптимизировано на основе классического изображения выше и стало деревом B+ с последовательными указателями доступа, как показано на следующем рисунке. Это повышает производительность интервального доступа.Например, если вы хотите запросить все записи данных с ключами от 18 до 49, когда будет найдено 18, вы можете получить доступ ко всем узлам данных одновременно, обходя узлы и указатели по порядку, который значительно повышает эффективность интервальных запросов.

3. Почему B-Tree (B+) используется для реализации индексации базы данных

3.1 Принцип доступа к диску

Введение в данные начинается со слов: B-дерево — это сбалансированное дерево поиска, разработанное для дисков или других вспомогательных устройств хранения с прямым доступом. Вспомогательное запоминающее устройство упоминалось выше, так что давайте разберемся в принципе и откуда оно взялось? Компьютерные системы имеют основную память и дисковую вспомогательную память.Главной памятью обычно является то, что мы называем оперативной памятью, то есть память, которая здесь не обсуждается. Сам индексный файл очень большой и обычно не существует в памяти, поэтому индекс часто хранится на диске в виде файла, поэтому для извлечения индекса требуются дисковые операции ввода-вывода. На рисунке ниже показан типичный дисковод.

Данные чтения диска опираются на механическое движение диска. Каждый раз, когда диск прочитан три части: Ищите время, задержка вращения, время передачи. Ищите время относится к времени, указанное время, указанная магнитная дорожка. Это может превратиться в 120 раз в секунду, задержка вращения составляет 1/120/2 = 4,17 мс; относится к времени передачи для чтения или записи данных с диска на диск, обычно в нескольких десятых миллисекундах, по отношению к первому Два времени можно игнорировать. Затем время доступа к диску для чтения данных, то есть время, время диска ввода / вывода влево и справа около 9 мс, на этот раз к основной памяти 5 порядков выше 50n. Он выглядел довольно хорошо, но машина на 500 человек может выполнять 500 миллионов инструкций в секунду, потому что инструкция полагается на природу власти, другими словами, впервые выполнить IO, может выполнить 400 000 инструкций, баз данных легко десять важных миллионов и десять Миллион данных, каждый 9 миллисекунд, очевидно, катастрофа.

Для того, чтобы сократить время чтения диска, компьютер сделал некоторую оптимизацию: упреждающее чтение диска. Упреждающее чтение с диска основано на принципе локальности: когда данные используются, данные, находящиеся поблизости, также часто используются немедленно. Таким образом, когда дисковые операции ввода-вывода не только обращаются к текущим данным на диске, но и соседние данные считываются в буфер памяти, потому что принцип локальности говорит нам, что когда компьютер обращается к данным, адрес, когда его соседние данные, скоро будут удалены. доступ.

Длина упреждающего чтения обычно является целым числом, кратным длине страницы. Страница — это логический блок памяти управления компьютером. Аппаратное обеспечение и операционные системы часто делят основную память и дисковую память на последовательные блоки одинакового размера. Каждый блок памяти называется страницей (во многих операционных системах размер страницы обычно равен 4k), основная память и диск обмениваются данными в единицах страниц.

Сказав все это, позвольте мне резюмировать:

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

3.2 Эффективность поиска B-/B+

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

В соответствии с определением B-дерева можно знать, что для извлечения за один раз необходимо получить доступ не более чем к узлам h (высота h деревьев). Поиск в B-Tree требует не более h-1 операций ввода-вывода (корневой узел находится в памяти), а асимптотическая сложность составляет O(h)=O(logdN). В общих практических приложениях исходящая степень d представляет собой очень большое число, обычно более 100, поэтому h очень мало (обычно не более 3). Поэтому эффективность B-Tree как индекса очень высока, что намного выше, чем у сбалансированного бинарного дерева и красно-черного дерева, потому что h этих деревьев, как правило, глубже.

Наглядная схема дерева B+ прилагается ниже:

Дерево B+ больше подходит в качестве структуры данных дискового индекса, чем B-дерево, потому что внутренние узлы дерева B+ не хранят данные, и чем больше степень исхода d внутреннего узла, тем меньше асимптотическая сложность. Верхний предел исходящей степени d зависит от размера ключа и данных в узле:dmax=floor(pagesize/(keysize+datasize+pointsize))

Как правило, 3-уровневое дерево B+ может хранить миллионы данных, то есть для чтения миллионов данных требуется только 3 дисковых ввода-вывода.Можно видеть, что эта эффективность значительно повышается. Если индекса нет, каждый раз, когда запрашивается элемент данных, требуются операции ввода-вывода, миллионы раз, что ужасно.

4. Принцип индексной реализации разных движков

4.1 Реализация индекса MyIsam

Индекс MyISAM реализован на дереве B +. Индекс myiasam разделен от данных, а данные узела листьев обращаются к адресу данных. Примерная диаграмма индекса первичного ключа следующим образом:

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

Реализация вторичного индекса MyIASM ничем не отличается от индекса первичного ключа, как показано ниже:

Отдельно стоит отличить его от InnoDB позже.

4.2 Реализация индекса InnoDB

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

Такой индекс называется кластерным индексом. Поскольку файлы данных InnoDB агрегируются по первичному ключу, InnoDB требует, чтобы таблица имела первичный ключ (MyISAM может не иметь его).Если он не указан явно, система MySQL автоматически выберет столбец, который может однозначно идентифицировать запись данных в качестве первичного ключа.Если он не существует Для этого типа столбца MySQL автоматически генерирует неявное поле в качестве первичного ключа для таблицы InnoDB.Длина этого поля составляет 6 байтов, а тип - long.

第二个区别就是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。 Другими словами, все вторичные индексы в InnoDB относятся к первичному ключу как к полю данных. Как показано ниже:

4.3 Значение

Понимание принципов реализации различных движков очень полезно для ежедневного проектирования баз данных.

1. Поиск по вторичному индексу InnoDB должен извлекать индекс дважды: сначала вторичный индекс извлекается для получения первичного ключа, а затем первичный ключ используется для извлечения записей в первичном индексе, поэтому мы можем понять, почему не рекомендуется используйте слишком длинное поле в качестве первичного ключа, поскольку все вторичные индексы ссылаются на первичный индекс, слишком длинный первичный индекс сделает вторичный индекс слишком большим.
2. Не рекомендуется использовать немонотонные поля в качестве первичного ключа InnoDB, потому что файл данных InnoDB сам по себе представляет собой B+Tree, а немонотонный первичный ключ приведет к тому, что файл данных будет часто разбиваться и корректироваться, чтобы поддерживать характеристики B+Tree при вставке новых записей. , очень неэффективно, поэтому обычно используйте поле автоинкремента в качестве первичного ключа.

Давайте сначала перейдем сюда, а следующий резюмирует стратегию оптимизации индекса.

Ссылаться на:

 1. http://blog.codinglabs.org/articles/theory-of-mysql-index.html
 2. 算法导论（第三版）

Более захватывающие статьи, пожалуйста, обратите внимание на общественные числа: «Heaven Cheng-Talk Technology».