Механизмы MySQL MyISAM и InnoDB по умолчанию используют индексы дерева B+ (оба отображаются как «BTREE» при запросе) В этой статье обсуждаются две проблемы:
- Почему основные базы данных, такие как MySQL, выбирают структуру индекса дерева B+?
- Как понять общие идеи оптимизации индекса MySQL на основе структуры индекса?
Почему не все индексы помещаются в память
Выбор структуры индекса основан на таком свойстве:Когда объем данных велик, индекс не может быть полностью загружен в память..
Почему не все индексы помещаются в память? Предполагая, что индекс организован в виде дерева, простая оценка:
- Предполагая, что один индексный узел размером 12 байт, 1000 строк данных и уникальный индекс, листовые узлы занимают в общей сложности около 100 МБ, а все дерево — не более 200 МБ.
- Если предположить, что строка данных занимает 200 байт, данные в сумме занимают около 2 гигабайт.
Предположим, что индекс хранится в памяти. То есть каждый раз, когда 2 ГБ данных сохраняются на физическом диске, они занимают 200 МБ памяти.索引:数据的占用比около 1/10. Соотношение заполняемости 1/10 считается большой проблемой? Физические диски намного дешевле памяти, например, сервер с 16G памяти и 1T жестким диском.Если вы хотите хранить жесткий диск объемом 1 ТБ, вам потребуется не менее 100 ГБ памяти., намного больше, чем 16G.
Учитывая, что в таблице может быть несколько индексов, объединенных индексов и меньшая занятость строк данных, фактический коэффициент заполнения обычно превышает 1/10, а в некоторых случаях может достигать 1/3.В архитектуре хранения на основе индексов索引:数据的占用比слишком высок, поэтому индекс не может полностью поместиться в память.
Другие структурные проблемы
Поскольку он не может поместиться в память, он должен полагаться на дисковое (или SSD) хранилище. Скорость чтения и записи памяти в тысячи раз выше, чем у диска (в зависимости от конкретной реализации), поэтому основная проблема заключается в следующем:Как уменьшить количество операций чтения и записи на диск".
Прежде всего, вне зависимости от механизма таблицы страниц, предполагая, что каждое чтение и запись напрямую проникают на диск, тогда:
- Линейная структура: чтение/запись в среднем O(n) раз
- Двоичное дерево поиска (BST): в среднем O(log2(n)) читает/записывает; наихудшее O(n) читает/записывает, если дерево несбалансировано
- Самобалансирующееся двоичное дерево поиска (AVL): добавлен самобалансирующийся алгоритм на основе BST, а максимальное время чтения/записи составляет O(log2(n))
- Красно-черное дерево (RBT): еще одно самобалансирующееся дерево поиска, максимальное чтение/запись O (log2 (n)) раз.
BST, AVL и RBT оптимизируют количество операций чтения и записи с O (n) до O (log2 (n)). Среди них и AVL, и RBT имеют больше функций самобалансировки, чем BST, что снижает количество операций чтения и записи. до максимума O (log2(n)).
Предполагая, что используется самоинкрементный первичный ключ, сам первичный ключ упорядочен, и количество операций чтения и записи древовидной структуры может быть оптимизировано по высоте дерева.Чем ниже высота дерева, тем меньше число читает и пишет, самобалансировка обеспечивает стабильность древовидной структуры. Если вы хотите провести дальнейшую оптимизацию, вы можете ввести B-дерево и дерево B+.
Какую проблему решает B-дерево?
Во многих статьях B-дерево ошибочно называют B-(минус)-деревом, что может быть неправильным пониманием его английского названия «B-Tree» (более того, B-дерево называется бинарным деревом или бинарным деревом поиска). Особенно при разговоре с B+ деревьями. Считается само собой разумеющимся, что если есть дерево B+ (плюс), то есть дерево B- (минус).На самом деле, английское название дерева B+ — «B+-Tree».
Если отбросить операции обслуживания, то B-дерево похоже на «m-арное дерево поиска» (m — максимальное количество поддеревьев), а временная сложность — O(logm(n)). Тем не менее, B-дерево спроектировано с учетом эффективной и простой операции обслуживания, так что глубина B-дерева поддерживается в пределах примерно между log(ceil(m/2))(n)~logm(n),Значительно уменьшает высоту дерева.
еще раз подчеркнуть:
Не беспокойтесь о временной сложности.В отличие от простых алгоритмов, количество дисковых операций ввода-вывода является более важным фактором. Читатели могут сделать вывод, что временная сложность B-дерева и AVL одинакова, но из-за небольшого количества слоев B-дерева и количества дисковых операций ввода-вывода производительность B-дерева лучше, чем у AVL и других бинарные деревья на практике.
Подобно двоичному дереву поиска, каждый узел хранит несколько ключей и поддеревьев, а поддеревья и ключи расположены по порядку.
Назначение таблицы страниц — расширить память + ускорить чтение и запись на диск. Страница (Page) обычно 4K (равна размеру блока блока данных диска, см. анализ inode и блока).С точки зрения чтения и записи диска операционная система загружает содержимое с диска в память в единицах страниц каждый раз (с точки зрения амортизации).Стоимость поиска), после изменения страницы, а затем записи страницы обратно на диск по необязательному расписанию. Учитывая хороший характер таблицы страниц, размер каждого узла можно сделать примерно равным одной странице (что делает m очень большим), так что каждая загруженная страница может полностью покрыть узел, чтобы можно было выбрать следующий уровень поддерева; Дерево такое же. Для таблицы страниц AVL (или RBT) эквивалентен B-дереву с поддеревьями 1 ключ + 2. Поскольку логически соседние узлы обычно не являются смежными физически, читается страница размером 4 КБ, и на странице нет абсолютно никаких узлов. Большая часть пространства будет недействительными данными.
Предполагая, что указатели узлов ключа и поддерева занимают 4 байта, узел B-дерева является самым большим.m * (4 + 4) = 8m B; Размер страницы 4 КБ. ноm = 4 * 1024 / 8 = 512, B-дерево с 512 ответвлениями, данные 1000 Вт, максимальная глубинаlog(512/2)(10^7) = 3.02 ~= 4. Глубина контрастного бинарного дерева, такого как AVL, равнаlog(2)(10^7) = 23.25 ~= 24, разница более чем в 5 раз. Шок! Глубина индекса B-дерева такова!
Кроме того, B-деревоОчень дружелюбен к принципу локальности. Если ключ относительно мал (например, самоувеличивающийся ключ 4B выше), в дополнение к добавлению таблицы страниц кэш может дополнительно ускорить упреждающее чтение. Так красиво~
Какую проблему решает дерево B+?
Остаточная проблема B-деревьев
Однако, если вы действительно хотите применить его к индексу базы данных, у B-дерева все еще есть некоторые проблемы:
- Ненайденная строка данных
- Не удалось обработать запрос диапазона
Вопрос 1
Записи таблицы данных имеют несколько полей.Недостаточно найти первичный ключ, но также найти строку данных. Есть 3 решения:
- Непосредственно сохраните строку данных (может соответствовать несколько строк), соответствующую ключу в узле.
- Строка данных хранится отдельно, к узлу добавляется поле для определения положения ключа, соответствующего строке данных.
- Измените логику оценки ключа и поддерева, чтобы поддерево было больше или равно предыдущему ключу и меньше следующего ключа, и, наконец, все доступы попадут на конечный узел; конечный узел непосредственно хранит строку данных или положение строки данных.
В схеме 1 строка данных обычно очень большая, и сохранение строки данных уменьшит количество поддеревьев на странице, а также уменьшит m и увеличит высоту дерева. Предполагая, что строка данных занимает 200 байт, указатель на организацию B-дерева можно игнорировать, тогда новыйm = 4 * 1024 / 200 = 20.48 ~= 21, максимальная глубинаlog(21/2)(10^7) ~= 7. Более чем в два раза IO, не считается.
На схеме 2 узел добавляет поле. Предполагая, что это указатель 4B, новыйm = 4 * 1024 / 12 = 341.33 ~= 341, максимальная глубинаlog(341/2)(10^7) = 3.14 ~= 4. Он мало чем отличается от 3 и его можно рассматривать.
Узел m и глубина схемы 3 не изменяются, но временная сложность становится стабильной O(logm(n)). учитывать.
вопрос 2
В реальном бизнесе частота запросов диапазона очень высока, и B-дерево может найти только одну позицию индекса (может соответствовать нескольким строкам), что затрудняет обработку запросов диапазона. Даны 2 варианта:
- Без изменений: при запросе сначала находится левая граница, затем правая граница, а затем DFS (или BFS) проходит узлы между левой и правой границей.
- На основе «Задачи 1-Схема 3», поскольку все строки данных хранятся в конечных узлах, листовые узлы B-дерева также упорядочены, и можно добавить указатель, указывающий на следующий листовой узел текущего листовой узел в порядке первичного ключа. ; При запросе сначала найдите левую границу, затем правую границу, а затем линейно пройдите от левой границы к ограниченной.
На первый взгляд кажется, что схема 1 лучше схемы 2 - временная сложность и постоянные члены одинаковы, и схему 1 менять не нужно. Но не забывайте о принципе локальности.Независимо от того, хранит ли узел строки данных или расположение строк данных, преимущество схемы 2 заключается в том, что конечные узлы хранятся непрерывно, что удобно для таблиц страниц и кэшей. Схема 1, с другой стороны, сталкивается с недостатками логически смежных узлов и физического разделения.
Вывести B+ дерево
Таким образом, решение 2 задачи 1 и решение 1 задачи 2 могут быть интегрированы в одно решение (индекс на основе B-дерева), а решение 3 задачи 1 и решение 2 задачи 2 могут быть объединены в одно решение (B+). древовидный индекс). На самом деле некоторые базы данных и файловые системы используют B-деревья, а некоторые — B+.
По причинам, которые некоторые обезьяны еще не понимают, Большинство основных баз данных, включая MySQL, выбирают деревья B+. который:
Основные изменения описаны выше:
- Измените логику организации ключей и поддеревьев и назначьте доступ к индексу для конечных узлов.
- Строка конечных узлов по порядку (удобно для запросов диапазона)
Процесс добавления, удаления и проверки B-дерева и B+ дерева
Процесс добавления и удаления B-дерева может временно относиться кОт дерева B, дерева B+, дерева B* к дереву RВ подразделе "6. Вставка и удаление B-дерева" добавление и удаление B+ дерева выполняется одинаково. Я не буду здесь вдаваться в подробности.
Оптимизация индекса MySQL
В соответствии с природой дерева B+ легко понять различные общие идеи оптимизации индекса MySQL.
Пока не обращайте внимания на различия между разными двигателями.
Предпочитаю использовать ключ автоинкремента в качестве первичного ключа
В предыдущем анализе, предполагая, что в качестве индекса используется самоинкрементный ключ 4B, m может достигать 512, а высота слоя всего 3. Есть два преимущества использования автоинкрементных ключей:
- Самоувеличивающийся ключ обычно представляет собой целочисленный тип, такой как int, и ключ относительно компактен, так что m может быть очень большим, а индекс занимает мало места. Самый крайний пример, если использовать varchar 50B (включая длину), то
m = 4 * 1024 / 54m = 75.85 ~= 76, максимальная глубинаlog(76/2)(10^7) = 4.43 ~= 5, плюс стоимость промаха кэша и сравнения строк, затраты времени значительно возрастают. В то же время, когда ключ увеличивается с 4B до 50B, занимаемое пространство всего дерева индексов также является чрезвычайно ужасающим (если вторичный индекс использует первичный ключ для поиска строк данных, рост пространства будет еще более серьезным). - Природа самоинкремента приводит к тому, что запрос на вставку новых строк данных обязательно попадает в крайний правый угол дерева индексов, а частота разбиения узлов низкая.В идеале дерево индексов может достигать «полного» состояния. Когда индексное дерево заполнено, высота слоя ниже, и частота объединения узлов при удалении узлов также ниже.
Опыт оптимизации:
Однажды Monkey использовала столбец varchar(100) в качестве первичного ключа для хранения containerId. Через 3 или 4 дня база данных 100G была заполнена. Мисс администратор базы данных эвфемистически выразила мне свое презрение в электронном письме. . . После этого столбец автоинкремента был добавлен в качестве первичного ключа, а containerId использовался в качестве уникального вторичного индекса.Эффект оптимизации времени и пространства был весьма значительным.
Соответствие крайнего левого префикса
Индекс может быть простым, состоящим из одного столбца (a), или сложным, состоящим из нескольких столбцов (a, b, c, d), т.е.联合索引. Если это совместный индекс, ключ также состоит из нескольких столбцов. В то же время индекс может использоваться только для определения того, существует ли ключ (равный), и не может быть сопоставлен в дальнейшем при обнаружении запросов диапазона (>,
Если есть индекс (a, b, c, d), условие запросаa = 1 and b = 2 and c > 3 and d = 4, он последовательно попадет в a, b и c в каждом узле и не попадет в d. То есть самый левый принцип сопоставления префиксов.
=, в порядке автоматической оптимизации
Нет необходимости учитывать порядок =, in и т. д. MySQL автоматически оптимизирует порядок этих условий, чтобы соответствовать как можно большему количеству проиндексированных столбцов.
Если есть индекс (a, b, c, d), условие запросаc > 3 and b = 2 and a = 1 and d < 4иa = 1 and c > 3 and b = 2 and d < 4Порядок в порядке, MySQL автоматически оптимизируетa = 1 and b = 2 and c > 3 and d < 4, последовательно нажмите a, b, c.
Столбцы индекса не могут участвовать в вычислениях
Условия запроса с индексированными столбцами, участвующими в расчете, не дружественны к индексу (даже индекс нельзя использовать), напримерfrom_unixtime(create_time) = '2014-05-29'.
Причина очень проста, как найти соответствующий ключ в узле? Если это линейное сканирование, то его нужно каждый раз пересчитывать, а стоимость слишком высока, если это бинарный поиск, необходимо определить соотношение размеров для метода from_unixtime.
Поэтому индексированные столбцы не могут участвовать в вычислении. вышесказанноеfrom_unixtime(create_time) = '2014-05-29'заявление должно быть написано какcreate_time = unix_timestamp('2014-05-29').
Не создавайте новые индексы, если их можно расширить
Если у вас уже есть индекс (a) и вы хотите создать индекс (a, b), попробуйте изменить индекс (a) как индекс (a, b).
Стоимость создания нового индекса легко понять. Если индекс (a) изменен на индекс (a, b), MySQL может напрямую изменить индекс (a, b) в дереве B+ индекса a посредством разделения, слияния и т. д.
Нет необходимости создавать индекс с префиксом отношения включения.
Если у вас уже есть индекс (a, b), вам не нужно создавать индекс (a), но при необходимости вам все равно нужно подумать о создании индекса (b).
Выберите столбцы с высокой степенью дискриминации в качестве индексов
Это легко понять. Например, если пол используется в качестве индекса, индекс может разделить только строки данных размером 1000 w на две части (например, 500 w для мужчин и 500 w для женщин), и индекс практически недействителен.
区分度Формулаcount(distinct <col>) / count(*), указывающая долю неповторяющихся полей. Чем больше доля, тем лучше различение. Степень дискриминации уникального ключа равна 1, в то время как степень дискриминации некоторых статусных и гендерных полей может приближаться к 0 перед лицом больших данных.
Это значение трудно определить.Как правило, требование к полю для соединения больше 0,1, то есть сканируется в среднем 10 записей.
Ссылаться на:
Ссылка на эту статью:Говоря об индексе B-дерева MySQL и оптимизации индекса
автор:обезьяна 007
Источник:monkeysayhi.github.io
Эта статья основана наCreative Commons Attribution-ShareAlike 4.0Выпущено по международному лицензионному соглашению, приветствуется перепечатка, вывод или использование в коммерческих целях, но авторство и ссылка на эту статью должны быть сохранены.