Индексы имеют решающее значение для хорошей производительности базы данных. Всякий раз, когда речь идет об оптимизации производительности базы данных, первое, что приходит на ум, это «индекс», чтобы увидеть, добавлен ли индекс в таблицу. Когда объем данных в таблице становится все больше и больше, особенно заметно влияние индексов на производительность. Когда объем данных невелик и нагрузка невелика, влияние отсутствия индексирования или неправильного индексирования на производительность может быть неочевидным, но когда объем данных постепенно увеличивается, производительность резко падает.

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

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

показатель(Index) — это структура данных, которая помогает MySQL эффективно получать данные, а также структура данных, используемая подсистемой хранения для быстрого поиска записей.

Чтобы понять, как работают индексы в MySQL, самым простым примером является просмотр раздела «Индексы» в оглавлении книги. Если мы хотим найти определенную главу в книге, мы обычно сначала смотрим на оглавление «указатель» книги, и мы сразу же находим соответствующий номер страницы.

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

Запрос является наиболее часто используемой операцией в базе данных.Мы все надеемся, что скорость запроса будет максимально возможной, поэтому разработчик системы базы данных оптимизирует ее с точки зрения алгоритма запроса. Конечно, самый простой алгоритм запросаПоследовательный поиск, но сложность этого алгоритма составляет O(n), что очень плохо при большом количестве данных. Например, в пользовательской таблице t_user есть следующие данные: если вы хотите запросить людей в возрасте 89 лет, если вы ищете по порядку, вам нужно просмотреть строку за строкой, что показывает, насколько низка эффективность запроса ( чем больше число, тем более неравномерным будет распределение данных, это займет больше времени).

mysql> select * from t_user;
+----+----------+-----+
| id | name     | age |
+----+----------+-----+
|  1 | xcbeyond |  22 |
|  2 | jack     |  34 |
|  3 | tom      |  77 |
|  4 | kitty    |   5 |
|  5 | make     |  91 |
|  6 | Mickey   |  23 |
|  7 | Andy     |  89 |
+----+----------+-----+
7 rows in set

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

Чтобы лучше понять индекс, следующий рисунок основан на таблицеt_userДанные в , показывающие один из возможных способов индексации.

Слева данные в таблице, всего 7 записей, для ускоренияageПоиск по столбцу поддерживает двоичное дерево поиска, показанное справа, каждый узел содержит значение ключа индекса и указатель на соответствующую запись данных, так что соответствующие данные можно быстро найти с помощью двоичного поиска, а время сложно.O(log2 N).

Однако в реальных базах данных такие бинарные деревья поиска редко реализуются (поскольку бинарные деревья поиска имеют требования к данным), но принцип аналогичен этому.

Во-вторых, индексная операция

Прежде чем официально представить индексы, давайте посмотрим, как MySQL создает индексы, перестраивает индексы, запрашивает индексы и удаляет индексы для последующего использования. (Коллекцию рекомендуется сохранять отдельно)

1. Создайте индекс

Создание индекса может быть выполнено вCREATE TABLEутверждение, также может использоваться отдельноCREATE INDEXилиALTER TABLEчтобы добавить индекс к таблице.

грамматика:

CREATE [UNIQUE/FULLTEXT] INDEX <索引名> ON <表名>(<列名>)

ALTER TABLE <表名> ADD INDEX|UNIQUE|PRIMARY KEY|FULLTEXT <索引名>(<列名>)

Среди них при создании индекса можно указать тип индекса: индекс первичного ключа (PRIMARY KEY), уникальный индекс (UNIQUE), полнотекстовый индекс (FULLTEXT), обычный индекс (INDEX).

Например:

1) Занять столindex_testНапример, сначала создайте обычную таблицуindex_test:

(При создании таблицы вы также можете создать индекс напрямую. Здесь, чтобы объяснить создание индекса, индекс создается отдельно)

mysql> create table index_test(id int,ch varchar(32));
Query OK, 0 rows affected

2) для столаindex_testСоздайте индекс отдельно:

mysql> create index idx on index_test(id);
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

или

mysql> alter table index_test add index idx(id);
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

2. Восстановите индекс

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

Перестройте индекс, по существу восстановив таблицу.

Например:

mysql> repair table index_test quick;
+-----------------+--------+----------+---------------------------------------------------------+
| Table           | Op     | Msg_type | Msg_text                                                |
+-----------------+--------+----------+---------------------------------------------------------+
| test.index_test | repair | note     | The storage engine for the table doesn't support repair |
+-----------------+--------+----------+---------------------------------------------------------+
1 row in set

3. Индекс запроса

Иногда, чтобы проверить, есть ли у таблицы индекс и каков индекс, нужно передать командуshow index from|in table_nameдля просмотра индекса.

грамматика:

SHOW INDEX FROM|IN <表名>

Например:

mysql> show index from index_test;
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table      | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| index_test |          1 | idx      |            1 | id          | A         |           0 | NULL     | NULL   | YES  | BTREE      |         |               |
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set

Если вы будете внимательны, то можете увидеть поля в результатах запросаindex_typeзначениеBTREE, о чем пойдет речь дальшеB Treeиндекс, который также может быть известен с другой стороныInnoDBТип индекса по умолчаниюB Tree.

4. Удалить индекс

Чтобы удалить индекс, вы можете использоватьDROP INDEXилиALTER TABLEзаявление для достижения.

грамматика:

DROP INDEX <索引名> ON <表名>

ALTER TABLE <表名> DROP INDEX <索引名>

Например:

mysql> drop index idx on index_test;
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

или

mysql> alter table index_test drop index idx;
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

3. Тип индекса

Существует много типов индексов, которые могут обеспечить более высокую производительность для различных сценариев. В MySQL,Индексация реализована на уровне механизма хранения., поэтому единого стандарта индексации не существует:Индексы разных механизмов хранения работают по-разному., и не все механизмы хранения поддерживают все типы индексов.

Отделено от структуры хранения:

• Индекс BTree (индекс B-Tree или B+Tree)
• хэш-индекс
• Полнотекстовый индекс (full-index)

На прикладном уровне его можно разделить на:

• Обычный индекс: то есть индекс содержит только один столбец, а таблица может иметь несколько индексов с одним столбцом.
• Уникальный индекс: значение индексируемого столбца должно быть уникальным, но допускаются нулевые значения.
• Составной индекс: то есть индекс содержит несколько столбцов.

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

Механизм хранения MySQL по умолчанию:Innodb, поддерживается только явноB-TreeИндексы для часто используемых таблиц,InnodbАдаптивный хеш-индекс будет устанавливаться прозрачно, то есть хэш-индекс будет устанавливаться на основе индекса B-дерева, что может значительно повысить эффективность поиска, и является прозрачным, неконтролируемым и неявным для клиента.

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

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

B для баланса (balance), а не двоичный (binary), потому что B-дерево развилось из самого раннего сбалансированного бинарного дерева.

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

Когда система считывает данные с диска в память, она использует дисковые блоки (block) в качестве базовой единицы данные, расположенные в одном и том же блоке диска, будут считаны за один раз, а не то, что нужно извлечь.

InnoDBВ движке хранилища есть страницы (Page), страница — это наименьшая единица управления диском.InnoDBРазмер по умолчанию каждой страницы в механизме хранения16KB, через параметрinnodb_page_sizeУстановите размер страницы на4K、8K、16K, в MySQL вы можете просмотреть размер страницы с помощью следующей команды:

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set

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

B-дерево определяет записи данных как два кортежа [ключ, данные]:

• keyЭто первичный ключ записи, то есть значение первичного ключа в таблице, которое используется для записи уникальной строки данных, а значение ключа уникально и отличается друг от друга.

• dataДанные, отличные от первичного ключа в строке записей.

деревоmB-дерево порядка обладает следующими свойствами:

• Каждый узел имеет не более m потомков.
• За исключением корневого узла и конечных узлов, каждый другой узел имеет по крайней мереceil(m/2)ребенок.
• Если корневой узел не является конечным узлом, он должен иметь как минимум 2 дочерних узла.
• Все конечные узлы находятся в одном слое и не содержат другой ключевой информации.
• Каждый нетерминальный узел содержит информацию о n ключевых словах (p0,p1,...pn,k1,...kn)
• Количество n ключевых слов удовлетворяет:ceil(m/2)-1 <= n <= m-1
• ki(i=1,…n)является ключевым словом, и ключевые слова отсортированы в порядке возрастания.
• pi(i=1,…n)является указателем на дочерний узел.p(i-1)все ключи узлов указанного поддерева меньше, чемki, но оба больше, чемk(i-1).

Примечание:ceil()является функцией округления.

Каждый узел в B-Tree может содержать большое количество ключевых значений в зависимости от реальной ситуации.key,данныеdataи указательp. На следующем рисунке показана структура индекса B-дерева 3-го порядка:

Каждый узел занимает место в одном блоке диска, и на одном узле есть два ключа в порядке возрастания.keyи три указателя на дочерние узлыp, указатель хранит адрес блока диска, на котором расположен дочерний узел. два ключевых словаkeyРазделен на три указателя, соответствующие трем полям области видимости.pи указывает на область видимости данных дочернего узла. Возьмите корневой узел в качестве примера, ключевое слово17а также35,p1Диапазон данных дочернего узла, на который указывает указатель, меньше17,p2Диапазон данных дочернего узла, на который указывает указатель, равен17~35,p3Диапазон данных дочернего узла, на который указывает указатель, больше, чем35.

Моделируемое ключевое слово поиска29Процесс строки данных:

1. Найдите блок диска 1 в соответствии с корневым узлом и прочитайте его в память. [Дисковый ввод-вывод в первый раз]

2. Сравните ключевые слова29в интервале（17,35）, найти указатель на блок диска 1p2.

3. согласно сp2Указатель находит дисковый блок 3 и считывает его в память. [Дисковый ввод-вывод 2-й раз]

4. Сравните ключевые слова29в интервале（26,30）, найти указатель на дисковый блок 3p2.

5. Найдите дисковый блок 8 по указателю `p2' и прочитайте его в память. [3-й дисковый ввод-вывод]

6. Найдите ключевое слово в списке ключевых слов в блоке диска 8.29.

Проанализируйте описанный выше процесс и найдите потребность3вторичный дискI/Oоперация, и3операция поиска в памяти. из-за ключевых слов в памятиkeyЭто упорядоченная структура таблицы, которая может использовать бинарный поиск для повышения эффективности. а также3вторичный дискI/OОперация является определяющим фактором, влияющим на эффективность всего поиска B-Tree.B-TreeотносительноAVLTree(Высоко сбалансированное бинарное дерево) уменьшает количество узлов, так что каждый дискI/OДанные, загруженные в память, сыграли свою роль, тем самым повысив эффективность запросов.

2. Индекс B+дерева

B+TreeвB-TreeОптимизация, основанная на этом, делает его более подходящим для реализации структуры индекса хранения,InnoDBМеханизм хранения должен использоватьB+TreeРеализуйте его индексную структуру.

из предыдущего разделаB-TreeНа структурной схеме видно, что каждый узел содержит не только данныеkeyзначение иdataстоимость. И место для хранения каждой страницы ограничено, еслиdataКогда объем данных велик, каждый узел (т. е. страница) будет хранить болееkeyСумма очень мала, и когда объем хранимых данных велик, это также вызоветB-TreeГлубина больше, и диск при запросе увеличен.I/OКоличество раз, что в свою очередь влияет на эффективность запроса. существуетB+Tree, все узлы записи данных хранятся на конечных узлах того же слоя в порядке размера значения ключа, а не только на конечных узлах.keyценная информация, которая может значительно увеличить емкость хранения каждого узлаkeyколичество значений, убывающееB+Treeвысота.

B+TreeотносительноB-TreeЕсть несколько отличий:

• Нелистовые узлы хранят только информацию о ключе-значении.

• Между всеми листовыми узлами есть цепной указатель.

• Записи данных хранятся в листовых узлах.

из предыдущего разделаB-Treeбыть оптимизированным, потому чтоB+TreeНелистовой узел хранит только информацию о значении ключа.Предполагая, что каждый блок диска может хранить 4 значения ключа и информацию об указателе, он становитсяB+TreeТогда его структура показана на следующем рисунке:

обычно вB+TreeЕсть два указателя на голову, один указывает на корневой узел, другой указывает на конечный узел с наименьшим ключевым словом, и между всеми конечными узлами (т. е. узлами данных) существует кольцевая структура. Следовательно, это может бытьB+TreeВыполняются две операции поиска: одна — поиск по диапазону и поиск по страницам для первичного ключа, а другая — случайный поиск, начиная с корневого узла.

Может быть, в приведенном выше примере всего 22 записи данных, я этого не вижу.B+TreeПреимущества, сделать расчет следующим образом:

InnoDBРазмер страницы в механизме хранения16KB, тип первичного ключа общей таблицы:INT(занимает 4 байта) илиBIGINT(занимает 8 байт), тип указателя также обычно 4 или 8 байт, то есть страница (B+Treeузел в ) примерно хранится в16KB/(8B+8B)=1KКлючевое значение (поскольку это оценка, для удобства расчета значение K здесь равно10^3). То есть глубина 3B+TreeИндекс может поддерживаться10^3 * 10^3 * 10^3 = 10亿 Рекорды.

На практике каждый узел может быть заполнен не полностью, поэтому в базе данных высота B+Tree обычно составляет 2–4 слоя. MySQLInnoDBПри разработке механизма хранения корневой узел находится в памяти, то есть при поиске записи строки с определенным значением ключа ему требуется не более1~3Операции ввода-вывода на вторичном диске.

3. Хэш-индекс

хэш-индекс (hash index),Дана основе хеш-таблицы. Для каждой строки данных механизм хранения вычисляет хеш-значение для всех индексированных столбцов (hash value), хеш-значения, рассчитанные для строк с разными значениями ключа, тоже разные. Хэш-индекс хранит все хэш-значения в индексе, сохраняя при этом указатель на каждую строку данных в хеш-таблице.

Только в MySQLMemoryДвижок показывает поддержку хэш-индексов, и хэш-индексы такжеMemoryТип индекса по умолчанию для механизма хранения,а такжеMemoryМеханизм хранения также поддерживаетB-Treeпоказатель.

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

продолжить с таблицейt_userПримеры данных вnameУстановите хэш-индекс. Предположим, что хеш-функция, используемая индексом,f(), то рассчитанное хэш-значение (все данные примера, а не реальные данные):

f('xcbeyond')=2390

f('jack')=4010

f('tom')=5178

f('kitty')=1067

f('make')=7901

f('Mickey')=3079

f('Andy')=8301

Вычисленное хеш-значение будет указывать на данные соответствующей строки данных, а отношение указания будет следующим:

Выполните следующий запрос, и соответствующие данные могут быть запрошены.

mysql> select * from t_user where name = 'xcbeyond';
+----+----------+-----+
| id | name     | age |
+----+----------+-----+
|  1 | xcbeyond |  22 |
+----+----------+-----+
1 row in set

Рассчитать сначалаxcbeyondХэш-значение и найти соответствующую строку данных в соответствии с хэш-значением.f('xcbeyond')=2390, поэтому MySQL ищет в индексе2390, и найдите строку данных, которая указывает на строку 1, затем сравните, равно ли значение строки 1xcbeyond, чтобы обеспечить точность найденных данных.

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

• Данные хэш-индекса не хранятся в порядке значений индекса, поэтому их нельзя использовать для сортировки.
• Хэш-индексы не поддерживают поиск частичного совпадения столбцов индекса., потому что хеш-индексы всегда используют все содержимое индексированного столбца для вычисления хеш-значения. Например, если для обоих столбцов данных (A, B) установлен хэш-индекс, если в запросе есть только столбец данных A, индекс нельзя использовать.
• Хэш-индексы поддерживают только равные запросы сравнения,включать=,in(),Не поддерживает любой диапазон, нечеткий поиск,Например,where age > 20,where name like '%xc%'.
• Если имеется много коллизий хэшей, подсистема хранения должна поддерживать связанные списки.Стоимость операций по поддержанию этих связанных списков будет очень высокой, а производительность запросов будет очень низкой.

4. Полнотекстовое индексирование

Полнотекстовый индекс — это специальный тип индекса,Ищет ключевые слова в тексте вместо сравнения значений в индексе.

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

Нет конфликта между созданием полнотекстового индекса и индекса B-Tree на основе значений для одного и того же столбца.Полнотекстовое индексирование подходит для операций полнотекстового нечеткого поиска (MATCH AGAINST), а не для обычных условных операций..

В-четвертых, преимущества индексации

Индекс позволяет серверу MySQL быстро найти указанную позицию таблицы, но это не единственная функция индекса.Как видно на данный момент, в зависимости от структуры данных индекса, индекс также имеет некоторые другие дополнительные функции.

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

• Индексы значительно сокращают объем данных, которые сервер MySQL должен сканировать. (полное сканирование таблицы)
• Индексы помогают серверу MySQL избежать сортировки и временных таблиц.
• Индексы могут превратить случайный ввод-вывод в последовательный ввод-вывод.

Является ли индексация лучшим решением?

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

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

Справочная статья:

1. woowoooo.brief.com/afraid/67 с 63777…
2. cloud.Tencent.com/developer/ ах…