Индекс баз данных, которые играли с интервьюерами на протяжении многих лет

база данных
Индекс баз данных, которые играли с интервьюерами на протяжении многих лет

Я сел напротив интервьюера и эмоционально представился, а младший брат интервьюера посмотрел на мое резюме с пустым выражением лица. Я не знаю, то ли мой младший брат слишком холоден, то ли привлечен моим резюме, спустя 2 минуты мой младший брат все еще не сказал мне ни слова.嘤嘤嘤~ Кажется, хитов два. Но это не имеет значения, все это не имеет значения.

Что такое индекс?

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

(Что можно спросить об индексе, это не что иное, как понятие индекса, правила использования индекса, классификация индекса, принцип работы индекса. Хи хи ~ я уже подготовил) Я:Простыми словами, индекс в базе данных похож на каталог книги: он может помочь нам быстро находить и искать определенные значения, тем самым повышая эффективность запроса данных.

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

Интервьюер:Итак, как вы говорите, чем больше индексов, тем лучше?

Чем больше индексов, тем лучше?

Я:Конечно, чем больше индексов, тем лучше, а индексы не всесильны, в некоторых случаях использование индексов снижает эффективность.

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

В случае, если количество строк данных в таблице данных относительно невелико, например менее 1000 строк, нет необходимости создавать индекс. Кроме того, при большом повторении данных, например более 10 %, нет необходимости использовать индекс для этого поля.

Например, если в поле указан пол, нет необходимости создавать для него индекс. Почему это? Если вы хотите найти 500 000 строк в 1 миллионе строк данных (например, пол — это данные о мужчинах), после создания индекса вам нужно посетить индекс 500 000 раз, а затем посетить таблицу данных 500 000 раз, поэтому добавьте накладные расходы может быть больше, чем без использования индекса.

вид индекса

Интервьюер кивнул и, похоже, был удовлетворен моим ответом выше. Затем спросил:

Интервьюер:Итак, о каких типах индексов вы говорите?

(Хи-хи, я слишком знаком с типами индексов. Но я все же начинаю свой ответ после небольшой паузы.)

Классификация по функциональной логике

Я:С точки зрения функциональной логики существует четыре основных типа индексов, а именно:普通索引、唯一索引、主键索引和全文索引.

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

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

индекс первичного ключаНа основе уникального индекса добавляется ненулевое ограничение, то есть NOT NULL+UNIQUE, и в таблице может быть не более одного индекса первичного ключа.

полный текстовый указательМало используется, собственный полнотекстовый индекс MySQL поддерживает только английский язык. Обычно мы можем использовать специализированные системы полнотекстового поиска, такие как ES (ElasticSearch) и Solr.

На самом деле, первые три индекса (общий индекс, уникальный индекс и индекс первичного ключа) являются своего рода индексами, но ограничения на данные постепенно улучшаются.

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

Классификация по физической реализации

Я:По физической реализации индексы можно разделить на 2 типа:聚集索引和非聚集索引. Мы также называем некластеризованный индекс二级索引或者辅助索引.

кластеризованный индексДанные можно сортировать и хранить по первичному ключу, что очень эффективно при поиске строк.

Например, если это китайский словарь, если мы хотим найти слово «число», мы можем напрямую найти положение китайского пиньинь в книге, то есть пиньинь «шу». Это находит положение индекса, а после него строку данных, которую мы хотим найти.

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

Возьмем также китайский словарь в качестве примера.Если вы хотите найти слово "число", то по методу подкоренного поиска сначала найдите корень слова "число", а потом этот справочник подскажет нам число сохранено слово «номер» страницы, мы переходим к указанному номеру страницы, чтобы найти это слово.

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

Различия между кластеризованными и некластеризованными индексами

На самом деле ответа на вышеизложенное достаточно, но для того, чтобы показать свое понимание, я также сделал следующее уточнение:

Я:Принцип кластерного индекса отличается от принципа некластеризованного индекса, и есть некоторые различия в использовании:

  1. Листовые узлы кластеризованного индекса хранят наши записи данных, а конечные узлы некластеризованного индекса хранят расположение данных. Некластеризованные индексы не влияют на физический порядок хранения таблиц данных.

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

  3. При использовании кластеризованного индекса эффективность запроса данных высока, но если данные вставляются, удаляются, обновляются и т. д., эффективность будет ниже, чем у некластеризованного индекса.

структура данных индекса

Интервьюер:Вы только что объяснили классификацию индексов с точки зрения функциональной логики и физической реализации. Кажется, вы хорошо понимаете структуру данных индексов. Расскажите мне об известных вам структурах данных индексов.

(Это легко, я выпалил)

Я:Хэш, B-дерево и B+-дерево могут использоваться в качестве индексных структур данных, но в MySQL используется B+-дерево, и B+-дерево также является нашей часто используемой индексной структурой данных.

Почему мы часто используем дерево B+ в качестве индексированной структуры данных?

Интервьюер:Почему мы часто используем дерево B+ в качестве индексированной структуры данных? Разве другие древесные структуры не пахнут?

(Я знал, что это не так просто. Увы, почему я только сейчас упомянул слово «обычно употребляемый»? Я не мог не плакать про себя, но все же старался сохранять самообладание.) Я:Прежде чем ответить на этот вопрос, позвольте мне рассказать о месте хранения индекса и критериях оценки дизайна структуры данных индекса.

место хранения индекса

Я:Мы знаем, что сервер базы данных имеет два носителя данных, а именножесткий дискиОЗУ. Память относится к временному хранилищу.При возникновении аварии, такой как сбой питания или сбой перезагрузки, данные будут потеряны; жесткий диск эквивалентен постоянному носителю данных, и данные могут быть постоянными, поэтому нам необходимо сохранять данные в жесткий диск.

Как оценить качество проектирования индексной структуры данных?

Я:Хотя скорость чтения из памяти высока, нам все равно нужно хранить индекс на жестком диске. Следовательно, когда мы запрашиваем жесткий диск, также генерируется операция ввода-вывода жесткого диска.

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

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

бинарное дерево

Интервьюер кивнул и дал мне сигнал продолжать. Чтобы дать удовлетворительный ответ на вопрос «Почему мы часто используем B+ дерево в качестве индексированной структуры данных», я взял ручку и начал с бинарного дерева, а интервьюер остановился. . Я:Далее поговорим о двоичном дереве. Мы знаем, что метод бинарного поиска является эффективным методом поиска данных. Временная сложность O (log2n). Можно сказать, что скорость поиска очень высока.

Взяв в качестве примера самое простое бинарное дерево поиска (Binary Search Tree), правила поиска узла и вставки узла одинаковы, мы предполагаем, что значение, вставленное в поиск, является ключом:

  1. Если ключ больше, чем корневой узел, ищите в правом поддереве;
  2. Если ключ меньше корневого узла, искать в левом поддереве;
  3. Если ключ равен корневому узлу, то есть узел найден, и можно вернуть корневой узел.

Например, бинарное дерево поиска, которое мы создали для серии журналов (25, 18, 36, 9, 20, 32, 41), показано ниже:

Но есть частные случаи, когда глубина бинарного дерева будет очень большой. Например, мы даем последовательность данных (9, 18, 20, 25, 32, 36, 41), а созданное бинарное дерево поиска показано на следующем рисунке:

Теперь это дерево также является бинарным деревом поиска, но производительность выродилась в связанный список, а временная сложность поиска данных стала O(n).

Мы видим, что глубина первого дерева равна 3, что означает, что для нахождения узла необходимо не более 3 сравнений, тогда как глубина второго дерева равна 7, что требует не более 7 сравнений для нахождения узла.

Сбалансированное бинарное дерево поиска

Интервьюер:Поскольку обычные бинарные деревья не работают, как насчет сбалансированных бинарных деревьев поиска? Потому что мы знаем, что это может предотвратить вырождение структуры данных в связанный список в особых случаях путем ротации.

Я:Как я только что упомянул, время запроса данных в основном зависит от количества дисковых операций ввода-вывода.Даже если используется улучшенное сбалансированное двоичное дерево поиска, глубина дерева составляет O(log2n).Когда n относительно велико, глубина также относительно велика, например, как на следующем рисунке:

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

Что такое B-дерево?

Я:Для тех же данных выше, если мы изменим двоичное дерево на M-арное дерево (M > 2), когда M = 3, те же 31 узел могут быть сохранены следующим троичным деревом:

Вы можете видеть, что высота дерева в это время уменьшается.Когда количество данных N велико и количество ветвей M дерева велико, высота M-арного дерева будет намного меньше, чем высота бинарного дерева.

Если в качестве структуры реализации индекса используется двоичное дерево, дерево станет очень высоким, количество операций ввода-вывода на жестком диске будет увеличено, и это повлияет на время запроса данных. Поэтому узел не может иметь только 2 дочерних узла, но должен допускать M дочерних элементов (M>2).

Появление B-дерева призвано решить эту проблему.Английское название B-дерева — это Balance Tree, представляющее собой сбалансированное многоходовое дерево поиска.Его высота намного меньше, чем у сбалансированного бинарного дерева. Структуры индексов в файловых системах и системах баз данных часто реализуются с использованием B-деревьев.

Структура B-дерева показана на следующем рисунке:

В сбалансированном многоканальном дереве поиска каждый узел B-дерева может включать в себя не более M дочерних узлов, а M называется порядком B-дерева. В то же время вы можете видеть, что каждый блок диска включает в себя ключ и указатель на дочерний узел. Если блок диска содержит x ключевых слов, то число указателей равно x+1. Для B-дерева 100-го порядка, если есть 3 слоя, оно может хранить до 1 миллиона данных индекса. Для большого количества индексных данных очень подходит структура B-дерева, потому что высота дерева намного меньше, чем высота бинарного дерева.

B-дерево порядка M (M>2) обладает следующими свойствами:

  1. Диапазон количества дочерних элементов корневого узла составляет [2,M].
  2. Каждый промежуточный узел содержит k-1 ключевых слов и k дочерних элементов, количество дочерних элементов = количеству ключевых слов + 1, а диапазон значений k равен [ceil(M/2), M].
  3. Конечные узлы включают k-1 ключевых слов (конечные узлы не имеют дочерних элементов), а диапазон значений k равен [ceil(M/2), M].
  4. Предположим, что ключевыми словами промежуточных узлов являются: Key[1], Key[2], …, Key[k-1], и ключевые слова отсортированы по возрастанию, то есть Key[i]
  5. Все листовые узлы находятся на одном уровне.

B-дерево, представленное на рисунке выше, является B-деревом порядка 3. Можем посмотреть блок диска 2, ключ в нем (8, 12), у него 3 потомка (3, 5), (9, 10) и (13, 15), видно (3, 5) ) меньше 8, (9, 10) находится между 8 и 12, а (13, 15) больше 12, как раз в соответствии с характеристиками, которые мы только что дали.

Тогда давайте посмотрим, как использовать B-дерево для поиска. Предположим, что ключевое слово, которое мы хотим найти, равно 9, тогда шаги можно разделить на следующие шаги:

  1. Сравниваем его с ключом (17, 35) корневого узла и, если 9 меньше 17, получаем указатель P1;
  2. Найдите блок диска 2 по указателю P1, ключ (8, 12), потому что 9 находится между 8 и 12, поэтому мы получаем указатель P2;
  3. Находим дисковый блок 6 по указателю P2, ключ (9, 10), а затем находим ключ 9.

Мы видим, что в процессе поиска B-дерева мы сравниваем много раз, но если данные считываются и сравниваются в памяти, это время ничтожно мало.

Чтение самого блока диска требует операции ввода-вывода, которая занимает больше времени, чем сравнение в памяти, что является важным фактором во времени поиска данных.По сравнению со сбалансированным двоичным деревом, B-дерево - это дисковый ввод-вывод.Меньше операций и более эффективен, чем сбалансированное двоичное дерево в запросе данных.

Что такое дерево B+?

Я:Наконец, давайте поговорим о дереве B+. Дерево B+ — это усовершенствование, основанное на дереве B. Основные СУБД поддерживают метод индексирования дерева B+, например MySQL. Разница между деревом B+ и деревом B заключается в следующих моментах:

  1. Узел с k дочерними элементами имеет k ключей. То есть количество дочерних элементов = количеству ключевых слов, а в дереве B количество дочерних элементов = количеству ключевых слов + 1.
  2. Ключевые слова нелистовых узлов также существуют в дочерних узлах и являются наибольшими (или наименьшими) из всех ключевых слов в дочерних узлах.
  3. Неконечные узлы используются только для индексации и не сохраняют записи данных.Информация, относящаяся к записям, размещается в конечных узлах. В B-дереве неконечные узлы содержат как индексы, так и записи данных.
  4. Все ключевые слова появляются в листовых узлах, листовые узлы образуют упорядоченный связанный список, а сами листовые узлы связаны в порядке возрастания в соответствии с размером ключевых слов.

На следующем рисунке показано дерево B+ с порядком 3. Ключевые слова 1, 18 и 35 в корневом узле являются дочерними узлами (1, 8, 14), (18, 24, 31) и (35, 41, 53). ) соответственно. ) минимальное значение. Ключевые слова родительского узла каждого слоя появятся в ключевых словах дочерних узлов следующего слоя, поэтому вся информация о ключевых словах включена в конечные узлы, и каждый конечный узел имеет указатель на следующий узел, так что A формируется связанный список.

Например, если мы хотим найти ключевое слово 16, дерево B+ будет искать сверху вниз слой за слоем:

  1. Сравните с ключом (1, 18, 35) корневого узла, 16 находится между 1 и 18, получите указатель P1 (указывающий на блок диска 2)
  2. Найдите блок диска 2, ключ (1, 8, 14), потому что 16 больше, чем 14, поэтому получите указатель P3 (указывающий на блок диска 7)
  3. Найдите дисковый блок 7, ключевое слово (14, 16, 17), а затем мы найдем ключевое слово 16, чтобы мы могли найти данные, соответствующие ключевому слову 16.

Интервьюер:Всего за весь процесс дерева B+ выполняется 3 операции ввода-вывода.Похоже, что процесс запроса дерева B+ и дерева B похож, так почему же мы чаще используем дерево B+?

Я:Фундаментальное различие между B+-деревом и B-деревом заключается в том, что промежуточные узлы B+-дерева не хранят данные напрямую. Преимущества этого:

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

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

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

(Кстати говоря, я доволен и плакать хочется, и не забыл подвести итоги)

Как правило, количество операций ввода-вывода на диск имеет решающее значение для эффективности использования индекса. Хотя традиционная структура данных двоичного дерева эффективна при поиске данных, легко увеличить количество дисковых операций ввода-вывода и повлиять на эффективность использования индекса. Поэтому при построении индекса мы предпочитаем использовать «объемную» структуру данных.

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

Интервьюер взял стоявший рядом с ним холодный кофе и сделал глоток.

(У этой маленькой девочки что-то есть)

«Постоянно обновляется……»

Любимая Троица 💖

Наконец, спасибо за чтение. Цель статьи — зафиксировать и поделиться, если в статье есть явные ошибки, пожалуйста, указывайте на них, и мы будем учиться вместе в ходе обсуждения. Большое тебе спасибо !

Если вы считаете, что эта статья полезна для вас, то поставьте лайк, ваша поддержка и поддержка являются для меня движущей силой двигаться вперед~

Добро пожаловать в мой публичный аккаунт WeChat [Backend Program Yuan], давайте вместе обсудим код и жизнь.

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

Ссылка на статью

  1. «Структуры данных и алгоритмы»;
  2. Geek Time: SQL нужно знать и нужно знать.