Где хранятся кластеризованный и некластеризованный индекс дерева B+?

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

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

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

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

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

введите здесь описание изображения

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

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

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


mysql sql indexing clustered-index b-tree
person python    schedule 11.12.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

Вторичный ключ — это отдельный BTree. Структурно два BT-дерева одинаковы, за исключением того, что находится в листовых узлах. Для вторичного ключа копия PRIMARY KEY помещается в конечные узлы. Следовательно, при поиске одной строки («точечный запрос») с использованием вторичного индекса есть две детализации BTree — одна для вторичного индекса и вторичная для PK.

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

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

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

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

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

Теперь для MyISAM:

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

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

person Rick James    schedule 11.12.2015
comment
Лучшее, что я пока читал :) Давно искал что-то подобное. Это значительно проясняет мои сомнения - person python; 11.12.2015
comment
Спасибо за комплимент. Что вы имеете в виду под разъяснением моих сомнений? - person Rick James; 11.12.2015
comment
Комментарий очень полезен. - person python; 11.12.2015