Индекс повышает эффективность запроса.Так же, как книга, которую мы читаем, если мы хотим сразу перейти к определенной главе, нужно ли нам смотреть оглавление и находить количество страниц по оглавлению?
Нам нужна структура данных для хранения этого каталога на компьютере.Обычные структуры данных включают хеш-таблицу, двоичное дерево поиска, двоичное сбалансированное дерево (AVL), красно-черное дерево, поэтому Innodb и MyISAM выбирают дерево b+.
1. Хэш-таблица
Хэш-таблица представляет собой массив + связанный список с нижними индексами 0, 1, 2, 3..... для указания местоположения его данных. Если вы хотите хранить данные в хеш-таблице, сначала используйте алгоритм хеширования для этих данных (в основном, операция по модулю), Если длина массива 13, после модуля 13 это 0-12, что является как раз нижней частью соответствующих данных.Если рассчитанный индекс тот же самый, он будет следовать за связанным списком в позиции нижнего индекса.
недостаток:
- Использование хеш-хранилища требует добавления всех файлов данных в память, что занимает больше места в памяти.
- Поиск хэша - это эквивалентный запрос, который очень быстрый, но между каждыми данными нет правила диапазона, но в реальной работе это больше запрос диапазона, и хеш не подходит.
Нельзя прямо сказать, что mysql не использует хеш-таблицы, но это должно быть определено в соответствии с механизмом хранения, механизм хранения в памяти использует хеш-таблицы.
2. Бинарное дерево поиска
недостаток:
- Как показано на рисунке, в крайних случаях может возникнуть проблема перекоса, и, в конце концов, это становится структурой связанного списка.
- Делает узел дерева слишком глубоким, тем самым увеличивая IO поиска, и теперь IO является узким местом поиска
3. Двоичное сбалансированное дерево-AVL
Чтобы сохранить баланс дерева и избежать перекоса данных, требуется операция поворота, а длина самого длинного поддерева и самого короткого поддерева не может превышать 1 при вращении влево или вправо.Если оно превышает 1, это не AVL дерево в строгом смысле.
недостаток:
1. Когда количество данных велико, для поддержания баланса требуется 1-n ротаций.Эта ротация является пустой тратой производительности, эффективность вставки и удаления крайне низкая, а эффективность запросов очень высока.
- Есть только две ветви, и глубина дерева все еще очень глубока, когда объем данных велик.
4. Красное черное дерево
Самое длинное поддерево не может превышать длину самого короткого поддерева в 2 раза.Благодаря изменению цвета и вращению вставка и запрос уравновешиваются.
Красно-черное дерево — это вариант дерева avl, в котором теряется часть производительности запросов для повышения производительности вставки.
недостаток:
Также есть только две ветки, и глубина все равно будет очень большой, когда объем данных большой.
Вышеупомянутые три двоичных дерева с увеличением данных в конечном итоге будут иметь слишком много узлов, и у них есть одна и только две ветви, поэтому количество операций ввода-вывода будет одинаковым.
Как решить проблему, что веток всего 2 и глубина слишком глубокая, поэтому есть дерево B, добавление веток
5. B-Tree
- Сначала не читай B-минус дерево, читай B-дерево
- Все ключевые значения распределены по всему дереву.
- Поиск может заканчиваться на нелистовом узле, и поиск выполняется по полному набору ключевых слов, а производительность близка к бинарному поиску.
- Каждый узел имеет не более m поддеревьев.
- Корневой узел имеет как минимум 2 поддерева.
- Узел ветвления имеет не менее m/2 поддеревьев (все узлы ветвления, кроме корневого узла и конечного узла).
- Все листовые узлы находятся в одном слое, каждый узел может иметь не более m-1 ключей, и они расположены в порядке возрастания.
Как показано на картинке выше: (картинка - это только ее часть, на самом деле нет предела, не только p1, p2, p3)
Каждый узел занимает один дисковый блок, а узел имеет два ключевых слова в порядке возрастания и три указателя на корневой узел поддерева, а указатель хранит адрес дискового блока, где находится дочерний узел. Три поля области действия, разделенные двумя ключевыми словами, соответствуют полям области действия данных поддерева, на которые указывают три указателя. Возьмем в качестве примера корневой узел, ключевые слова равны 16 и 34, диапазон данных поддерева, на который указывает указатель p1, меньше 16, диапазон данных поддерева, на который указывает указатель p2, равен 16-34, и диапазон данных поддерева, на который указывает указатель p3, больше 34 .
Процесс поиска ключевого слова 28:
- Найдите корневой узелблок диска 1, читать в память. [Первая дисковая операция ввода-вывода]
- Ключ сравнения 28 находится в интервале (16, 34), и найден указатель p2 блока 1 диска.
- Найти по указателю p2дисковый блок 3, читать в память. [Операция ввода/вывода второго диска]
- Ключ сравнения 28 находится в интервале (25, 31), и найден указатель p2 дискового блока 3.
- Найти по указателю p2дисковый блок 8, читать в память. [Третья дисковая операция ввода-вывода]
- Найдите ключевое слово 28 в списке ключевых слов в дисковом блоке 8, конец.
недостаток:
- Каждый узел имеет ключи и данные, а пространство для хранения каждой страницы ограничено.Если данных много, количество ключей, которые может хранить каждый узел, будет меньше.
- Когда объем хранимых данных велик, глубина будет увеличиваться, увеличивая количество операций ввода-вывода для запросов к диску, что влияет на производительность запросов.
6. Дерево В+
Дерево B+ — это оптимизация, основанная на дереве B. Изменения заключаются в следующем:
- Каждый узел дерева B+ может содержать больше узлов. Этому есть две причины. Первая причина — уменьшить высоту дерева. Вторая причина — изменить диапазон данных на несколько интервалов. Более быстрое извлечение.
- Нелистовые узлы хранят только ключи, а листовые узлы хранят ключи и данные.
- Два указателя конечных узлов связаны друг с другом (в соответствии с характеристиками упреждающего чтения с диска), и производительность последовательных запросов выше.
Как показано выше: В дереве B+ есть два головных указателя, один указывает на корневой узел, а другой указывает на наименьший конечный узел ключевого слова, и между всеми конечными узлами (и узлами данных) существует кольцевая структура, поэтому дерево B+ можно разделить на две. Существует несколько операций поиска: одна — это поиск по диапазону и поиск по страницам для первичного ключа, а другая — случайный поиск, начиная с корневого узла.
Различия в индексах в InnoDB и MyISAM
1. Индекс первичного ключа InnoDB
Конечные узлы хранят определенные данные строки
2. InnoDB — индекс непервичного ключа
Листовые узлы индекса, не являющегося первичным ключом, хранят значение первичного ключа (поэтому данные запроса в основном должны быть возвращены в таблицу).
3. MyISAM
Листовой узел хранит адрес данных строки, что требует одной дополнительной адресации и еще одного ввода-вывода.
Резюме: почему mysql использует дерево B+
Точное выражение: почему механизмы хранения mysql InnoDB и MyISAM используют деревья B+ для индексов
- Хеш-таблица, запрос на равное значение выполняется очень быстро, но он не соответствует общему поиску по диапазону, и нет связи между двумя соседними значениями, а сравнение хэшей потребляет память.
- Бинарное дерево/сбалансированное бинарное дерево/красно-черное дерево все имеют и только 2 ветви.Общим является то, что при большом объеме данных глубина дерева становится глубже и увеличивается количество операций ввода-вывода.
- B-дерево будет хранить данные об узлах, так что количество ключей, хранящихся на странице, будет уменьшено, а глубина дерева будет увеличена.
- Неконечные узлы в дереве B+ удаляют данные, что увеличивает количество ключей на странице, а конечные узлы соединяются через связанный список, что способствует поиску по диапазонам и пейджингу.
Спасибо за чтение. Если у вас есть какая-либо помощь, вы можете поставить лайк, чтобы поощрить вас. Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение для обмена!