задний план
Полагаю, что про индексы при оптимизации БД будет говорить каждый, и я не исключение.В принципе каждый может ответить на раз, два, три про оптимизацию структуры данных, а также кэширование страниц и т.д., но один раз Интервью на Ali P9 спросил меня: Можете ли вы рассказать о процессе загрузки индексных данных с уровня компьютера? (Просто хотел, чтобы я рассказал об IO)
Я умер на месте ... потому что базовые знания компьютерных сетей и операционных систем действительно мое слепое пятно, но я наверстаю это позже, не так много глупостей, давайте начнем с загрузки данных компьютером и поговорим о другом ракурсе Индекс чата.
текст
Индекс MySQL - это, по сути, структура данных
Давайте сначала рассмотрим загрузку данных для компьютеров.
Дисковый ввод-вывод и читайте дальше:
Давайте сначала поговорим о дисковом вводе-выводе.Диск считывает данные механическим движением.Каждый раз, когда вы читаете данные, вам нужноИщи, указывай, копируй в памятьТрехступенчатая операция.
искатьВремя — это время, необходимое магнитному манипулятору для перемещения на указанную дорожку, обычно менее 5 мс;
найти точкуЭто найти точку, где существуют данные из дорожки.Среднее время составляет половину времени круга.Если это диск 7200 об / мин, среднее время поиска точки составляет 600000/7200/2 = 4,17 мс;
скопировать в памятьВремя очень быстрое, и его можно игнорировать по сравнению с предыдущими двумя временами, поэтомуСреднее время второго ввода-вывода составляет около 9 мс.. Звучит очень быстро, но миллионы данных в базе данных достигают 9000 с после одного прохода, что, очевидно, является катастрофическим уровнем.
Учитывая, что дисковый ввод-вывод — очень затратная операция, операционная система компьютера оптимизировала упреждающее чтение, при выполнении которого не только данные текущего адреса диска, но исмежные данныеОни также считываются в буфер памяти, потому что, когда компьютер обращается к данным по адресу, соседние данные также будут доступны быстро.
Данные, считываемые каждым IO, называются страницей, а размер данных на конкретной странице связан с операционной системой, обычно 4k или 8k, то есть, когда мы читаем данные на странице, это действительно происходит. ИО.
(Внезапно я вспомнил вопрос, который мне задали сразу после выпуска. Сколько байт в 64-битной операционной системе занимает тип int в Java? Каков максимум? Почему?)
Затем мы хотим оптимизировать запрос к базе данных, нам нужноСвести к минимуму операции дискового ввода-вывода, так что есть индекс.
Что такое индекс?
MySQLОфициальное определение индекса: Index (Индекс) должен помочьMySQLСтруктуры данных для эффективного извлечения данных.
MySQL Есть два типа индексов, обычно используемых в B-дереве, индексы B-дерева и хэш-индексы.
Эта основная лекцияBTreeпоказатель.
Индекс BTree
BTreeM-разветвленное дерево BTree, также известное как многостороннее сбалансированное дерево поиска, имеет следующие характеристики:
- Каждый узел дерева содержит не более m потомков.
- За исключением корневого узла и листовых узлов, каждый узел имеет не менее [ceil(m/2)] дочерних элементов (ceil() округляется в большую сторону).
- Если корневой узел не является конечным узлом, он должен иметь не менее двух дочерних элементов.
- Все листовые узлы находятся на одном уровне.
- Каждый нелистовой узел состоит из n ключей и n+1 указателей, где [ceil(m/2)-1]
Это 3-форк (просто пример, в реальности будет много форков) Схема структуры BTree, каждый блок называется дисковым блоком или блочным блоком, это то, что операционная система считывает в память за один IO, блок соответствует четырем секторам, фиолетовый представляет ключ данных в блоке диска, желтый представляет данные данных, а синий представляет указатель p, указывающий на позицию следующего блока диска.
Для имитации процесса поиска данных с ключом 29:
1. Прочитайте блок корневого диска 1 каталога файлов в соответствии с указателем корневого узла. [Операция дискового ввода-вывода1 раз】
2. Дисковый блок 1 хранит 17, 35 и три указателя данных. Мы находим 17
3. По указателю p2 находим и читаем дисковый блок 3. [Операция дискового ввода-вывода2 раза】
4. Дисковый блок 3 хранит 26, 30 и три указателя данных. Мы находим, что 26
5. По указателю p2 находим и читаем блок диска 8. [Операция дискового ввода-вывода3 раза】
6. 28 и 29 хранятся в дисковом блоке 8. Находим 29 и получаем данные, соответствующие 29.
Можно видеть, что индекс BTree заставляет каждый дисковый ввод-вывод, извлеченный в память, играть роль, тем самым повышая эффективность запросов.
Но можно ли что-то оптимизировать?
Из рисунка видно, что каждый узел содержит не только значение ключа данных, но и значение данных. Место для хранения каждой страницы ограничено.Если данные данных велики, количество ключей, которые могут быть сохранены каждым узлом (т. е. страницей), будет очень маленьким.Когда объем хранимых данных велик, он также будет приводят к B- Глубина дерева велика, что увеличивает количество дисковых операций ввода-вывода во время запроса, тем самым влияя на эффективность запроса.
B+древовидный индекс
B+TreeвB-TreeОсновываясь на оптимизации, он больше подходит для реализации структуры индексов внешнего хранилища. В B+Tree все узлы записи данных хранятся на листовых узлах того же слоя в порядке размера значения ключа, а на нелистовых узлах хранится только информация о значении ключа, что может значительно увеличить количество значений ключа. хранится в каждом узле. , уменьшите высоту B+Tree.
Между B+Tree и B-Tree есть несколько различий:
Неконечные узлы хранят только информацию о ключе-значении, а записи данных хранятся в конечных узлах.B-дерево в предыдущем разделе оптимизировано.Поскольку неконечные узлы B+Tree хранят только информацию о ключе-значении, высота B+Tree может быть сжата до исключительно низкого уровня.
Конкретные данные следующие:
Размер страницы в механизме хранения InnoDB составляет 16 КБ, тип первичного ключа общей таблицы — INT (занимает 4 байта) или BIGINT (занимает 8 байт), а тип указателя также обычно составляет 4 или 8 байтов, т. е. сказать, что около 16 КБ / (8B + 8B) = 1K ключевых значений хранятся на странице (узел в B + Tree) (поскольку это оценка, для удобства расчета значение K здесь 〖 10〗^3).
Другими словами, индекс B+Tree с глубиной 3 может содержать 10^3 * 10^3 * 10^3 = 1 миллиард записей. (В этом методе расчета есть ошибка, и листовые узлы не рассчитываются. Если листовые узлы вычисляются, глубина на самом деле равна 4)
Нам нужно выполнить только три операции ввода-вывода, чтобы найти нужные данные из 1 миллиарда фрагментов данных, что намного лучше, чем исходные 9000 секунд миллионов данных.
И обычно в B+Tree есть два указателя на голову, один указывает на корневой узел, другой указывает на конечный узел с наименьшим ключевым словом, и между всеми конечными узлами (то есть узлами данных) существует кольцевая структура. Следовательно, в дополнение к поиску по диапазону и поиску по страницам первичного ключа B+Tree, мы также можем начать с корневого узла и выполнить случайный поиск.
Индекс B+Tree в базе данных можно разделить на кластеризованный индекс и вторичный индекс.
Реализация приведенной выше примерной диаграммы B+Tree в базе данных представляет собой кластеризованный индекс.Листовые узлы в B+Tree кластеризованного индекса хранят данные записи строки всей таблицы.Разница между вспомогательным индексом и кластеризованным индексом лежит в листьях вспомогательного индекса.Узел не содержит все данные записи строки, а хранит ключ кластеризованного индекса соответствующих данных строки, то есть первичный ключ.
При запросе данных через вторичный индекс механизм хранения InnoDB просматривает вторичный индекс, чтобы найти первичный ключ, а затем использует первичный ключ, чтобы найти полные данные записи строки в кластеризованном индексе.
Однако, несмотря на то, что индексы могут ускорить выполнение запросов и повысить производительность обработки MySQL, чрезмерное использование индексов также может привести к следующим последствиям:недостатки:
- Создание и поддержка индексов требует времени, и это время увеличивается с увеличением объема данных.
- В дополнение к пространству данных, занимаемому таблицей данных, каждый индекс также занимает определенное количество физического пространства. Если вы хотите создать кластеризованный индекс, потребуется больше места.
- При добавлении, удалении и изменении данных в таблице индекс также поддерживается динамически, что снижает скорость обслуживания данных.
Примечание. В некоторых случаях индексы могут ускорить выполнение запросов, но в некоторых случаях снизить эффективность.
Индексирование — это только один из факторов повышения эффективности, поэтому при создании индексов следует придерживаться следующих принципов:
- Индексирование часто используемых столбцов может ускорить поиск.
- Создайте индекс для столбца, который является первичным ключом, обеспечивайте уникальность столбца и организуйте расположение данных в таблице.
- Создайте индексы для столбцов, которые часто используются при объединении таблиц. Эти столбцы в основном представляют собой некоторые внешние ключи, которые могут ускорить соединение таблиц.
- Создайте индекс для столбца, который часто необходимо искать на основе диапазона, поскольку индекс уже отсортирован, так что его указанный диапазон является непрерывным.
- Создайте индекс для столбца, который часто необходимо сортировать.Поскольку индекс уже отсортирован, сортировку индекса можно использовать в запросе для ускорения запроса сортировки.
- Создавайте индексы для столбцов, в которых часто используется предложение WHERE, чтобы ускорить условное суждение.
Теперь все знают, почему индекс может быть таким быстрым.На самом деле это приговор.Через структуру индекса можно минимизировать количество IOs базы данных.Ведь время одного IO действительно слишком велико. . .
Суммировать
Что касается интервью, многие знания на самом деле можно легко освоить, но для целей обучения вы найдете много вещей.Мы должны углубиться в основы компьютеров, чтобы раскрыть тайны.Многие люди спрашивают мне, как запомнить так много вещей, На самом деле, обучение само по себе очень беспомощная вещь. Поскольку мы должны учиться, почему бы не учиться усердно? Научиться получать от этого удовольствие? В последнее время тоже наверстываю азы, а в будущем начну обновлять знания по основам работы с компьютером и сетями.
Я Ао Бин, чем больше ты знаешь, тем больше ты не знаешь, увидимся в следующий раз!
талантнаш【Три подряд】Это самая большая движущая сила для создания Ao Bing.Если в этом блоге есть какие-либо ошибки и предложения, вы можете оставить сообщение!
Статья постоянно обновляется, вы можете искать в WeChat "Третий принц Ао Бин"Прочтите это в первый раз, ответьте [материал] Подготовленные мной материалы интервью и шаблоны резюме крупных заводов первой линии, эта статьяGitHub github.com/JavaFamilyОн был включен, и есть полные тестовые сайты для интервью с крупными заводами.Добро пожаловать в Star.