Индексы могут быть пугающими для многих людей.В конце концов, индексы MySQL необходимо спрашивать на каждом собеседовании.Даже если собеседование откладывается в первую очередь, в обычной разработке оптимизация SQL является главным приоритетом.
Не будет преувеличением сказать, что качество SQL в системе может напрямую определять скорость вашей системы. Но задумывались ли вы над вопросом перед оптимизацией? То есть: каков принцип нашей оптимизации? Какова теоретическая основа оптимизации SQL?
Хотя и говорят, что практика приносит истинное знание, я считаю, что теория является фундаментом, поддерживающим практику, потому что мы не можем слепо практиковать без цели, потому что это часто приводит к удвоенному результату при половинном усилии.
Итак, сказав так много, я просто хочу сказать вам, что прежде чем мы действительно начнем оптимизацию индекса, нам нужно полностью понять принцип индексации. Если вы будете говорить об оптимизации таким образом, вы почувствуете себя более плавно~
1. Характер индекса
Суть индекса — это отсортированная структура данных. Я считаю, что это знакомо не всем, потому что, когда дело доходит до индексации, многие люди, естественно, думают о каталоге в словаре.
Да, эта аналогия очень яркая, но если углубиться, то боюсь, что многие друзья немного потеряют дар речи.Теперь, когда вы уже знаете суть индекса, значит, у вас уже есть основа для прочтения этой статьи. , Я верю, что у вас, прочитавших текст, появится новое понимание принципа индексации.
2. Классификация индексов
В базе данных есть много типов индексов (не думайте, что индексы — это только деревья B+, потому что мы обычно используем MySQL). И разные типы, очевидно, предназначены для разных случаев, так какие типы индексов существуют? Давайте подробнее рассмотрим ниже.
2.1, Хэш-индекс
Хэш-индекс является относительно распространенным индексом, его эффективность запроса одной записи очень высока, а временная сложность равна 1. Однако хеш-индекс не является наиболее часто используемым типом индекса базы данных, особенно наш часто используемый механизм Mysql Innodb не поддерживает хэш-индекс. В основном по следующим причинам:
- Хэш-индекс подходит для точного поиска, но не подходит для поиска по диапазону.
- Поскольку подсистема хранения будет вычислять хэш-код для каждой строки, хэш-коды относительно малы, а хэш-коды разных строк «ключ-значение» обычно различаются, хэш-код хранится в хэш-индексе, а хэш-коды не между собой Обычные и хеш-операции не гарантируют порядок, поэтому два данных с одинаковыми значениями, хеш-значение которых сильно различается, делятся на разные сегменты. Вот почему хэш-индекс может выполнять только запросы на постоянное сопоставление, потому что только таким образом хэш-код может сопоставить данные.
Для хэш-индексов друзьям нужно только здесь разобраться.
2.2, бинарное дерево
Кроме того, структура данных, используемая в обычных индексах, является древовидной.Во-первых, давайте представим самое классическое двоичное дерево.
Давайте сначала представим характеристики бинарного дерева:
-
- Временная сложность бинарного дерева O (n)
-
- У узла может быть только два дочерних узла. то есть не более 2 градусов
-
- Левый дочерний узел меньше этого узла, правый дочерний узел больше этого узла
Во-первых, давайте посмотрим, как выглядит бинарное дерево.
Но в крайнем случае будет цепочка, то есть узлы увеличивались с одной стороны. Как показано ниже
В бинарном дереве есть особая структура - сбалансированное бинарное дерево, характеристики сбалансированного бинарного дерева:
-
- Корневой узел будет меняться по мере изменения данных
-
- Чем больше данных, тем больше время обхода, больше времени ввода-вывода и тем медленнее (дисковый ввод-вывод определяется высотой дерева)
2.4, дерево Б (два или три дерева)
Разобравшись с бинарным деревом, мы можем поговорить о том, что такое B-дерево. B-дерево выглядит так:
Из схемы структуры B-дерева видно, что каждый узел содержит не только значение ключа данных, но и значение данных.
Место для хранения каждой страницы ограничено.Если данные относительно велики, это приведет к меньшему объему хранения ключей каждого узла.Когда объем данных велик, B-дерево также будет очень глубоким, тем самым увеличивая количество дисковых операций ввода-вывода, что влияет на эффективность запросов.
Ну, сказав это, типы общих индексов также закончены.Вышеприведенный контент используется только как предзнаменование.Давайте официально начнем дерево B+ MySQL.
2.5, дерево В+
Наиболее часто используемой структурой данных индекса в MySQL является дерево B+, которое имеет следующие характеристики:
- В дереве B+ все узлы записи данных хранятся на листовых узлах того же слоя в соответствии с размером значения ключа, в то время как нелистовые узлы хранят только ключевую информацию, что может значительно уменьшить количество ключей, хранящихся в каждом узле. , Уменьшить высоту дерева B+
- Ключевые слова дочерних узлов дерева B+ расположены в порядке от меньшего к большему, а конечные данные слева сохранят указатель начальных данных узла справа.
- Дерево B+ имеет меньше уровней: по сравнению с деревом B, B+ хранит больше ключевых слов на неконечный узел, а дерево имеет меньше уровней, поэтому запросы данных выполняются быстрее.
- Скорость запроса дерева B+ более стабильна: все адреса данных ключевых слов B+ хранятся на листовых узлах, поэтому количество раз каждого поиска одинаково, поэтому скорость запроса более стабильна, чем у дерева B;
- Дерево B+ имеет естественную функцию сортировки: все данные конечных узлов дерева B+ образуют упорядоченный связанный список, что более удобно при запросе данных в диапазоне размеров, данные очень компактны, а частота попаданий в кэш будет выше. чем у дерева Б.
- Обход полного узла дерева B+ выполняется быстрее: дерево B+ обходит все дерево только для того, чтобы пройти все конечные узлы, вместо необходимости обхода каждого слоя, такого как дерево B, что выгодно для базы данных при полном сканировании таблицы.
Что ж, после разговора о характеристиках очень многих B+-деревьев, давайте сфотографируем, чтобы посмотреть, как выглядит B+-дерево (если вы не понимаете, не беда, ниже будет объяснено пошагово)
Приведенная выше страница данных - это место, где собственно хранится страница данных, а страницы данных связаны двусвязным списком.Ну, здесь мы быстро разберемся в типах каждого индекса, а затем приступим к формальному анализу Дерево В+. .
3. Каталог первичного ключа
Мы вынимаем страницу данных на картинке выше, а затем уточняем ее, она становится картинкой ниже
Мы все знаем, что когда MySQL хранит данные, они основаны настраница данных— наименьшая единица, а хранение данных на странице данных —непрерывныйДа, данные на странице данных сортируются по первичному ключу (первичный ключ не сортируется по ROW_ID, поддерживаемому самой MySQL), а страница данных и страница данных связаныДвусвязный списокдолжны быть связаны, данные и время данныхОдносвязный списокбыть связанным.
То есть на каждой странице данных он должен иметь минимальный первичный ключ, и тогда номер страницы каждой страницы данных и минимальный первичный ключ образуюткаталог первичного ключа(Как и в левой части рисунка выше), предположим, что вы хотите найти данные с первичным ключом 2 сейчас и, наконец, определить, что запись с первичным ключом 2 находится на странице данных 1 с помощью метода двоичного поиска, затем вы найдете страницу данных 1, а затем Чтобы найти запись, первичный ключ которой равен 2, нам нужно сначала узнать общий процесс и не вдаваться в подробности. Давайте сначала посмотрим на принцип структуры с точки зрения макросов , а затем к принципу реализации микропредставления.
То, что я только что сказал выше, на самом деле можно понимать как индекс первичного ключа, а индекс первичного ключа также является самым простым и основным индексом. В настоящее время все должны знать, почему вы можете ускорить запрос первичного ключа, верно?
4. Индексная страница
Но теперь предположим, что существует много-много страниц данных, будет ли соответствующий каталог первичного ключа очень большим?
Что, если есть 10 миллионов записей, 50 миллионов записей? Правда ли, что даже если это бинарный поиск, его эффективность все равно очень низкая, поэтому для решения этой проблемы MySQL разработал новую структуру хранения —индексная страница.例如有下面这样情况，
Предполагая, что в указанном выше каталоге первичного ключа есть много записей, приведенная выше структура превратилась в эту, MySQL разделит записи на разные индексные страницы, что выглядит следующим образом.
Страница индекса записывает номер страницы каждой страницы данных и запись наименьшего первичного ключа на странице данных, то есть наименьший первичный ключ и номер страницы данных не просто сохраняются в каталоге первичного ключа, а эволюционируют в страница индекса. Страница индекса аналогична странице данных, если одной страницы недостаточно, она будет разделена на следующую страницу.
Если вы хотите найти эту запись с id=20 сейчас, а? Итак, на какой странице индекса мне искать эту запись? Поэтому в это время определенно необходимо поддерживать индексную страницу.
Верно, MySQL также спроектирован таким образом, то есть MySQL также разработал структуру данных для обслуживания индексных страниц, которая также называетсяиндексная страница, но они находятся на разных уровнях, например:
то естьСтраницы индекса, которые поддерживают страницы индексав реалеСтраницы индекса, на которых хранятся записи и страницы данныхПредыдущий слой, теперь если вы хотите найти эту запись с id=20, то есть начать поиск с верхней страницы индекса, и через бинарный поиск вы можете быстро найти запись с id=20 s находится в индексе On страница 2, затем перейдите на страницу индекса 2, чтобы найти, а затем она такая же, как и раньше (обратите внимание, что записи на странице индекса также связаны через односвязный список), по каждому наименьшему первичному ключу можно найти id= 20 находится в данных на странице 5, предположим, что страница данных 5 выглядит так
На данный момент, можете ли вы выяснить, как расположены данные?
5. Наслоение индексных страниц
Итак, поскольку вы уже знаете, что слишком много индексных страниц будет распространяться на верхний уровень, теперь предположим, что на верхнем уровне слишком много индексных страниц, что нам делать? Это очень просто, продолжайте разделяться и переходите на следующий уровень, ничего лишнего, я нарисую картинку, чтобы вы поняли
Я вижу, ты видишь? Смоделируем процесс поиска, допустим, вы хотите найти запись 37. Честно говоря, я вообще не знаю, где эта запись. Хорошо, теперь давайте смоделируем процесс поиска MySQL, сначала изиндексная страница верхнего уровняНачать поиск, так как id=37, поэтому он находит страницу 16 индекса, а затем продолжает поиск на странице 16 индекса. В это время он также может найти id=37 на странице 3 индекса, затем продолжить поиск и, наконец, может найти реальные данные. Предположим, что на странице 8 страница данных 8 выглядит так
Это идеально? Если мне нужно завершить приведенное выше изображение, то.... брат должен (рисунок слишком большой, структура связанного списка данных на странице индекса не будет отображаться)
В это время вы были остроумны и открыли какие-нибудь маленькие секреты? Он похож на бинарное дерево? По сути, это структура B+-дерева, которая также является физической структурой реальных данных, хранящихся на диске. Каковы свойства дерева B+? Дерево B+ также является типом двоичного дерева поиска, но его данные хранятся только в листовых узлах (здесь страницы данных), напримериндексная страница + страница данныхСкомпонованное B+-деревокластеризованный индекс(Это предложение очень важно).
Кластерный индекс создается MySQL на основе структуры индекса первичного ключа.
6. Индекс непервичного ключа
Но теперь проблема возникает снова, так как акцент здесьиндекс первичного ключаЗатем мы обычно развиваем много других индексов в дополнение к другим показателям, что я должен делать, когда? Предположим, вы сейчасname,ageСоздайте индекс. Оглядываясь назад на индекс первичного ключа, необходимо ли поддерживать дерево B+ на основе порядка первичных ключей при вставке данных?
На самом деле принцип непервичного ключевого индекса тот же.MySQL поддерживает дерево B+.Говоря грубо говоря,сколько индексов вы создадите,MySQL поможет вам поддерживать столько же деревьев B+.Почему я не могу построить тоже много индексов?Я знал раньше, что не могу построить слишком много индексов, потому что индексы также занимают место, что на самом деле является основной причиной)
Если это правда сейчасname+ageЧтобы построить индекс, что хранится в это время? В настоящее время MySQL поддерживает отдельную древовидную структуру B+ в соответствии с именем и возрастом, и данные по-прежнему хранятся на странице данных, но каждая запись в исходных данных записывается с id=xx, а теперь она записывается с именем =xx , age=xx, id=xx, несмотря ни на что, первичный ключ обязательно сохранится, давайте сначала сфотографируем
При вставке данных MySQL сначала сортирует данные по имени. Если имя такое же, сортировка выполняется по возрасту в объединенном индексе. Если оно не изменилось, выполняется сортировка по полю первичного ключа. Принцип вставки такой.
В настоящее время записи на каждой странице данных фактически хранятся виндексное полеи поле первичного ключа, а других полей нет (почему бы и нет? Хранить везде одни и те же данные пустая трата места, да и не нужно, поэтому будет следующая оптимизация индекса), что касается поиска, принцип и обработайте с помощью кластеризованного индекса Опять же, я не буду повторять их здесь, но важно следующее: Предположим, вы теперь выполняете этот SQL:
SELECT name FROM student WHERE name='wx'
Тогда запрос в это время совершенен, индекс используется и не нужноформа возврата
7. Вернуться к столу
Это так, теперь нам нужно найти запись по имени, а поле запроса (то есть поле запроса после выбора) имеет только имя (пока оно находится в трех полях имя, возраст и id) В это время можно напрямую получить окончательную запись
Другими словами, поскольку записи в объединенном индексе содержат только имя, возраст и идентификатор, если запрашиваются только эти три поля, то желаемый результат может быть запрошен в дереве B+.
Теперь предположим, что запрос SQL такой (мы предполагаем, что в студенте есть другие поля, кроме имени, возраста, идентификатора)
SELECT * FROM student WHERE name='wx'
Теперь все кончено, потому что, хотя вы можете быстро найти запись по имени, но поскольку имя + возраст не является кластеризованным индексом, страница данных дерева B + в это время хранит только свой собственный ассоциированный индекс и поле индекса первичного ключа. не хранит другие поля, поэтому другие значения атрибута получить в это время нельзя, что мне делать в это время?
В этом случае MySQL долженформа возвратаосведомился. В это время MySQL снова выполнит поиск по кластеризованному индексу на основе идентификатора в найденной записи, то есть он будет искать в дереве B+ на основе идентификатора, чтобы сохранить идентификатор. Поскольку страница данных в кластеризованном индексе записывает полную запись записи, этот процесс называетсяформа возврата.
Еще раз подчеркните значение следующей таблицы:根据非主键索引查询到的结果并没有查找的字段值，此时就需要再次根据主键从聚簇索引的根节点开始查找，这样再次查找到的记录才是完成的.
Наконец, позвольте мне взглянуть на процесс обслуживания MySQL для индексов, не являющихся первичными ключами:
Для индексов, не являющихся первичными ключами (обычно объединенных индексов), при поддержке дерева B+ он будет оценивать в соответствии с полями объединенного индекса.Предполагая, что объединенный индекс: имя + адрес + возраст, тогда MySQL поддерживает дерево B+ индекса. Если имя одинаковое, оно будет отсортировано по второму адресу. Если адрес совпадает, то оно будет отсортировано по возрасту. Если возраст совпадает, оно будет отсортировано по к значению поля первичного ключа.Индекс непервичного ключа, когда MySQL поддерживает дерево B+, он поддерживает только поле индекса и поле первичного ключа.