В случае сохранения кластерного и некластеризованного индекса дерева B +?

Question

В настоящее время я читаю об основах B+ Tree и запутался в распределении пространства для кластерного и некластеризованного индекса.

Когда мы создаем кластерный индекс на B+ tree, индекс будет храниться в основной памяти, а листья содержат указатели данных на фактические блоки. Блоки хранятся на дисках, а блоки содержат запись.

• Обычно кластерный индекс создан первичный ключ
• Там может быть только один кластерный индекс

Теперь предположим, что у нас есть таблица (идентификатор, имя, класс), и я создал два некластеризованные индексы на name и class. Мое сомнение в том, где будет храниться некластеризованный индекс? и как поиск будет выполняться для query как

select id, name, class from table where id = 3, name='Leo' and class='10' 

Мое предположение:

• Поскольку идентификатор поле является первичным ключом, так первым использованием кластерного индекса будет ID = 3
• Теперь, используя некластеризованный индекс на name и class, мы найдем остальные поля

Как вы думаете, мое предположение верно? Не могли бы вы подробнее рассказать о хранении кластерного индекса? Имеет ли индекс (кластеризованный и не кластерный) n-арное дерево?). Я не могу одновременно визуализировать как кластерный, так и некластеризованный индекс.

Answer 1

Я говорю конкретно о InnoDB ...

The PRIMARY KEY (как вы говорите) кластер с данными. Весь BTree для этого (data + PK) хранится в одном наборе блоков на диске (а не «основной памяти»). Узлы «листа» содержат все столбцы.

Дополнительный ключ - отдельный бит. Структурно два BTrees одинаковы, за исключением того, что находится в листовых узлах. Для вторичного ключа копия PRIMARY KEY помещается в листовые узлы. Следовательно, при просмотре одной строки («точечный запрос») с использованием вторичного индекса есть два разворота по БРИ - один для вторичного индекса и вторичный для ПК.

Все блоки «кэшируются» в «buffer_pool», поэтому они являются иногда в основной памяти, но всегда сохраняются (рано или поздно) на диске. (Журнал транзакций и т. Д.), Убедитесь, что «позже» не нарушает правила, что данные всегда сохраняются.)

Ваши две фотографии - хороший старт. Однако ...

• Нелистные узлы связаны вместе (как вы показываете), но они не обязательно смежны на диске. При вставке новой строки (или новой записи индекса) блок может «разбить» из-за полного заполнения.Это приводит к разбросу блоков вокруг диска.
• Листовые узлы также связаны друг с другом, но могут быть разбросаны.
• Для некластеризованной, хорошо, рекомендуем вам начать сначала, принимая во внимание проблему PK, и т.д.

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

• запроса точки сверло вниз ВТКЕЙ
• вторичный поиск должен сделать 2 сверло падения
• «Диапазон» сканирует - либо из данных, или индекса - являются очень эффективными, поскольку они сканируют через один блок и затем переходите к (логически) следующего блока через двунаправленную связь между блоками на нижнем уровне. Следовательно, это действительно B + Tree, а не просто BTree.
• (больше на диапазоне) WHERE clustered_key BETWEEN ... является очень эффективным
• (больше на диапазоне) WHERE secondary_key BETWEEN ... очень эффективны при нахождении ПК значения, которые нужно, но затем превращается в кучу (потенциально) случайных точечных запросы.
• Все блоки в значительной степени эквивалентны для кеширования. Но (очевидно?) Не-листовые узлы, как правило, живут в кеше из-за «наименее используемого» алгоритма. (Я оставляю много деталей.)
• Может быть только один кластерный индекс. (Если вы не желаете дублировать все данные, это было сделано в нескольких двигателях, кроме InnoDB.)
• Блок содержит столько «записей» (данных или индексов или не-лист), сколько практично у них момент - от 1 до сотен.
• По умолчанию блок составляет 16 КБ. (И не легко изменить.)
• С innodb_file_per_table = ON все BTrees для данной таблицы живут в одном табличном пространстве .ibd '.
• С innodb_file_per_table = OFF все BTrees для всех таблиц живут в одном глобальном «табличном пространстве», называемом ibdata1. (Опять же, чрезмерно упрощена.)

Теперь для MyISAM:

• Данные для одной таблицы жизни в файле (.MYD).
• Все индексы (включая PRIMARY KEY) для одной таблицы живут в файле (.MYI)
• Все индексы - это BTrees. (Данные отсутствуют.)
• Листовые узлы индекса 'point' в файле данных.
• Индексные блоки составляют 1 КБ.
• Файл данных - это просто поток с произвольным доступом.

(Есть много больше деталей.)