Как индексирование B-дерева работает в mysql

Когда я создаю индекс для таблицы в mysql, я вижу, что index_type имеет тип BTREE. Теперь, хотя я понимаю о btree (s), я не понимаю, как он хранит индекс и как база данных ищет записи на основе этого.

Я имею в виду, что btree отлично подходит для баз данных для выполнения чтения и записи больших блоков данных, когда мы создаем индекс для типа столбца Primary key, я понимаю, что он создает дерево и разделяет значения для корня на основе типа значения корня.

Теперь, хранит ли он только первичный ключ ID под деревьями или все данные, связанные с этим первичным ключом?

После поиска искомого первичного идентификатора, как база данных извлекает запись?

Ответ 1

В базе данных хранится значение, индексированное как ключ B-Tree, и указатель записи как значение B-Tree.

Всякий раз, когда вы ищете запись, содержащую определенное значение индексированного столбца, механизм находит ключ, удерживающий это значение в B-Tree, извлекает указатель на запись и извлекает запись.

Что такое "указатель записи", зависит от механизма хранения.

В MyISAM указатель записи является смещением к записи в файле MYI.
В InnoDB указатель записи - это значение PRIMARY KEY.

В InnoDB, сама таблица является B-Tree с PRIMARY KEY как ключ B-Tree. Это то, что называется "кластеризованным индексом" или "индексированной таблицей". В этом случае все остальные поля сохраняются как значение B-Tree.

В MyISAM записи сохраняются без специального заказа. Это называется "хранилище кучи".

Ответ 2

MySQL InnoDB фактически использует B + Tree, которые добавляют больше возможностей, чем B-Tree.

Например:

Только у узла листьев есть значения, позволяющие большему количеству ключей в одном и том же узле страницы уменьшить высоту дерева, что уменьшит количество операций ввода-вывода.

Добавьте двунаправленный указатель в каждом листовом узле, чтобы ускорить поиск диапазона

B-Tree

B +

Tree