Индекс MySQL (2) хранение дерева B+ на диске

MySQL

обзор

w200


предыдущий пост«Зачем использовать дерево B+ для индекса MySQL»Я рассказал о том, почему MySQL решил использовать дерево B+ в качестве базовой структуры хранения, и поднял два вопроса:

  1. Индекс дерева B+ не находит строку напрямую, а просто находит страницу, на которой находится строка, считывает всю страницу в память, а затем выполняет поиск в памяти.
  2. Высота дерева B+ индекса обычно составляет 2-4 слоя, и при поиске записей требуется максимум 2-4 IO.

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

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

Как мы все знаем, данные MySQL на самом деле хранятся в файлах, а скорость поиска дискового ввода-вывода намного ниже, чем скорость памяти, поэтому уменьшение количества дисковых операций ввода-вывода может значительно повысить производительность MySQL.

1.1 Почему дисковый ввод-вывод медленный

Сначала просмотрите очки знаний:Время дискового ввода-вывода = поиск + вращение диска + время передачи данных

При чтении данных с диска система отправляет логический адрес на диск, а диск транслирует логический адрес в физический адрес (какая дорожка, какой сектор). При механическом движении магнитная головка сначала находит соответствующую дорожку, а затем находит соответствующий сектор дорожки.Сектор - это наименьшая единица хранения данных на диске (см.图1-1).

-w356
 Рисунок 1-1 Физическая структура диска

1.2 Сравнение производительности

Производительность последовательного чтения и записи механического жесткого диска очень хорошая, но производительность произвольного чтения и записи очень низкая.

  • Последовательный доступ: скорость доступа к памяти в 6-7 раз выше, чем скорость доступа к жесткому диску (kafkaхарактеристики, о них я расскажу позже, если будет возможность)
  • Произвольный доступ: скорость доступа к памяти выше, чем скорость доступа к жесткому диску.Более 100 000 раз

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

2. Хранение индексов на диске

Зная производительность дискового ввода-вывода, давайте посмотрим, как MySQL проектирует физическое хранилище индексов в соответствии с этой ситуацией.InnoDBВозьмем двигатель в качестве примера,MyISAMОн немного отличается, о чем будет сказано позже.

Предположим, у нас есть такая таблица图2-0Данные

CREATE TABLE `user` (
  `ID` bigint(11) NOT NULL AUTO_INCREMENT,
  `NAME` varchar(20),
  PRIMARY KEY (`ID`),
  KEY `idx_name` (`NAME`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Рисунок 2-0 Табличные данные

2.1 Кластерный индекс (Clustered index)

Каждая таблица InnoDB имеет специальный индекс, называемый кластерным индексом, который представляет собой дерево B+, построенное из первичного ключа таблицы.

Создайте кластеризованный индекс, показанный на рис. 2-1, на основе демонстрационных данных:

 Рисунок 2-1 Кластеризованный индекс дерева B+

2.1.1 Очки знаний

  • Конечные узлы хранят все данные строк всей таблицы.
  • Нелистовые узлы не хранят данные строки, чтобы хранить больше ключей индекса, тем самым уменьшая высоту дерева B+, тем самым уменьшая количество операций ввода-вывода.
  • Хранение кластеризованного индекса не является физически непрерывным, и каждая страница данных связана двусвязным списком в другом блоке диска.

2.1.2 Найти: Предположим, вы хотите найти элемент данных 6

  1. Загрузите корневой узел из дискового блока 0 в память, сгенерируйте IO и используйте двоичный поиск в памяти, чтобы определить, что 6 находится между 3 и 9;
  2. По дисковому адресу указателя P2 в память загружается диск 2, происходит второй IO и выполняется бинарный поиск в памяти для нахождения 6, и конец.

Здесь выполняются только два IO.На самом деле размер каждого блока диска составляет 4K, а 3-х уровневое дерево B+ может представлять миллионы данных, то есть для каждого поиска требуется только 3 IO, поэтому повышение производительности индекс будет огромен.



2.1.3 Как выбрать кластеризованный индекс

Каждая таблица InnoDB имеет один и только один кластеризованный индекс, так как же она выбирает индекс?

  • В общем, используйтеPRIMARY KEYкак кластеризованный индекс.
  • если не определеноPRIMARY KEY, будет использовать первыйUNIQUEиNOT NULLстолбец как кластеризованный индекс.
  • Если в таблице нет подходящегоUNIQUEИндекс, который будет внутренне генерировать скрытый кластеризованный индекс на основе значения идентификатора строки.GEN_CLUST_INDEX.

Поэтому при построении таблицы, если нет логически уникального и ненулевого столбца, вы можете добавить столбец auto_increment, чтобы упростить создание кластеризованного индекса.

2.2 Некластеризованные индексы (вторичные индексы)

Некластеризованный индекс также называется вспомогательным индексом.Листовые узлы не содержат данных записи строки, но хранят ключ кластеризованного индекса.

По данным выборки (idx_nameindex) для построения вспомогательного индекса, как показано на рис. 2-2:

 Рисунок 2-2 Некластеризованный индекс дерева B+

2.2.1 Очки знаний

  • Каждая таблица может иметь несколько вторичных индексов.
  • При поиске данных по вспомогательному индексу сначала выполните поиск по вспомогательному индексу, чтобы получить первичный ключ кластеризованного индекса, а затем используйте индекс первичного ключа, чтобы найти полную запись строки.
  • Поиск по индексу, не являющемуся первичным ключом, выполняется в два раза медленнее, чем по индексу с первичным ключом.

2.2.2 Найти: ПолучитьNAME=JakeДанные

Первый этап: найти первичный ключ индекса первичного ключа через вспомогательный индекс

  1. Загрузите корневой узел, проиндексированный idx_name, в память из дискового блока 0, сгенерируйте IO и найдите его в указателе P2.
  2. По дисковому адресу указателя P2 загружается дисковый блок 2 в память, происходит второй ввод-вывод, и обнаруживается узел Jake и его индекс первичного ключа 9.

Второй этап: найти полную запись строки по индексу первичного ключа

  1. Загрузите корневой узел из дискового блока 0 в память, сгенерируйте ввод-вывод и используйте двоичный поиск в памяти, чтобы определить, что 9 находится в указателе P3.
  2. По дисковому адресу указателя P3 в память загружается диск 3, происходит второй IO, а затем выполняется бинарный поиск в памяти для нахождения 9 и записи его строки,

Поиск окончен.

Продолжение следует…

Если вы хотите следить за обновленными статьями и делиться галантерейными товарами в режиме реального времени, вы можете подписаться на мой официальный аккаунт.

懂了吗


Категории