Многие друзья оставляли сообщения с вопросами о базовой реализации индексов MySQL, позвольте мне рассказать о деревьях B+. Зная правду и причину, разобраться в дереве B+ несложно, сегодня я больше расскажу об «индексе базы данных, почему он устроен именно так».
Вопрос 1. Зачем базам данных создавать индексы?
В библиотеке есть книги мощностью 1000 Вт. Чтобы найти "Дорогу архитектора", проверяйте их одну за другой. Когда вы хотите их проверить?
Итак, библиотекарь разработал свод правил:
(1) Классы истории расположены на первом этаже, классы литературы — на втором этаже, а классы информационных технологий — на третьем этаже…
(2) Категория ИТ, которая делится на категорию программного обеспечения, категорию оборудования...
(3) Категория программного обеспечения, отсортированная по названию...
быстро найти книгу.
По аналогии, в базе хранится 1000 Вт данных, чтобы найти записи с name="shenjian", проверяйте их одну за другой, когда вы их найдете?
Итак, естьпоказатель, который используется для улучшения скорости поиска базы данных.
Вопрос 2. Хэш (hash) быстрее, чем tree (дерево), зачем структуру индекса оформлять в виде дерева?
Существует два распространенных типа структур данных, которые ускоряют скорость поиска:
(1)хэш, таких как HashMap, средняя временная сложность запроса/вставки/изменения/удаления составляет O(1);
(2)Дерево, таких как сбалансированное двоичное дерево поиска, средняя временная сложность запроса/вставки/изменения/удаления составляет O(lg(n));
можно увидеть,Будь то запрос на чтение или запрос на запись, Индексы хэш-типа быстрее, чем индексы древовидного типа, так почему же структура индекса предназначена для древовидного типа?
Голос за кадром: 80% студентов не смогли ответить на интервью.
Индекс выполнен в виде дерева, что соответствует требованиям SQL.
для такогооднострочный запросТребования SQL:
выберите * из t, где имя = «shenjian»;
Это правда, что хэш-индекс быстрее, потому что за раз запрашивается только одна запись.
Голос за кадром: Итак, если бизнес требует однострочного доступа, такого как паспорт, вы действительно можете использовать хэш-индекс.
Но дляСортировать запросТребования SQL:
(1) Группировка: группировать по
(2) Сортировать: упорядочить по
(3) Сравнение:
(4)…
хэшТип индекс, он будет ухудшен с течением времени сложности O (n), а такжетип дерева«Упорядоченное» свойство по-прежнему поддерживает высокую эффективность O (log (n)).
Любое оформление, отклоняющееся от требований, является хулиганством.
Еще одна вещь: InnoDB не поддерживает создание хэш-индекса вручную.
Голос за кадром: Адаптивный хэш-индекс — это механизм ядра InnoDB.
Вопрос 3. Почему индексы баз данных используют деревья B+?
Чтобы сохранить целостность системы знаний, кратко представлены несколько видов деревьев.
Первый тип: бинарное дерево поиска
Двоичное дерево поиска, как показано на рисунке выше, является наиболее известной структурой данных, поэтому я не буду ее здесь представлять.Почему он не подходит для использования в качестве индекса базы данных?
(1) при большом объеме данных высота дерева будет относительно высокой, а при большом объеме данных запрос будет выполняться медленнее;
(2) Каждый узел хранит только одну запись, что может привести к большому количеству дисковых операций ввода-вывода для одного запроса;
Голос по поводу: Это дерево часто видно в учебниках в колледже, так что это самый известный.
Второй: B-дерево
B-дерево, как показано на рисунке выше, характеризуется:
(1) Это уже не бинарный поиск, а поиск m-fork;
(2) Листовые узлы и нелистовые узлы хранят данные;
(3) Обход по порядку, можно получить все узлы;
VoiceOver, я действительно не хочу вводить эту функцию: количество ключевых слов j, содержащихся в нерунтном узле, удовлетворены, (┌m / 2┐) -1 , это условие должно выполняться при разделении узла.
B-дерево было создано как структура данных для реализации индексов, потому что оно прекрасно использует «принцип локальности».
Что такое принцип локальности?
Логика принципа локальности такова:
(1) Блоки чтения и записи памяти, чтение и запись диска происходит медленно и намного медленнее;
(2)диск читать вперед: Дисковое чтение и запись не читаются по запросу, а считываются вперед постранично, за раз будет считываться одна страница данных, и каждый раз будет загружаться больше данных.Если данные, которые будут считаны в будущем, находятся на этой странице , этого можно избежать Будущий дисковый ввод-вывод, повысить эффективность;
Голос за кадром: Обычно одна страница данных ОС имеет размер 4K, MySQL Страница 16K.
(3)принцип локальности: дизайн программного обеспечения должен стараться следовать «концентрации чтения данных» и «использовать данные, данные рядом с ними будут использоваться с высокой вероятностью», чтобы упреждающее чтение с диска могло полностью улучшить дисковый ввод-вывод;
Почему B-дерево подходит для индексации?
(1) Поскольку он m-разветвлен, его высота может быть значительно уменьшена;
(2) Каждый узел может хранить записи J. Если размер узла установлен равным размеру страницы, например 4 КБ, функция упреждающего чтения может быть полностью использована, а дисковый ввод-вывод может быть значительно уменьшен;
Третий тип: B+ дерево
Дерево B+, как показано на рисунке выше, по-прежнему является m-арным деревом поиска.некоторые улучшения:
(1) Нелистовые узлы больше не хранят данные, а данные хранятся только на конечных узлах того же уровня;
Голос за кадром: Длина пути от корня до каждого узла в дереве B+ одинакова, чего нельзя сказать о дереве B.
(2) Между листьями добавляется связанный список для получения всех узлов, и обход по порядку больше не требуется;
Эти улучшения придают деревьям B+ лучшие свойства, чем деревья B:
(1) Поиск диапазона, после определения минимума и максимума, промежуточный листовой узел является набором результатов, обратный поиск по порядку не требуется;
Голос за кадром: Запросы диапазона часто используются в SQL, что является самым большим преимуществом деревьев B+ перед деревьями B.
(2) Листовой узел хранит фактическую строку записи, а строка записи хранится относительно компактно, что подходит для дискового хранилища большого объема; нелистовой узел хранит PK записи, который используется для ускорения запросов и подходит для хранения памяти;
(3) Если узел без листьев не хранит фактическую запись, но только хранит ключ от записи, затем в случае той же памяти, дерево B + может хранить больше индексов;
Наконец, количественно оценить,Почему высота m-разветвленного дерева B+ намного меньше высоты бинарного дерева поиска?
Рассчитайте примерно:
(1) Принцип локальности, размер узла устанавливается на одну страницу, одна страница составляет 4 КБ, при условии, что КЛЮЧ имеет 8 байтов, узел может хранить 500 КЛЮЧЕЙ, то есть j = 500;
(2) m-арное дерево, примерно m/2
(3) Тогда:
Одноуровневое дерево: 1 узел, 1*500 KEY, размер 4K
Двухуровневое дерево: 1000 узлов, 1000*500=50W ключей, размер 1000*4K=4M
Трехслойное дерево: 1000*1000 узлов, 1000*1000*500=500 миллионов ключей, размер 1000*1000*4K=4G
Голос за кадром: Эм, помогите мне увидеть, нет ли ошибки.
Видно, что для хранения большого количества данных (500 миллионов) не требуется очень большая глубина дерева (высота 3), а индекс не занимает слишком много памяти (4G).
Суммировать
(1) индексы базы данных используются для ускорения запросов;
(2) Хотя хэш-индекс равен O(1), а индекс дерева равен O(log(n)), в SQL есть много «упорядоченных» требований, поэтому база данных использует индекс дерева;
(3) InnoDB не поддерживает ручное создание хэш-индексов;
(4) Предварительное чтение данныхИдея такова: чтение и запись на диск не читаются по требованию, а считываются вперед по страницам, за раз будет считываться одна страница данных, и каждый раз будет загружаться больше данных, чтобы в будущем уменьшить дисковый ввод-вывод.
(5) Принцип локальности: дизайн программного обеспечения должен стараться следовать «концентрации чтения данных» и «использовать данные, данные рядом с ними будут использоваться с высокой вероятностью», чтобы упреждающее чтение диска могло полностью улучшить дисковый ввод-вывод.
(5) Наиболее часто используемое дерево B+ для индексов баз данных:
- Очень подходит для дискового хранилища, может в полной мере использовать принцип локальности, упреждающее чтение диска;
- Очень низкая высота дерева, способная хранить большие объемы данных;
- сам индекс занимает очень мало памяти;
- Может хорошо поддерживать одноточечный запрос, запрос диапазона, упорядоченный запрос;
Путь архитектора- Делитесь практическими статьями об архитектуре
связанное предложение: \
"Параллелизм InnoDB настолько высок, почему это?》
Операция:\
Это также дерево B+ В чем разница между индексами InnoDB и MyISAM?
Идея важнее, чем вывод, надеюсь, у вас есть урожай, спасибо.