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

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

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

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

Как база данных извлечет запись после обнаружения нужного первичного идентификатора?


mysql database search b-tree
person JPro    schedule 02.03.2010    source источник

Ответы (2)


arrow_upward
24
arrow_downward

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

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

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

  • В MyISAM указатель записи представляет собой смещение к записи в файле MYI.

  • В InnoDB указатель записи является значением PRIMARY KEY.

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

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

person Quassnoi    schedule 02.03.2010
comment
Спасибо за объяснение. В моей базе данных у меня есть несколько таблиц с MyISAM и некоторые как InnoDB с индексами на них. Повлияет ли это каким-либо образом на соединения и запросы, которые я пишу, это разные типы? - person JPro; 02.03.2010
comment
@JPro: база данных автоматически обрабатывает базовые детали индексации. Синтаксис JOIN одинаков для таблиц MyISAM и InnoDB. - person Quassnoi; 02.03.2010
comment
я имею в виду, имеет ли вообще значение создание всех таблиц с одним и тем же механизмом хранения или нет? - person JPro; 02.03.2010
comment
@JPro: вы можете свободно смешивать разные движки в одном запросе. Однако имейте в виду, что MyISAM не поддерживает транзакцию, и при использовании нескольких таблиц в одном запросе DML, который вы позже откатываете, имейте в виду, что откат не повлияет на изменения в таблицах MyISAM. Но, опять же, в запросе SELECT совершенно нормально смешивать оба движка. - person Quassnoi; 02.03.2010
comment
только последний вопрос. Я вижу в своей папке mysql два типа файлов (.frm и .myd), файлы .myd больше, чем файлы .frm. Я предполагаю, что .frm используется btrees. Как данные сохраняются в этом файле? Если база данных хочет найти какую-либо запись, она просто открывает файл и выполняет поиск по дереву? - person JPro; 02.03.2010
comment
@JPro: FRM — это описание таблицы, оно не содержит данных. Для MyISAM данные таблицы содержатся в MYD полях, данные индекса содержатся в MYI файлах. Для InnoDB табличные данные содержатся в InnoDB табличных пространствах, которые могут быть общими (все таблицы и индексы находятся в одном файле в корне каталога данных) или отдельными таблицами (таблица и все ее индексы находятся в один файл ibd в каталоге базы данных) - person Quassnoi; 02.03.2010

arrow_upward
2
arrow_downward

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

Такие как:

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

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

B-дерево

B-дерево

Дерево B+

B+Дерево

person sendon1982    schedule 19.10.2019