Я полагаю, что многие друзья-программисты знакомы с индексированием данных. Наиболее распространенным индексом является B+ Tree index. Индексирование может ускорить поиск в базе данных, но снизит скорость операций добавления, изменения и удаления. Некоторое неправильное написание приведет к индексация, сбой и т. д.
Но если спросить, почему после использования индекса запрос выполняется быстрее? Каков принцип B+ Tree index? В настоящее время многие люди могут этого не знать.Сегодня я возьму в качестве примера движок MySQL InnoDB, чтобы рассказать о принципе индекса B+ Tree.
Основы индексации
Базовая структура хранения MySQL — это страница, которая, вероятно, выглядит так:
Здесь нам необходимо знать следующее (очень важное):
- Когда мы создаем таблицу с помощью механизма MySQL InnoDB, может быть только один первичный ключ, если мы не укажем явно между ними, то MySQL автоматически сгенерирует неявное поле в качестве первичного ключа;
- Кластеризованный индекс: индекс, созданный с помощью первичного ключа, конечные узлы кластеризованного индекса хранят данные в таблице;
- Некластеризованный индекс: индекс, созданный не первичным ключом; некластеризованный индекс хранит первичный ключ и столбцы индекса в конечных узлах; при использовании некластеризованного индекса для запроса данных первичный ключ на листе будет запрошены, а затем данные будут найдены по первичному ключу (этот процесс называется поверхностью возврата).
Отношения между страницами и между страницами и между страницами и данными
Мы используем кластерный индекс как объяснение. Отношения между страницами и страницами и между страницами и данными следующие:
- Между страницей данных и страницей данных формируется двусвязный список;
- Запись на каждой странице данных представляет собой односвязный список;
- Каждая страница данных формирует каталог страниц (Page directory) по внутренним записям, если это первичный ключ, то его можно быстро найти в каталоге страниц методом дихотомии;
- Если мы делаем запрос на основе непервичного ключа и неиндексного столбца, нам нужно пройти по двусвязному списку, чтобы найти страницу, на которой он расположен; затем пройти по односвязному списку на странице; если данные в таблице большой, такой запрос будет очень медленным.
Принцип индекса B+ Tree
Давайте сначала посмотрим, как выглядит индекс дерева B+ (на примере кластеризованного/первичного ключа):
- Если мы хотим запросить данные с id = 16 в это время:
- Запросите страницу-1 и обнаружите, что на странице-2 хранится меньше 30 данных;
- Запросите page-2 и обнаружите, что page-5 хранит данные от 10 до 20;
- Запросите страницу-5 и найдите данные с id = 16.
Очевидно, что когда индекс не используется, необходимо пройти по двусвязному списку, чтобы найти соответствующую страницу, но с помощью индекса соответствующую страницу можно найти через послойный «каталог».
Почему индекс дерева B+ замедляет скорость добавления, изменения и удаления
- B+ Tree — сбалансированное дерево, при добавлении, изменении или удалении дерева его первоначальная структура будет разрушена;
- Когда мы добавляем, изменяем и удаляем данные, нам нужно тратить дополнительное время на обслуживание индекса;
- Из-за этих дополнительных накладных расходов индекс будет замедлять скорость добавления, изменения и удаления.
Теперь вы понимаете, как работают индексы B+ Tree?
Последний вопрос для размышления:Почему официально рекомендуется использовать в качестве индексов самовозрастающие первичные ключи?Вы можете написать свой ответ в сообщении.
Дядя, который знает код | Текст [Оригинал]