предисловие
Структура индекса и алгоритм поиска
Как оператор sql работает в mysql? Как ты это нашел? Среди них база данных (хранимые данные) и алгоритм поиска. Давайте сначала рассмотрим несколько алгоритмов поиска;
- Поиск в каталоге: аналогичный индекс
- Обход: поиск методом грубой силы
- Разделение пополам: базовый алгоритм B+ деревьев
- Поиск ключа: поиск хэша
Структуры данных, которые можно индексировать: массив, связанный список, красно-черное дерево, B-дерево (B-дерево, B+ дерево).
Итак, какая структура данных подходит для структуры хранения базы данных MySql?
Поговорим об общих способах хранения данных: память (подходит для небольшого объема данных), диск (большой объем данных).
Принцип работы диска: скорость + вращение, концепция страниц диска: каждая страница около 16Кб.
Структуры данных, которые не подходят для MySql и почему
Массивы и связанные спискиНедостатком является то, что его нельзя сохранить при большом объеме данных, а значит, он не подходит для больших объемов данных.
хэшХеш-значение вычисляется хэш-функцией, и происходит коллизия хэшей.Кроме того, хэш не поддерживает запрос по частичному индексу и поиск по диапазону. Но преимущество хеширования в том, что временная сложность поиска составляет O(1), поэтому когда можно использовать хэш-индекс? То есть, когда условия запроса не изменятся, и нет частичных запросов и запросов диапазона.
красно-черное деревоКогда объем хранимых данных велик, количество слоев узлов в красно-черном дереве велико, то есть высота дерева относительно высока.При поиске базовых данных количество поисков относительно велико, то есть дисковый ввод-вывод используется чаще. Его можно свести к следующим двум пунктам:
- Слишком много отходов, чтобы читать: При расчете каждый слой исходного дерева, вероятно, должен быть выделен16KBОднако для красно-черного дерева фактическое количество хранимых узлов относительно невелико, то есть размер хранимых данных намного меньше, чем16KB, что приводит к пустой трате места для хранения
- Слишком много операций чтения с диска: Чем больше слоев дерева, тем больше раз диск читается при поиске данных
Как показано ниже, если вам нужно найти числа4Если его нужно искать три раза, то есть три операции дискового ввода-вывода:
Давайте задумаемся, почему красно-черное дерево можно использовать в поиске hashMap?
Это включает в себя разницу между диском и памятью.Я не буду объяснять это здесь, просто знайте, что это потому, что hashMap использует память.
Внедрение BTree и B+Tree
Что можно улучшить по двум изложенным выше пунктам (причина, по которой он не подходит для структуры данных mysql)? Мы можем начать со следующих двух пунктов:
- Увеличьте количество узлов в каждом слое дерева, чтобы выделенные 16 КБ можно было использовать полностью, то есть для решения вышеуказанной проблемы потерь чтения.
- Максимально уменьшите высоту дерева, чтобы дерево выглядело «коренастым», что может уменьшить количество операций чтения с диска.
Итак, как мы можем достичь вышеуказанного метода? Это требует использования деревьев B+ Фактически, базовой структурой данных MySql является используемое дерево B+.
Структура данных BTree
Несколько важных характеристик BT-деревьев порядка N:
- Узел содержит не более N поддеревьев (указателей), N-1 ключевых слов (пространства для хранения данных) (N>=2);
- За исключением корневого узла и листового узла, каждый другой узел имеет не менее M=N/2 дочерних узлов, и M округляется в большую сторону, то есть при разбиении отделяется от середины и делится на M поддеревьев;
- Если корневой узел не является листовым узлом, существует как минимум два поддерева.
Что это значит? Давайте взглянем на следующее B-дерево третьего порядка. Структура выглядит так:
В BTree есть очень важная операция: если дерево не соответствует вышеуказанным свойствам, какая операция будет выполнена? Все уже знают, что красный и черный будут менять цвета, вращаться влево или вправо (Бинарное дерево, красно-черное дерево и реализация красно-черного дерева в Голанге). BTree выполнит операцию разделения.
Сначала рассмотрим пример:
Создайте BTree 5-го порядка и вставьте следующие данные: 2, 13, 6, 1, 7, 4, 10, 12, 5, 16, 22.
Согласно характеристикам BTree, на странице диска на уровне 5 имеется не более 5 указателей (адресов для хранения путей поиска) и 4 областей хранения (ключевых слов хранения, то есть данных, подлежащих хранению), тогда конкретные вставленные данные выглядят следующим образом:
При вставке 7 обнаруживается, что места недостаточно.В это время произойдет операция разделения, отделение промежуточного узла и перемещение промежуточного узла в корневой узел следующим образом:
При вставке 16, которое больше 6, оно должно быть вставлено справа от правого поддерева 13, но найденного места недостаточно, в это время будет выполняться операция разделения, и средний узел (12) дерева правое поддерево будет отделено, а средний узел будет разделен.Перейдите к корневому узлу, а затем разделитесь на левое и правое поддеревья.На данный момент всего имеется три поддерева, как показано ниже:
Наконец, полное дерево, полученное вставкой 22, выглядит следующим образом:
Вы также можете добавить много других данных, а затем посмотреть на эффект после разделения, и я не буду перечислять их все здесь.
Следует отметить, что узел разделенного дерева по-прежнему должен соответствовать характеристикам BTree, а на самом деле он также соответствует характеристикам бинарного дерева поиска (бинарного дерева сортировки).Если вы забыли студентов, вы можете обратиться к статье, написанной ранее:Бинарное дерево, красно-черное дерево и реализация красно-черного дерева в Голанге.
Видно, что значение левого поддерева меньше 6, значение среднего узла (7, 10) находится между 6 и 12, а значение правого поддерева больше 12. Как правило, это упорядочено слева направо.
Вышеуказанные операции представляют собой подробный процесс построения BTree.Следует отметить, что операция разделения выполняется в процессе построения.После разделения мы должны обратить внимание на то, удовлетворяются ли еще характеристики BTree, и является ли это бинарной сортировкой дерево. Иногда при вставке числа оно может проходить через несколько операций разделения.
Возвращаясь к двум упомянутым выше вопросам: 1.Слишком много отходов, чтобы читать2.Слишком много операций чтения с диска. По характеристикам BTree мы видим, что эффективность поиска BTree достаточно высока, и он также может решить эти две проблемы. Но MySql по-прежнему не использует структуру данных BTree, почему?
Основные причины следующие:
- Потому что BTree не подходит для поиска диапазона. Возьмем приведенное выше в качестве примера.Например, если я хочу найти данные меньше 6, я сначала найду узел 6, а затем мне нужнотраверсЕсли вы не пройдете левое поддерево из 6 узлов (индекс), вы не сможете получить данные меньше 6, а это означает, что индекс недействителен, поэтому он не подходит для поиска по диапазону.
- В дополнение к хранению узлов BTreeпоказательКроме того, также хранитсяданныеСамо по себе занимает много места, но размер страницы диска ограничен (около 16Кб), поэтому при хранении данных одного размера BTree относительно высока (относительно B+Tree), а его стабильность слабее.
Подводя итог двум основным причинам, MySql, наконец, выбралB+Treeструктура данных для хранения данных.
Структура данных B+Tree
Процесс разделения B+Tree и BTree аналогичен, за исключением того, что нелистовые узлы B+Tree не будут хранить данные, только значение индекса (адрес указателя), и все данные хранятся в конечных узлах, цель повысить стабильность системы секса. Процесс разделения B+Tree здесь больше не указан. Давайте непосредственно посмотрим, как выглядит B+Tree, как показано на следующем рисунке:
Фактически базовая структура данных B+Tree MySql выглядит так, как показано на следующем рисунке:
Видите разницу между B+Tree и BTree? Из приведенного выше рисунка видно, что B+Tree имеет следующие характеристики:
- Листовые узлы связаны, это упорядоченный двусвязный список, цель которого состоит в том, чтобы решить поиск диапазона. Например, если вам нужно найти данные меньше 9, вам нужно только найти данные, равные 9, а затем вынуть все данные слева от 9.
- Нелистовые узлы не хранят данные, а только индексы, и использование пространства более эффективно.
- Количество данных равно количеству узлов, другими словами, нелистовые узлы хранят максимальное или минимальное значение своих поддеревьев.
В случае сбоя индекса BTree необходимо пройти все дерево, чтобы получить все данные, в то время как B+Tree нужно только найти первый узел конечного узла, чтобы получить все данные.Видно, что эффективность выше. чем B+Tree. , что является магией двусвязного списка.
Вычислите порядок m, то есть сколько B+Tree нужно взять
Как рассчитывается м? Он рассчитывается в соответствии с размером страницы диска, то есть определяется размером страницы диска.
Мы знаем, что размер страницы диска составляет около 16 КБ. Когда MySql создает индекс, он может рассчитать, сколько данных может хранить страница диска, исходя из полей и типов.
Согласно официальному описанию документа, при высоте дерева равной 2 (уровень 2) оно может хранить более 20 000 единиц данных, при высоте равной 3 (уровень 3) оно может хранить более 20 миллионов единиц данных. данных Как рассчитать?
Во-первых, 1 килобайт (КБ) = 1024 байта (В), страница имеет 16 КБ, при условии, что хранилищепервичный ключ + указательЕсть примерно 8+6=14Б, тогда можно сохранить одну страницу: 16*1024/(8+6)=1170индекс.
Для B+дерева 3-го порядка оно, вероятно, может хранить: 1170^3 фрагментов данных, что составляет около 20 миллионов.
Суммировать
BTree — это переход B+Tree.B+Tree подходит для дисковых индексов с большими объемами данных.Классический — базовая структура индекса MySql, упомянутая выше.Все данные существуют в листовых узлах, а другие узлы только хранят индексы. , что повышает стабильность системы, повышает эффективность поиска и сокращает операции ввода-вывода на диск во время запроса.
Больше качественных технических статей, все в "Перейти клавишный воин"Официальный аккаунт, интересующиеся могут обратить внимание на обмен.