Ставьте лайк и смотрите снова, формируйте привычку, ищите в WeChat【Третий принц Ао Бин] Все мои статьи здесь, эта статьяGitHub github.com/JavaFamilyОн был включен, есть полный тестовый сайт для интервью с крупными заводами первой линии, а в конце статьи естьБлагосостояние.
предисловие
При написании базы данных я сразу подумал о MySQL, Oracle, индексах, хранимых процедурах, оптимизации запросов и так далее.
Я не знаю, если все думают так же, как я, больше всего я хочу написать индекс, почему?
Следующая сцена интервью, я не знаю, знакомы ли вы с ней:
Интервьюер: В базе данных десятки миллионов данных, а запрос выполняется очень медленно, что нам делать?
Интервьюер: Добавьте index.
Интервьюер: Какие типы данных есть в индексе? Какова структура индекса? Какие поля подходят для индексации? Преимущества В+? В чем разница между кластеризованным индексом и неагрегированным индексом? Почему индексы замедляют выполнение таких задач обслуживания, как вставка, удаление и модификация? ……..
Интервьюер: Почему интервьюер ушел из нашей компании?
Да, все могут знать, что добавление индекса происходит медленно, так зачем его добавлять, какое поле добавлять, а характеристики структуры данных индекса, преимущества и так далее относительно туманны или даже неизвестны.
Тогда у нас не так много ББ, давайте начнем это интервью напрямую.
текст
Я вижу в вашем резюме, что вы знакомы с базами данных и индексами MySQL.Начнем с индексов.Какие структуры данных индексов?
Хэш, B+
При разработке индекса вы обнаружите, что тип индекса можно выбрать.
Почему хеш-таблицы, полностью сбалансированные двоичные деревья, B-деревья и B+-деревья могут оптимизировать запросы и почему Mysql предпочитает B+-деревья?
Позвольте мне сначала поговорить о Hash:
Вы можете посмотреть анимацию ниже
Обратите внимание, что индекс массива, соответствующий значению поля, вычисляется случайным образом алгоритмом хеширования, поэтому он может выглядетьхэш-коллизия.
Итак, для такой структуры индекса теперь выполните следующую инструкцию sql:
выберите * из sanguo, где имя = 'яйцо'
Вы можете напрямую вычислить индекс массива на «яйце» в соответствии с алгоритмом хеширования, а затем вы можете напрямую извлечь данные из данных и получить адрес соответствующей строки данных, а затем запросить эту строку данных, тогда, если вы выполняете следующий оператор sql сейчас:
выберите * из sanguo, где имя> «яйцо»
ничего не может сделать, потому что характеристики хеш-таблицыМожет быть быстрым и точным запросом, но не поддерживает запрос диапазона.
Если делать индекс, то скорость тоже очень медленная, и надо все сканировать.
В качестве отступления, в каких сценариях больше подходят хэш-таблицы?
В случае эквивалентного запроса есть только случай KV (Key, Value), такой как Redis, Memcached и другое промежуточное ПО NoSQL.
Вы говорите о неупорядоченной хеш-таблице, существует ли упорядоченная структура данных?
отсортированный массив, это лучше, это очень приятно в эквивалентном запросе и запросе диапазона.
У него вообще нет недостатков?
Нет, упорядоченный подходит для статических данных, потому что если мы будем добавлять, удалять и изменять данные, они изменят свою структуру.
Например, если вы добавите новую, все узлы за новой добавленной позицией будут перемещены назад, что очень дорого.
Тогда по тому, что вы сказали, он совсем нехорош, и его характеристики некуда ставить.
Его можно использовать в качестве статического механизма хранения для хранения статических данных, таких как ваши счета Alipay в 2019 году, записи о покупках Taobao в 2019 году и т. д., которые очень подходят, все из которых являются историческими данными, которые не изменятся.
Что-то, чувак, как насчет бинарного дерева?
Дополнение и структура бинарного дерева показаны на рисунке:
Структура бинарного дерева Я не буду здесь больше ББ, друзья, которые не понимают, могут перейти к главе структуры данных.
Двоичные деревья упорядочены, поэтому поддерживаются запросы диапазона.
Но его временная сложность равна O(log(N)). Чтобы сохранить эту временную сложность, временная сложность обновления также должна быть O(log(N)), поэтому дерево должно храниться как полностью сбалансированное двоичное дерево.
Как я могу услышать, что вы говорите, что сбалансированное двоичное дерево неплохо для индексации?
Это плохо.Индекс не только хранится в памяти, но и должен сохраняться на диск.Вы можете видеть, что данных на рисунке ровно столько.Если данных слишком много, то высота дерева будет очень высока, и стоимость запроса будет увеличиваться с увеличением высоты дерева.
В целях экономии многие компании до сих пор используют механические жесткие диски.Такой запрос десятков миллионов уровней занимает около 10 секунд.Кто это выдержит?
Что делать, если используются B-деревья?
Точно так же давайте взглянем на структуру B-дерева:
Можно обнаружить, что представление B-дерева «короче», чем полностью сбалансированное двоичное дерево для тех же элементов, потому что узел в B-дереве может хранить несколько элементов.
На самом деле B-дерево уже является хорошей структурой данных, и эффект от индексации все еще хорош.
Тогда почему использовались не B-деревья, а B+-деревья?
Давайте сначала посмотрим на структуру B plus:
Мы можем обнаружить, что для одних и тех же элементов представление дерева B+ является «толстым», чем дерево B, потому что нелистовые узлы в дереве B+ будут иметь избыточную копию в конечных узлах, а листовые узлы связаны по указателям.
Итак, каковы преимущества деревьев B+?
На самом деле это очень просто. Давайте посмотрим на структуру данных выше. Исходный хэш не поддерживает диапазонные запросы. Высота бинарного дерева очень большая. Только дерево B сравнимо с деревом B+.
Один узел B-дерева может хранить несколько элементов.По сравнению с полностью сбалансированным двоичным деревом общая высота дерева уменьшается, а эффективность дискового ввода-вывода повышается.
Дерево B+ является обновленной версией дерева B, но неконечные узлы являются избыточными.Преимущество этого заключается в том, чтоДля повышения эффективности поиска диапазона.
Причина улучшения не что иное, как тот факт, что будет указатель на листовой узел следующего узла.
резюме: Здесь можно сделать вывод, что Mysql использует структуру данных дерева B+ в качестве индекса, что может повысить эффективность дискового ввода-вывода при запросе индекса и может повысить эффективность запросов диапазона, а элементы в дереве B+ также упорядочены.
Итак, сколько элементов хранится в узле дерева B+, вам лучше всего знать?
А, это, это? Лежа* немного ошарашен.
Через некоторое время я до сих пор не могу думать об этом, поэтому я могу только честно объяснить: я не знаю keke очень хорошо.
Вы можете подумать о том, насколько велик узел в дереве B+ под другим углом?
Наиболее подходящим узлом в дереве B+ является страница или кратное количество страниц..
Зачем?
Потому что если размер узла меньше 1 страницы, то при чтении этого узла фактически считывается 1 страница, что приводит к пустой трате ресурсов.
Если размер узла больше 1 страницы, например 1,2 страницы, то при чтении этого узла будет прочитано 2 страницы, что также приведет к пустой трате ресурсов.
Поэтому, чтобы не создавать потерь, наиболее целесообразно контролировать размер узла кратным 1 странице, 2 страницам, 3 страницам и 4 страницам.
Вы упомянули концепцию страниц, не могли бы вы вкратце объяснить мне?
Прежде всего, основная структура хранения Mysql:Страница(Записи хранятся на странице):
отдельные страницы данныхможет сформироватьДвусвязный список
изаписи на каждой странице данныхформировать другойоднонаправленныйсвязанный список
- Каждая страница данных генерирует запись для хранящихся на ней записейкаталог страниц, черезпервичный ключЕго можно использовать в каталоге страниц при поиске записи.Дихотомия быстрого позиционированияПерейдите к соответствующему слоту, а затем просмотрите записи в соответствующей группе слота, чтобы быстро найти указанную запись.
отдругие столбцы(не первичный ключ) в качестве критерия поиска: можно начинать только с самой маленькой записиИтерация по каждой записи в односвязном списке по очереди.
Итак, если мы напишем оператор SQL, такой как select * from user, где username='BingCing' без какой-либо оптимизации, он сделает это по умолчанию:
Перейдите на страницу, где находится запись
- Вам нужно пройти по двусвязному списку, чтобы найти страницу, на которой вы находитесь.
Найдите соответствующую запись на странице, где она находится
- Поскольку запрос не основан на первичном ключе, вы можете просматривать только односвязный список страницы, на которой вы находитесь.
Очевидно, что в случае большого количества данных такой поиск будеточень медленно! Это немного похоже на возвратные часы.
Ой? Поговорите с вами.
Черт возьми, какого черта мой рот делает.
Возвращаемая таблица, вероятно, состоит в том, что у нас есть индекс с первичным ключом в качестве идентификатора и индекс с общим полем имени, Мы ищем по общему полю:
выберите * из таблицы, где имя = 'Ping C'
Процесс выполнения заключается в том, чтобы сначала запросить «C-C» по индексу имени, затем обнаружить, что его идентификатор равен 2, и, наконец, перейти к индексу первичного ключа, чтобы найти значение, соответствующее идентификатору 2.
Вернемся к процессу поиска по дереву индекса первичного ключа, т.е.форма возврата. Однако есть также способы избежать возврата таблицы, т.е.индекс покрытия.
Ой? Тогда вы можете поговорить со мной о покрытии индексов?
! ! ! мой рот. . .
Это на самом деле легче понять. Только что мы использовали select * для запроса всех из них.Если мы запрашиваем только идентификатор, на самом деле индекс поля «Имя» уже существует, поэтому нет необходимости возвращать таблицу.
Покрывающий индекс может сократить количество операций поиска по дереву и повысить производительность, а также является средством, которое мы часто используем для оптимизации эффективности запросов в реальном процессе разработки.
Многие совместные индексы создаются для поддержки покрывающих индексов, а специальные службы могут значительно повысить эффективность.
Знаете ли вы самый левый принцип соответствия индекса?
Крайний левый принцип соответствия:
- Индекс может быть простым, состоящим из одного столбца (a), или сложным, состоящим из нескольких столбцов (a,b,c,d), т.е.совместный индекс.
- Если это совместный индекс, ключ также состоит из нескольких столбцов, при этом индекс можно использовать только для того, чтобы узнать, является ли ключсуществуют (равные), при обнаружении запросов диапазона (>, больше нет совпадений, а затем вырождается в линейный поиск.
- следовательно,Порядок столбцов определяет количество столбцов, которые могут попасть в индекс..
пример:
- Если есть индекс (a,b,c,d) и условия запроса a=1 и b=2 и c>3 и d=4, a, b и c будут найдены последовательно в каждом узле, но д нельзя бить. (c уже является диапазонным запросом, d точно не отсортирован)
Суммировать
Индекс в базе данных – этоОченьВажные точки знаний!
Вышеупомянутый на самом деле индекссамый простойЯ не говорил о таких вещах, как N-арное дерево, таблица пропуска и LSM, в то же время для создания хорошего индекса нужно учитывать множество аспектов:
- Принцип сопоставления крайнего левого префикса. Это очень важный, очень важный, очень важный (важная вещь, сказанная трижды) принцип, MySQL всегда будет сопоставляться справа, пока не встретит запрос диапазона (>,
- выбрать как можно большеСтолбцы с высокой дискриминацией используются в качестве индексов., формула для различения: COUNT(DISTINCT col)/COUNT(*). Указывает соотношение не дублирующихся полей, чем больше соотношение, тем меньше записей мы сканируем.
- Столбцы индекса не могут участвовать в вычислениях, старайтесь содержать столбцы «чистыми».. Например, FROM_UNIXTIME(create_time)='2016-06-06' не может использовать индекс, причина очень проста,Все значения полей в таблице данных хранятся в дереве B+, но при извлечении нужно применить функцию ко всем элементам для сравнения, что явно слишком дорого. Таким образом, оператор должен быть записан как: create_time=UNIX_TIMESTAMP('2016-06-06').
- Насколько это возможнорасширенный указатель, не создавайте новый индекс. Например, в таблице уже есть индекс a, и теперь вам нужно добавить индекс (a, b), тогда вам нужно только изменить исходный индекс.
- Эффект извлечения одного составного индекса с несколькими столбцами и нескольких индексов с одним столбцом отличается, поскольку при выполнении SQL
MySQL может использовать только один индекс, выбирает наиболее строгий индекс из нескольких одностолбцовых индексов.(После исправления в MySQL 5.0 и более поздних версиях есть стратегия «объединения индексов». Прочитав «High Performance MySQL Third Edition», автор книги думает:Лучше создать лучший индекс, чем полагаться на стратегию «индекса слияния».). - Стратегия «индекса слияния» заключается в простом использовании нескольких одностолбцовых индексов, а затем объединении этих результатов с помощью «объединения или и».
Ссылки на идеи:
"Битва с MySQL"
«Высокопроизводительный MySQL»
Последняя часть содержимого взята из ->java3y "Index and Lock"
Дин Ци "Битва MySQL"
болтовня
Я уже размещал видео на станции B:
Все отзывы по-прежнему в порядке, я постараюсь больше в будущем, и я также надеюсь дать мне отзывы о предложениях по улучшению.
Свой первый супер грубый влог я снял в прошлом году:
Так как техника съёмки и монтажа была вся хрень, я её удалил, но недавно думал выложить снова, и я запутался ха-ха. Я хотел увидеть и оставить сообщение и я передам его. Ха-ха, мы будем следующий период.
Сегодня Bingbing также впервые заработала после 16 дней в Ханчжоу.Я очень рад, что наша компания находится в списке первой партии возобновления работы в Ханчжоу.Я не разговаривал ни с кем подобным за 16 дней. Я так счастлив, но я не могу включить кондиционер, пришлось открыть окна, чтобы проветрить, было действительно супер-супер-холодно.
Эта знакомая рабочая станция, этот знакомый дисплей, уголки моих глаз...
Проституция нехороша, творить нелегко,твойкакЭто самая большая движущая сила для создания Bing Bing, увидимся в следующей статье!
Постоянное обновление, продолжение следует...
Статья постоянно обновляется каждую неделю, вы можете искать в WeChat "Третий принц Ао Бин"Прочтите это в первый раз, ответьте [материал】【интервью】【резюме] Подготовленные мной материалы интервью и шаблоны резюме крупных заводов первой линии, эта статьяGitHub github.com/JavaFamilyОн был включен, и есть полные тестовые сайты для интервью с крупными заводами.Добро пожаловать в Star.
Чем больше вы знаете, тем больше вы не знаете