Каждое решение создается для решения определенного типа проблем, поэтому при вопросе, почему используется определенное решение, его суть состоит в том, чтобы исследовать, для каких потребностей используется это решение и какие проблемы оно решает.
Таким образом, чтобы выяснить, почему InnoDb использует дерево B+, нужно выяснить, для каких потребностей используется дерево B+ и какие проблемы оно решает.
что нужно
Давайте рассмотрим некоторые часто используемые операторы SQL.
# 根据某个确定值来查询对应的信息
select id, name, email from user where id = 1;
# 通过区间值查询
select id, name, email from user where id > 12 and id < 20
# 通过范围查询并进行排序
select id, name, email from user where id < 123 order by id desc limit 10;
Из приведенных выше нескольких часто используемых SQL мы видим, что в процессе поиска данных в базе данных существуют следующие три типа требований:
- Найти точно и быстро на основе значения
- Быстро найти данные в этом интервале на основе верхнего и нижнего пределов интервала
- Запрос подходящих записей и сортировка по определенным полям
Поэтому необходимо найти решение, отвечающее всем вышеперечисленным требованиям. Существует два типа структур данных, которые обычно используются для запросов:
- хеш-таблица
- Дерево
хеш-таблица
Хеш-таблица (хеш-таблица) представляет собой структуру данных, доступ к которой осуществляется напрямую по (ключу, значению).Он сопоставляет значение ключа с соответствующей позицией хеш-таблицы через хеш-функцию, и эффективность поиска очень высока.
Один из типов индекса в индексе, хеш-индекс, реализован на основе хеш-таблицы.Предположим, мы строим хэш-индекс по имени, процесс поиска показан на следующем рисунке:
Для каждой строки данных механизм хранения будет вычислять хэш-код для всех столбцов индекса (расположение хэш-таблицы выше), и каждый элемент в хеш-таблице указывает на указатель строки данных, потому что сам индекс хранит только соответствующее хэш-значение, поэтому структура индекса очень компактна, и соответствующую запись данных можно найти непосредственно в соответствии со значением ключа, что делает скорость поиска хеш-индекса очень быстрой! Но у хеш-индекса есть и свои недостатки, а именно:
- Действительны только запросы, соответствующие всем столбцам индекса. Например, если я создаю хэш-индекс для столбцов (имя, адрес), если запрашивается только имя столбца данных, индекс нельзя использовать.
- Хеш-индекс хранится не в порядке значений индекса, то есть хэш-значение ключа, вычисленное хэш-функцией, не в порядке, поэтому его нельзя использовать для сортировки, и его нельзя искать по интервалу .
- Хэш-индексы поддерживают только запросы сравнения на равенство, такие как = и in(), и не поддерживают поиск диапазона, например id > 17.
Таким образом, хэш-индекс подходит только для определенных случаев и действительно может привести к значительному повышению производительности при использовании в соответствующих сценариях. Например, в InnoDB есть специальная функция, называемая «адаптивный хэш-индекс».Если InnoDB заметит, что некоторые значения столбца индекса часто используются, он создаст другой хэш-индекс на основе индекса дерева B+ в памяти, чтобы Дерево B+ также имеет преимущества хэш-индекса.
Следовательно, структура хеш-таблицы не может соответствовать указанным выше требованиям.
Далее давайте посмотрим на дерево.
Дерево
Сбалансированное бинарное дерево
Сбалансированное бинарное дерево можно использовать для поиска, и временная сложность его поиска составляет примерно O(log2n), но можно ли использовать сбалансированное бинарное дерево в качестве структуры индекса?
Ответ - нет.
Поскольку данных таблицы базы данных обычно много, они обычно хранятся на диске. Скорость диска во много раз медленнее, чем у памяти, поэтому постарайтесь уменьшить количество считываний диска, а повысить скорость за счет чтения данных из памяти.
Итак, как поместить в память как можно больше эффективных индексных данных?
Здесь нужно решить две проблемы:
1. как можно больше
При чтении данных с диска они считываются блоками диска (принцип локальности и опережающего чтения с диска), а не по одному. При использовании древовидной структуры в качестве индексированной структуры данных нам нужно считывать узел дерева с диска каждый раз, когда мы просматриваем данные, то есть соответствующий блок диска, поэтому, если мы можем поместить как можно больше данных в блок диска , то каждый раз будет считываться больше данных.
Сбалансированное бинарное дерево заключается в том, что каждый узел хранит только одно значение ключа и данные, то есть при хранении каждый блок диска хранит только одно значение ключа и данные.
Если хранится большой объем данных, то возможно, что в сбалансированном бинарном дереве будет много узлов, а высота дерева будет чрезвычайно велика, при поиске данных будет выполняться много дисковых операций ввода-вывода, а эффективность будет чрезвычайно низкий.
Так что сбалансированное бинарное дерево не может решить проблему хранения в памяти как можно большего количества индексов.
2. Действительные данные индекса
Когда мы говорим сбалансированное двоичное дерево, мы имеем в виду сбалансированное двоичное дерево по логической структуре, а его физическая реализация представляет собой массив. Следовательно, на логически подобных узлах их физическое расположение может быть далеко друг от друга. Следовательно, многие данные о странице диска, считываемые каждый раз, могут не использоваться, то есть эффективных данных индекса не так много, поэтому в процессе поиска по-прежнему требуется много операций чтения с диска.
Таким образом, сбалансированное бинарное дерево также не может решить эту проблему.
Поэтому была придумана структура данных, способная решить эти две проблемы — B-дерево.
B-дерево
B-дерево (Balance Tree), что означает сбалансированное дерево. B-дерево эволюционировало из сбалансированного двоичного дерева. Каждый узел B-дерева может хранить несколько ключевых слов. Размер узла устанавливается равным размеру страницы на диске, что позволяет в полной мере использовать функцию упреждающего чтения с диска. Весь узел считывается каждый раз, когда читается страница диска. Поскольку каждый узел хранит много ключевых слов, глубина дерева будет очень маленькой. Тогда количество выполняемых операций чтения с диска будет очень маленьким, и будет больше искать прочитанные данные в памяти. Пример структуры B-дерева показан на следующем рисунке:
Поскольку каждый узел B-дерева, то есть каждый блок диска, хранит больше данных, проблема хранения как можно большего количества индексов, упомянутая выше, в определенной степени решается. Это также в определенной степени решает проблему хранения как можно большего количества действительных индексов.
Однако B-дерево решает проблему только до определенной степени, и нам нужно решить проблему лучше. То есть можно ли хранить более эффективные индексы?
Ответ положительный. Здесь в игру вступает дерево B+.
Лучшее дерево B+, которое решает проблему
B-дерево решает проблему в определенной степени, а B+-дерево, развившееся из B-дерева, может решить проблему лучше, поэтому B-дерево практически не используется на практике.
Структурная схема дерева B+ выглядит следующим образом:
Так в чем же разница между деревом B+ и деревом B?
- В дереве B+ данные не хранятся на нелистовых узлах, хранятся только ключевые значения.
Поскольку размер страницы в базе данных фиксирован, размер страницы в InnoDB по умолчанию составляет 16 КБ. Если данные не сохраняются, узел может хранить больше ключевых значений, и соответствующее дерево порядка дерева будет больше. то же самое С точки зрения количества данных, требуемая высота дерева будет ниже, а дерево будет более приземистым, так что количество дисковых операций ввода-вывода при поиске данных будет уменьшено, а эффективность запросов будет улучшена.
Поскольку порядок дерева B+ равен количеству значений ключа, при условии, что узел дерева B+ может хранить 1000 значений ключа, тогда дерево B+ с 3 уровнями может хранить 1000 x 1000 x 1000 = 1 миллиард данных. И обычно корневой узел находится в памяти, поэтому для поиска 1 миллиарда данных требуется всего 2 дисковых ввода-вывода.
Эта функция B+ решает упомянутую выше проблему хранения как можно большего количества индексных данных, а эффективность запросов также высока.
- Данные индекса в листовых узлах B+-дерева расположены по порядку, а листовые узлы связаны через двусвязный список.
Эта функция делает дерево B+ чрезвычайно простым для реализации поиска по диапазону, поиска по сортировке, группового поиска и других операций. Однако реализовать эти операции в B-дереве непросто, поскольку данные разбросаны по каждому узлу.
Поскольку данные индекса сортируются по порядку, то есть каждый раз при чтении страницы данных необходимо использовать большую часть данных индекса в ней, поэтому это также является хорошим решением вышеупомянутого способа хранения как можно большего количества данных. Возможна эффективная проблема с индексацией данных.
Суммировать
Благодаря приведенному выше анализу мы можем обнаружить, что при использовании определенного решения это решение должно использоваться для удовлетворения определенных требований, и в процессе удовлетворения требований возникнут некоторые проблемы, и окончательное решение должно быть способно решить проблему и максимально удовлетворить потребности.
Поэтому, четко изучив, какие потребности удовлетворяет определенное решение, какие проблемы оно решает и как решать проблемы, вы также поймете, почему используется это решение.