Индекс — это структура данных, предназначенная для более быстрого запроса данных. В таблице с большим объемом данных создание хорошего индекса может значительно повысить производительность.
Disk io и читать дальше
Поскольку в базе данных хранится большой объем данных, хранить их в памяти для запросов невозможно, поэтому запрос данных неизбежно будет иметь дело с диском, поэтомуТолько поняв базовые знания о дисковом вводе-выводе и упреждающем чтении, мы можем по-настоящему понять принцип индексации.
Данные чтения диска зависят от механического движения.Время, необходимое для считывания данных каждый раз, можно разделить на три части: время поиска, задержка вращения и время передачи.Время поиска относится к времени, которое требуется магнитному рычагу для перемещения в указанную дорожку., основной диск обычно составляет менее 5 мс; задержка вращения - это скорость диска, которую мы часто слышим, например, диск 7200 об / мин, что означает, что он может вращаться 7200 раз в минуту, то есть он может вращаться 120 раз за 1 секунду, а задержка вращения составляет 1/120/2 = 4,17 мс; Время передачи относится ко времени чтения или записи данных с диска, как правило, в десятых долях миллисекунды, что незначительно по сравнению с первые два раза. Тогда время доступа к диску, то есть время одного дискового ввода-вывода, составляет около 5+4,17 = 9 мс, что звучит довольно неплохо, но вы должны знать, что машина со скоростью 500 MIPS может выполнять 500 миллионов инструкций в секунду, потому что инструкции основаны на Такова природа электричества, другими словами, за один ввод-вывод может быть выполнено 400 000 инструкций, а база данных легко может содержать 100 000 000 000 000 000 или даже 10 000 000 данных уровня, а каждые 9 миллисекунд — это, очевидно, катастрофа. Учитывая, что дисковый ввод-вывод является очень затратной операцией, операционная система компьютера сделала некоторые оптимизации, при выполнении ввода-вывода в буфер памяти считываются не только данные текущего адреса диска, но и соседние данные, т.к. Принцип упреждающего чтения говорит нам, что когда компьютер обращается к данным по адресу, соседние данные также будут доступны быстро. Данные, считываемые каждым IO, называются страницей. Количество данных на конкретной странице связано с операционной системой, обычно 4k или 8k, то есть, когда мы читаем данные на странице, фактически происходит только один ввод-вывод.
структура данных индекса
Я упоминал способ чтения данных с диска ранее, так как же наш индекс взаимодействует с этим способом для более быстрого поиска данных? Во-первых, нам нужно понять структуру данных индекса. Индекс, о котором мы здесь говорим, — это индекс B+TREE, потому что этот индекс используется чаще всего.На самом деле, у индекса также есть хеш-индекс, индекс пространственных данных и полнотекстовый индекс.
Во-первых, давайте разберемся со структурой данных B+TREE:
B+Tree — это многоканальное дерево поиска (не бинарное):
Определите, что любой нелистовой узел имеет не более M потомков и M>2;
Количество потомков корневого узла равно [2, M];
Количество сыновей нелистовых узлов, отличных от корневого узла, равно [M/2, M];
Каждый узел хранит не менее M/2-1 (с округлением вверх) и не более M-1 ключевых слов (не менее 2 ключевых слов)
Количество ключевых слов нелистовых узлов = количеству указателей на сыновей - 1;
Ключевые слова для нелистовых узлов: K[1], K[2], …, K[M-1] и K[i]
Указатели нелистовых узлов: P[1], P[2], …, P[M]; где P[1] указывает на поддерево с ключевым словом меньше K[1], а P[M] указывает на ключевое слово больше или равно Поддерево K[M-1], другие P[i] указывают на поддерево, ключ которого принадлежит [K[i], K[i+1]);
Все листовые узлы расположены на одном уровне;
Добавьте цепочку указателей ко всем листовым узлам;
Все ключевые слова появляются в листовых узлах;
Как показано на рисунке, это B-ДЕРЕВО с M, равным 3.
Особенности В+:
Все ключевые слова появляются в связанном списке листовых узлов (плотный индекс), а ключевые слова в связанном списке идут по порядку;
Невозможно попасть в нелистовой узел;
Нелистовой узел эквивалентен индексу (разреженному индексу) конечного узла, а листовой узел эквивалентен слою данных, в котором хранятся данные (ключевое слово);
Больше подходит для системы индексации файлов;
Анализ эффективности индекса B+TREE:
Глубина B+TREE не превышает O(log[M/2]N), и каждый узел на пути должен использовать временную сложность O(logM), чтобы определить, какая ветвь (используя бинарный поиск), вставка и удаление могут be Требуется O(M) работы, чтобы скорректировать всю информацию об узле, поэтому время выполнения вставки и удаления в наихудшем случае составляет O(Mlog[M]N), а каждый запрос стоит всего O(logN). Только что из временной сложности видно, что при запросе в памяти Mzuihaode выбирает 3 или 4, и скорость будет увеличиваться при ее увеличении. Но наши данные хранятся на диске, и затраты времени на увеличение M ничтожны по сравнению со временем, которое требуется для чтения памяти. В это время значение M выбирается как максимальное значение, которое внутренний узел может поместить в дисковый блок, поэтому диапазон значений M составляет [32, 256], так что, когда лист заполнен элементами, и лист заполнен, значит заполнен жесткий диск Блок заполнен. Это означает, что запись всегда можно найти при очень небольшом количестве обращений к диску, потому что глубина B-дерева в это время составляет всего 2 или 3, а корень может быть загружен непосредственно в память, поэтому общая скорость доступа будет высокой.
Итак, давайте еще раз посмотрим на картинку выше:
Если вы хотите найти элемент данных 30, то сначала с диска в память будет загружен блок диска 1. В это время происходит IO. В памяти используется двоичный поиск, чтобы определить, что 29 находится между 28 и 65, и заблокирован указатель P2 дискового блока 1. Поскольку время очень короткое (по сравнению с вводом-выводом диска), дисковый блок 3 загружается с диска в память через дисковый адрес P2 указатель дискового блока 1, и происходит второй IO, 30 между 28 и 35, заблокирован Указатель P2 дискового блока 3 загружает дисковый блок 8 в память через указатель, и происходит третий IO. в памяти выполняется бинарный поиск, чтобы найти 30, и запрос завершается, всего три операции ввода-вывода. Реальная ситуация такова, что трехслойное дерево b+ может представлять миллионы данных. Если для поиска миллионов данных требуется только три операции ввода-вывода, повышение производительности будет огромным. Если нет индекса, каждый элемент данных будет иметь операцию ввода-вывода. , тогда в общей сложности требуются миллионы операций ввода-вывода, очевидно, что стоимость очень и очень высока.
Стратегия высокопроизводительной индексации
независимый столбец
Некоторые запросы неправильно используют индексы, из-за чего Mysql не может использовать существующие индексы. Например, если столбцы в запросе не являются независимыми, Mysql не будет использовать индекс. Независимый столбец означает, что индекс не может быть частью выражения, а также не может быть параметром функции, например:
select app_id from app where app_id + 1 = 5;
MySQL не может разобратьapp_id + 1это выражение, поэтому индекс нельзя использовать.
Префиксные индексы и индексная избирательность
Иногда проиндексированные поля бывают особенно длинными, что делает индекс большим и медленным. В этом случае для индексации могут быть извлечены только первые несколько символов поля, что может сэкономить пространство индекса и повысить эффективность индекса, но это снизит избирательность индекса. Избирательность индекса относится к отношению уникального значения индекса (мощности) к общему количеству таблиц данных. Чем выше избирательность индекса, тем выше эффективность запроса, потому что индекс может помочь Mysql отфильтровать больше строк при поиске. Такие как первичные ключи и уникальные индексы, в настоящее время производительность является лучшей. Следовательно, при выборе длины индекса необходимо учитывать избирательность индекса, чтобы добиться оптимизации производительности.
многоколоночный индекс
Большинство из них не имеют достаточного понимания индексов, поэтому легко закоммитить следующие два:
Создайте независимые индексы для многих столбцов. Создание отдельных индексов для нескольких столбцов не улучшает производительность запросов Mysql. Mysql после 5.0 представил стратегию «слияния индексов», так что можно было сканировать несколько индексов с одним столбцом и объединять результаты. Существует три варианта этого алгоритма: условное объединение ИЛИ и условное пересечение И. В этом случае слияние результатов будет потреблять много ресурсов ЦП, и этот процесс оптимизации не входит в «стоимость запроса». Так что эти затраты будут занижены, а иногда эффективность даже ниже полного сканирования, и этот момент легко не заметить при оптимизации.
Многоколоночный индекс был создан в неправильном порядке. Если запрос не соответствует порядку индекса, это также приведет к тому, что Mysql не сможет использовать индекс. Есть несколько полезных принципов при создании многостолбцовых индексов: Сначала размещайте наиболее избирательные столбцы, независимо от сортировки и группировки. Но во многих случаях использовать его таким образом может быть нехорошо, и его все же необходимо оценивать в соответствии с конкретной ситуацией.
кластеризованный индекс
Кластерный индекс — это не отдельная форма индекса, а форма хранения данных Mysql в индексе B+TREE. Реализация кластерного индекса InnoDB хранит индексы B+TREE и строки данных в единой структуре, как показано на рисунке:
Кластерные индексы иногда могут быть полезны для производительности, но иногда они могут вызвать серьезные проблемы с производительностью. Ниже мы используем несколько изображений, чтобы отличить таблицу с некластеризованным индексом от таблицы с кластеризованным индексом:Данные таблицы некластеризованного индекса показаны выше.Граф индекса первичного ключа для таблицы некластеризованного индексаГраф индекса первичного ключа кластеризованного индекса
Как видно из приведенных выше рисунков, индекс первичного ключа некластеризованной индексной таблицы ничем не отличается от обычного индекса, он представлен непосредственно в виде указателя на расположение данных в индексе, но индекс первичного ключа таблицы с кластеризованным индексом — это «просто» a. Нет необходимости в отдельном хранении строк данных, как в некластеризованных индексных таблицах. Давайте посмотрим непосредственно на сравнительную таблицу двух:
Зная их отличия, давайте обсудим преимущества кластерных индексов:
Связанные данные можно хранить вместе, а все необходимые данные можно получить, прочитав лишь несколько страниц данных с диска при запросе.
Доступ к данным быстрый, потому что данные и индекс находятся вместе, поэтому запрос выполняется быстро.
Запросы, использующие сканирование покрывающего индекса, могут напрямую использовать значение первичного ключа конечного узла. Преимущество использования первичного ключа в качестве «указателя» для вторичного индекса (вторичного индекса) вместо использования значения адреса в качестве указателя заключается в том, что это сокращает работу по обслуживанию вторичного индекса при перемещении строки или страницы данных. Разделить Использование значения первичного ключа в качестве указателя приведет к тому, что вспомогательные индексы будут занимать больше места в обмен на то преимущество, что InnoDB не нужно обновлять этот «указатель» во вспомогательном индексе при перемещении строк. То есть положение строки будет меняться при изменении данных в базе данных (расщепление узла дерева B+ и разбиение страницы будут упомянуты позже в недостатках).Использование кластеризованного индекса может гарантировать, что независимо от того, как изменяется узел первичного ключа B+ дерева, вторичные индексные деревья не затрагиваются.
Давайте посмотрим на недостатки кластерных индексов:
Кластерные индексы не имеют преимуществ для данных, если все данные находятся в памяти.
Скорость вставки мало влияет при вставке в порядке первичного ключа, но когда он не добавляется в порядке, скорость будет затронута.После вставки используйте таблицу оптимизации для оптимизации таблицы, которая может обновлять статистику индекса и освободить неиспользуемый кластеризованный индекс Space.
Обновление кластеризованного индекса обходится дорого, поскольку InnoDB заставляет каждую обновленную строку перемещаться в новое место.
Таблица, основанная на кластеризованном индексе, может столкнуться с «проблемой разделения страниц» при вставке новой строки или при обновлении первичного ключа и необходимости перемещения строки. Когда строка вставляется в полную страницу, механизм хранения разделяет страницу на две страницы, чтобы вместить строку.Такая операция разделения страницы приведет к тому, что таблица займет больше места. Более того, это приведет к прерывистому хранению данных и разреженным строкам, а также к более медленному сканированию всего диска. Разделение страниц также приводит к большому перемещению данных, при этом вставка изменяет как минимум 3 страницы. При последовательной вставке редко возникает ситуация, когда необходимо изменить большое количество страниц.Самым узким местом в производительности являются накладные расходы на блокировку, когда первичный ключ автоматически увеличивается или уменьшается. Как показано на рисунке:Добавить по порядкуПри вставке неупорядоченных значений
Вторичные индексы (вторичные индексы) могут быть больше, чем ожидалось, поскольку конечные узлы вторичного индекса содержат столбцы, которые ссылаются на первичный ключ строки. И вторичный индекс требует двух поисков.
индекс покрытия
Покрывающий индекс относится к запросу, который содержит значения всех полей, которые необходимо запросить. Покрывающий индекс — очень полезный инструмент, который может значительно повысить эффективность, поскольку конечные узлы индекса уже содержат все необходимые данные, и нет необходимости читать строки данных. Его преимущества заключаются в следующем:
Записи индекса намного меньше, чем строки данных, поэтому, если вам нужно только прочитать индекс, MySQL может значительно сократить объем доступа к данным.
Поскольку индексы хранятся в порядке значений столбцов, для запросов диапазона с интенсивным вводом-выводом простой поиск индекса выполняется намного быстрее, чем обращение к жесткому диску для случайного запроса каждой строки данных.
Механизмы баз данных (такие как MyISAM) кэшируют только индексы в памяти, а кэши данных зависят от кэшей операционной системы, поэтому для доступа к данным требуются системные вызовы, которые могут вызвать серьезные проблемы с производительностью.
Упомянутый выше кластерный индекс особенно полезен при покрытии индекса.
Поскольку покрывающий индекс сохраняет значение столбца в индексе, область применения покрывающего индекса применима только к B+TREE.
сканирование индекса для сортировки
Сканирование самого индекса происходит быстро, потому что нужно переместить только одну запись индекса в следующую. Однако если индекс не может покрыть все столбцы запроса, то для соответствующей строки необходимо запросить только каждую запись индекса. В основном это случайный ввод-вывод, поэтому чтение данных в индексном порядке на самом деле медленнее, чем последовательное полное сканирование таблицы, особенно для рабочих нагрузок с интенсивным вводом-выводом.
Mysql может использовать индекс для сортировки результатов только тогда, когда порядок столбцов в индексе точно такой же, как порядок слов в порядке, и направление сортировки (вперед и назад) всех столбцов одинаково. Конечно, если крайний левый префикс уже является константой в условии where, предложение order by, удовлетворяющее самому левому префиксу, не обязательно.
Индексы и блокировки
Индексы позволяют запросам блокировать меньше строк. Например, если оператор for update, с которым мы столкнулись ранее, использует индекс первичного ключа, то будет заблокирована только одна строка, а остальные заблокируют таблицу. Во многих случаях при запросе блокируются только строки, найденные индексом, что может уменьшить накладные расходы на множество блокировок. Следует отметить еще одну деталь InnoDB: InnoDB использует разделяемые блокировки (блокировки чтения) для вторичных индексов (вспомогательных индексов), но эксклюзивные блокировки (блокировки записи) используются для доступа к индексам первичных ключей (фактически, это то, к чему мы стремились). работа над до Индекс с первичным ключом, встречающийся в этом примере, является блокировкой строки, но другие индексы являются блокировками таблицы). В этом случае ранее упомянутый покрывающий индекс (вторичный индекс для доступа к индексу первичного ключа) использовать нельзя, а использование для обновления происходит намного медленнее, чем совместное использование в режиме общего доступа или неблокирующий запрос.
небольшой совет
Оптимизация базы данных — очень важная задача. Во многих случаях нельзя допускать догматических ошибок. Самый важный способ — проверить, как оптимизировать ваши собственные операции. Очень вероятно, что оптимизация сработает при объеме данных 100M, но станет медленным запросом при 1G.В этом случае нужно думать, как избежать такой проблемы. База данных может хранить некоторые исторические данные в виде записей, но в большинстве случаев нам нужны свежие данные или несколько горячих данных.В этом случае нам нужно использовать кеш для завершения этой работы, а не слепо только базу данных. Это важно при разработке идей. Кроме того, индексы не всемогущи.Не стройте индексы без разбора.Иногда скорость будет ниже, а место будет потрачено впустую.При построении индекса следует подумать о необходимости и полезности этого индекса. Кроме того, оптимизация медленных запросов иногда не обязательно требует добавления индексов, во многих случаях цель оптимизации может быть достигнута за счет построения некоторых операторов. Вышеупомянутое содержание в основном взято из книги, которую я читал ранее, "Высокопроизводительная MySQL". Имея некоторые знания алгоритмов и собственный опыт, я пишу это здесь только для того, чтобы привлечь некоторые идеи. До оптимизации базы данных еще далеко. , Многие, я надеюсь учиться и делать успехи вместе с вами.