показатель
Официальное определение индекса в MySQL: Индекс — это структура данных, которая помогает MySQL эффективно получать данные.
Мы знаем, что запрос к базе данных является одной из наиболее важных функций базы данных. Мы все надеемся, что скорость запроса данных может быть максимально высокой, поэтому разработчики систем баз данных оптимизируют их с точки зрения алгоритмов запросов. Конечно, самый простой алгоритм запросаПоследовательный поиск(линейный поиск), этот алгоритм со сложностью O(n) заведомо плох при большом количестве данных.К счастью, развитие компьютерных наук предоставило много лучших алгоритмов поиска, таких какбинарный поиск(бинарный поиск),Поиск по бинарному дереву(поиск по бинарному дереву) и т.д. Если вы немного проанализируете его, вы обнаружите, что каждый алгоритм поиска может быть применен только к определенной структуре данных.Например, бинарный поиск требует, чтобы извлеченные данные были упорядочены, а поиск бинарного дерева может применяться только к определенной структуре данных.бинарное дерево поискаОднако сама организационная структура данных не может в полной мере удовлетворять различным структурам данных (например, теоретически невозможно организовать одновременно оба столбца по порядку), поэтому, помимо данных, система баз данных поддерживает еще и определенную алгоритм поиска, который удовлетворяет требованиям структур данных, которые каким-то образом ссылаются на данные (указывают на них), чтобы к этим структурам данных можно было реализовать расширенные алгоритмы поиска. Эта структура данных является индексом.
См. пример:
На рис. 1 показан один из возможных подходов к индексации. Слева находится таблица данных с двумя столбцами и семью записями. Крайний левый — физический адрес записи данных (обратите внимание, что логически смежные записи не обязательно физически соседствуют на диске). Чтобы ускорить поиск Col2, можно поддерживать двоичное дерево поиска, показанное справа, каждый узел содержит значение ключа индекса и указатель на физический адрес соответствующей записи данных, чтобы можно было использовать двоичный поиск. за O(log2n) Соответствующие данные получены в пределах сложности.
Хотя это надежный индекс, практические системы баз данных почти не используют бинарные деревья поиска или их эволюционные разновидности.красно-черное дерево(красно-черное дерево), причины будут описаны ниже.
B-дерево и B+дерево
В настоящее время большинство систем баз данных и файловых систем используют B-Tree или его вариант B+Tree в качестве структуры индекса.В следующем разделе этой статьи мы обсудим, почему B-Tree и B+Tree используются таким образом в комбинации. с принципами памяти и принципами доступа к компьютеру.Широко используемый для индексов, этот раздел описывает их исключительно с точки зрения структуры данных.
B-Tree
представляет собой многостороннее дерево поиска (не бинарное):
1. Определить, что любой нелистовой узел имеет не более M потомков и M>2;
2. Число сыновей корневого узла равно [2, M];
3. Количество сыновей нелистовых узлов, отличных от корневого узла, равно [M/2, M];
4. Каждый узел хранит не менее M/2-1 (с округлением вверх) и не более M-1 ключевых слов (не менее 2 ключевых слов)
5. Количество ключевых слов нелистовых узлов = количеству указателей на сыновей - 1;
6. Ключевые слова для нелистовых узлов: K[1], K[2], …, K[M-1] и K[i] 7. Указатели нелистовых узлов: P[1], P[2], …, P[M], где P[1] указывает на ключ, ключевое слово которого меньше K[1]
Поддерево, P[M] указывает на поддерево, ключевое слово которого больше, чем K[M-1], другие P[i] указывают на поддерево, ключевое слово которого принадлежит (K[i-1], K[i]);
8. Все листовые узлы расположены на одном слое;
9. Каждый k соответствует данным.
Например: (M=3) эквивалентно дереву 2-3, дерево 2-3 - это дерево, каждый узел которого имеет либо 2 дочерних элемента и 1 элемент данных, либо 3 дочерних элемента и 2 элемента данных, конечные узлы не имеют дочерних элементов. и иметь 1 или 2 элемента данных.
Поиск B-дерева начинается с корневого узла и выполняет бинарный поиск по (упорядоченной) последовательности ключевых слов в узле, если он попадает, он заканчивается, в противном случае он входит в дочерний узел диапазона, к которому ключевое слово запроса принадлежит; повторять до тех пор, пока соответствующий дочерний указатель не станет пустым или уже не будет конечным узлом; псевдокод алгоритма поиска на B-дереве выглядит следующим образом:
BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);
Особенности B-деревьев:
1. Набор ключевых слов распределен по всему дереву;
2. Любое ключевое слово появляется и появляется только в одном узле;
3. Поиск может закончиться на нелистовом узле;
4. Производительность поиска эквивалентна бинарному поиску по полному набору ключевых слов;
5. Автоматический контроль уровня;Самоконтроль B-деревьев:
Каждый внутренний узел B-дерева содержит определенное количество ключевых значений. Обычно количество значений ключа выбирается между d и 2d. На практике значение ключа занимает большую часть места в узле. Фактор 2 гарантирует, что узлы можно разделить или объединить. Если внутренний узел имеет 2d-ключи, процесс добавления ключа к этому узлу разделит узел на 2d-ключи и 2d-ключи и добавит этот ключ к родительскому узлу. Для каждого разделенного узла требуется минимальное количество ключей. Точно так же, если внутренний узел и его соседи имеют d ключей, то ключ будет удален путем слияния его со своими соседями. Удаление этого ключа приведет к тому, что у этого узла будет d-1 ключей; слияние с соседом добавляет d ключей плюс один, перемещенный от родителя соседа. Результатом является полностью заполненное значение ключа 2d.-
Процесс построения B-дерева:
Далее следует вставить в B-дерево по очереди
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
btreebuild.gif
B+Tree
Существует множество вариантов B-Tree, наиболее распространенным из которых является B+Tree, например, MySQL обычно использует B+Tree для реализации своей индексной структуры.
-
По сравнению с B-Tree, B+Tree имеет следующие отличия:
1. Количество указателей поддеревьев нелистовых узлов равно количеству ключевых слов;
2. Указатель поддерева P[i] нелистового узла указывает на поддерево, значение ключа которого принадлежит [K[i], K[i+1]) (B-дерево — открытый интервал);
3. Добавьте цепочку указателей ко всем листовым узлам;
4. Все ключевые слова появляются в листовых узлах;
5. Внутренний узел не хранит данные, только ключ
Например: (М=3)
Paste_Image.png
Поиск B+ в основном такой же, как B-дерево, разница в том, что дерево B+ попадает только тогда, когда оно достигает конечного узла (B-дерево может попадать в нелистовые узлы), и его производительность также эквивалентна выполнению двоичного поиск по полному набору ключевых слов;
Особенности В+:
1. Все ключевые слова появляются в связанном списке листовых узлов (плотный индекс), а ключевые слова в связанном списке идут по порядку;
2. Нельзя попасть в нелистовой узел;
3. Нелистовой узел эквивалентен индексу (разреженному индексу) листового узла, а листовой узел эквивалентен слою данных, в котором хранятся (ключевые слова) данные;
4. Больше подходит для системы индексации файлов;-
Процесс построения дерева B+:
Далее следует вставить в дерево B+ по очереди
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
Bplustreebuild.gif
Физическое хранилище для индексов
В общем, сам индекс тоже очень большой, и хранить его весь в памяти невозможно, поэтому индекс часто хранится на диске в виде индексных файлов. В этом случае потребление дисковых операций ввода-вывода будет формироваться в процессе поиска по индексу, по сравнению с доступом к памяти потребление операций ввода-вывода на несколько порядков выше, поэтому важнейший показатель для оценки качества данных структура в качестве индекса — это асимптотическая сложность числа операций ввода-вывода на диске во время поиска. Другими словами, структура индекса должна минимизировать количество обращений к диску в процессе поиска.
B-tree
Если каждый блок диска может хранить ровно один узел B-дерева (ровно 2 имени файла). Тогда узел BTNODE представляет блок диска, а указатель поддерева — это адрес другого блока диска.
- Далее смоделируем процесс поиска файла 29:
1. Найдите блок корневого диска 1 файлового каталога в соответствии с указателем корневого узла и импортируйте информацию в память. 【Операция дискового ввода-вывода 1 раз】
2. В это время в памяти есть два файла с именами 17, 35 и три файла с адресами других страниц диска. По алгоритму находим: 173. По указателю p2 находим дисковый блок 3 и импортируем содержащуюся в нем информацию в память. 【Операция дискового ввода-вывода 2 раза】
4. В это время в памяти имеются два файла с именами 26, 30 и три файла данных, в которых хранятся другие адреса дисковых страниц. По алгоритму находим: 265. По указателю p2 находим блок диска 8 и импортируем содержащуюся в нем информацию в память. 【Операция дискового ввода-вывода 3 раза】
6. В это время в памяти есть два файла с именами 28 и 29. По алгоритму находим имя файла 29 и находим дисковый адрес файловой памяти.
Анализируя описанный выше процесс, выясняется, что требуется 3 операции ввода-вывода на диск и 3 операции поиска в памяти. Что касается поиска имени файла в памяти, поскольку это упорядоченная табличная структура, половинный поиск можно использовать для повышения эффективности. Что касается операции ввода-вывода, то она является определяющим фактором, влияющим на эффективность поиска всего B-дерева.
Конечно, если мы используем дисковую структуру хранения сбалансированного бинарного дерева для поиска, диск будет в 4 раза, вплоть до 5 раз, и чем больше файлов, тем меньше дисковых операций ввода-вывода будет использовать B-дерево, чем сбалансированное бинарное дерево, и КПД будет выше.
B+tree
- Преимущества B+tree:
- Стоимость чтения и записи диска для B+-дерева ниже
Внутренний узел ****B+-дерева**** не имеет указателя на конкретную информацию ключевого слова. Следовательно, его внутренние узлы меньше, чем B-деревья. Если все ключевые слова одного и того же внутреннего узла хранятся в одном блоке диска, тем больше ключевых слов может содержать блок диска. Чем больше ключевых слов нужно искать, тем больше считывать в память за один раз. Условно говоря, количество операций чтения и записи ввода-вывода также уменьшается.
Например, предположим, что дисковый блок на диске содержит 16 байтов, ключевое слово — 2 байта, а информационный указатель ключевого слова — 2 байта. Для внутреннего узла B-дерева 9-го порядка (узел имеет максимум 8 ключей) требуется 2 диска. в то время как ****В+
**** Внутреннему узлу дерева требуется только 1 диск быстро. Когда внутренний узел необходимо прочитать в память, B-дерево имеет на одно время поиска дискового блока больше (в диске время вращения диска), чем дерево ****B+****. - Эффективность запросов B+-дерева более стабильна
Потому что нетерминал — это не тот узел, который окончательно указывает на содержимое файла, а только индекс ключевого слова в листовом узле. Таким образом, любой поиск по ключевому слову должен проходить по пути от корневого узла к конечному узлу. Длина пути всех запросов с ключевыми словами одинакова, что обеспечивает одинаковую эффективность запроса для всех данных.
Механизм хранения индексов двух механизмов хранения mysql
Реализация индекса MyISAM
Механизм MyISAM использует B+Tree в качестве структуры индекса, а поле данных конечного узла хранит адрес записи данных. На следующем рисунке представлена схема индекса MyISAM:
Здесь в таблице три столбца.Предполагая, что мы используем Col1 в качестве первичного ключа, приведенный выше рисунок является схематическим представлением первичного ключа таблицы MyISAM. Видно, что индексный файл MyISAM сохраняет только адрес записи данных. В MyISAM нет разницы в структуре между первичным индексом и вторичным ключом (Secondary key), но первичный индекс требует, чтобы ключ был уникальным, в то время как ключ вторичного индекса может повторяться. Если мы построим вторичный индекс на Col2, структура этого индекса показана на следующем рисунке:
Это также B+Tree, и поле данных сохраняет адрес записи данных. Таким образом, алгоритм поиска индекса в MyISAM заключается в том, чтобы сначала искать индекс в соответствии с алгоритмом поиска B + Tree.Если указанный ключ существует, значение поля данных извлекается, а затем считывается соответствующая запись данных со значением поля данных в качестве адреса.
Метод индексирования MyISAM также называется «некластеризованным».
Реализация индекса InnoDB
Хотя InnoDB также использует B+Tree в качестве структуры индекса, конкретная реализация полностью отличается от MyISAM.
Первое существенное отличие заключается в том, что файлы данных InnoDB сами по себе являются индексными файлами. Из вышеизложенного известно, что индексный файл MyISAM и файл данных разделены, а индексный файл сохраняет только адрес записи данных. В InnoDB сам файл данных таблицы представляет собой индексную структуру, организованную B+Tree, а поле данных конечного узла этого дерева сохраняет полные записи данных. Ключ этого индекса является первичным ключом таблицы данных, поэтому сам файл данных таблицы InnoDB является первичным индексом.
Вышеприведенный рисунок представляет собой схематическую диаграмму основного индекса InnoDB (который также является файлом данных).Вы можете видеть, что конечные узлы содержат полные записи данных. Такой индекс называется кластерным индексом. Поскольку файлы данных InnoDB агрегируются по первичному ключу, InnoDB требует, чтобы таблица имела первичный ключ (MyISAM может не иметь его).Если он не указан явно, система MySQL автоматически выберет столбец, который может однозначно идентифицировать запись данных в качестве первичного ключа.Если он не существует Для этого типа столбца MySQL автоматически генерирует неявное поле в качестве первичного ключа для таблицы InnoDB.Длина этого поля составляет 6 байтов, а тип - long.
Второе отличие от индексов MyISAM заключается в том, что поле данных вторичного индекса InnoDB хранит значение первичного ключа соответствующей записи вместо ее адреса. Другими словами, все вторичные индексы в InnoDB относятся к первичному ключу как к полю данных. Например, вспомогательный индекс, определенный для Col3:
Здесь в качестве критерия сравнения используется код ASCII английских символов. Реализация кластеризованного индекса делает поиск по первичному ключу очень эффективным, но при поиске по вторичному индексу необходимо получить индекс дважды: сначала извлекается вторичный индекс для получения первичного ключа, а затем первичный ключ используется для извлечения. записи в первичном индексе.
Понимание методов реализации индексов различных механизмов хранения очень полезно для правильного использования и оптимизации индексов.Например, зная реализацию индекса InnoDB, легко понять, почему не рекомендуется использовать слишком длинные поля в качестве первичных ключей, поскольку все вторичные индексы ссылаются на первичный ключ Index, длинный первичный индекс сделает вторичный индекс слишком большим. В другом примере не рекомендуется использовать немонотонное поле в качестве первичного ключа в InnoDB, потому что файл данных InnoDB сам по себе является деревом B+, а немонотонный первичный ключ заставит файл данных поддерживать характеристики B+Tree при вставке новых записей Частая корректировка разделения очень неэффективна, и использование поля автоинкремента в качестве первичного ключа является хорошим выбором.