01 Предисловие

Здравствуйте, давно не было обновлений. Потому что я недавно брал интервью. На подготовку ушло две недели и за 3 дня я получил 5 предложений.Наконец выбрал предложение от единорога в интернет-индустрии в Гуанчжоу.Я только вчера присоединился к компании. За последние несколько дней я просто разобрался с интересными вопросами, которые были заданы в интервью, а также воспользовался случаем, чтобы поделиться с вами.

Интервьюер этой компании оказался немного интересным, с одной стороны, младшим братом-ровесником, мы проболтали два часа (у меня пересохло во рту). Вторая сторона — архитектор из Али, он задал вопрос сцены:

В базе данных есть поле типа string, в котором хранится URL Как спроектировать индекс?

В то время я далРазделение полей: первая половина URL-адреса должна иметь низкую дискриминацию, а вторая половина — высокую; я разделяю высокую и низкую дискриминацию на два поля для хранения и строю индекс на поле с высокой дискриминацией.конкретные ответы и предлагаемыемаксимизировать различиеидеи.

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

02 Индексировать все поле

Сначала покажите дизайн таблицы:

CREATE TABLE IF NOT EXISTS `t`(
   `id` INT(11) NOT NULL AUTO_INCREMENT,
   `url` VARCHAR(100) NOT NULL,
   PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

Данные таблицы:

Собственно этот вопрос =Как создать индекс для строк?, вы можете сказать, что недостаточно выполнить следующий оператор напрямую?

alter table t add index index_url(url);

Я наугад нарисовал картинку, и структура MySQL index_url такая:

Действительно, это возможно. Для выполнения следующего оператора запроса требуется толькоодно сканированиеПросто сделай это.

select id,url from t where url='javafish/nhjj/mybatis';

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

Есть ли способ менее занимающий место? Мы, естественно, думаем о MySQLиндекс префикса.

03 Индекс префикса

Для приведенных выше данных таблицы добавьте индекс префикса, нет необходимости добавлять индекс ко всему полю, поэтому вы можете построить индекс следующим образом:

alter table t add index index_url(url(8));

На данный момент структура index_url выглядит следующим образом:

select id,url from t where url='javafish/nhjj/mybatis';

Выполните тот же sql-запрос, его процесс выглядит следующим образом:

Найдите из дерева индексов index_url, чтобы удовлетворить значение индексаjavafish, первым найденным является ID1; строка, значение первичного ключа которой равно ID1, найдена по первичному ключу, и считается, что значение url не равноjavafish/nhjj/mybatis, эта строка записей отбрасывается;
Возьмите следующую запись местоположения ID1, только что найденную, и обнаружите, что она все ещеjavafish, выньте ID2, затем перейдите к индексу ID, чтобы взять всю строку и судить, она все равно неверна;
Повторяйте предыдущий шаг до тех пор, пока значение, полученное на index_url, не будетjavafish, цикл заканчивается. В этом процессеЧтобы вернуться к индексу первичного ключа для выборки данных 6 раз, то есть для сканирования 6 строк. Благодаря этому сравнению вы легко обнаружите, что после использования префиксной индексации вы можетеКоличество раз, когда оператор запроса считывает данные, увеличивается..

Когда мы увеличиваем длину индекса префикса URL до 10. Вы обнаружите, что при выполнении того же оператора запроса просто нужносканировать 1 строкумогут быть получены целевые данные.

3.1 Выбор длины префикса

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

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

select count(distinct url) as L from t;

Пакетные операции могут быть выполнены следующим образом:

SELECT
	count( DISTINCT LEFT ( url, 8 ) ) AS L8,
	count( DISTINCT LEFT ( url, 9 ) ) AS L9,
	count( DISTINCT LEFT ( url, 10 ) ) AS L10,
	count( DISTINCT LEFT ( url, 11 ) ) AS L11 
FROM
	t;

Результат таков:

Наши принципы выбора длины префикса:Высокая степень отличия + небольшой след; учитывая оба фактора, я бы выбрал 10 в качестве длины индекса префикса.

3.2 Недостаточный индекс префикса

Префиксная индексация хороша, но и у нее есть свои недостатки. Например, выбор длины, о котором мы говорили выше, не годится, что приведет кУвеличьте количество строк сканирования.

Еще один момент заключается в том, что используется индекс префикса, когда вы оптимизируете sql,Невозможно использовать покрытие индексаЭто оптимизировано. Друзья, которые не уверены в покрытии индекса, советую прочитать эту статью«Принципы индекса MySQL»

Например: даже если вы измените определение index_url на префиксный индекс url (100), хотя index_url уже содержит всю информацию, InnoDB все равно придется вернуться к индексу id и проверить еще раз, потому что система не определяет индекс префикса Усекает ли определение полную информацию.

Это также учитывается при выборе индекса префикса.

04 Другие способы

Приведенные выше URL-адреса относительно короткие и также могут быть проиндексированы с помощью префиксов. Предположим, что URL-адрес вдруг стал длиннее (не спрашивайте почему, он может стать длиннее и толще), и это выглядит так:

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

Есть ли другой способ гарантировать степень дискриминации, не занимая так много места?

Да, например:Хранение в обратном порядке и добавление хеш-полей

4.1 Хранение в обратном порядке

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

select url from t where url = reverse('输入的 url 字符串');

4.2 Хэш-поля

Добавьте целочисленное поле в таблицу данных, которое используется в качестве кода проверки URL-адреса, и создайте для него индекс..

alter table t add url_crc int unsigned, add index(url_crc);

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

INSERT INTO t VALUE( 00000000007, 'wwww.javafish.top/article/erwt/spring', CRC32('wwww.javafish.top/article/erwt/spring'))

Затем вставьте результат после выполнения.

Однако следует отметить, что каждый раз, когда вставляется новая запись, для заполнения этого нового поля используется проверочный код, полученный функцией crc32(), и могут возникать конфликты.

То есть результаты, полученные двумя разными URL-адресами с помощью функции crc32(), могут быть одинаковыми, поэтому часть оператора запроса where также должна определять, совпадают ли значения URL-адресов:

select url from t where url_crc = crc32('输入的 url 字符串') and url = '输入的 url 字符串'

Таким образом, это эквивалентно уменьшению длины индекса URL-адреса до 4 байтов, сокращению пространства для хранения и повышению эффективности запросов.

4.3 Сравнение двух

Тот же пункт: не поддерживаетсязапрос диапазона.

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

Их различия в основном отражаются в следующих трех аспектах:

отдополнительное пространство занятоВидно, что метод хранения в обратном порядке не требует дополнительного места для хранения индекса первичного ключа, в то время как метод хеш-поля требует добавления поля. Конечно, использование длины префикса в 4 байта в способе хранения в обратном порядке должно быть недостаточным, если он больше, то этот расход практически компенсируется дополнительным хеш-полем.
существуетПотребление ЦПС одной стороны, метод обратного порядка требует дополнительного вызова обратной функции каждый раз при записи и чтении, тогда как метод хеш-поля требует дополнительного вызова функции crc32(). Хотя бы из-за вычислительной сложности этих двух функций дополнительные ресурсы ЦП, потребляемые обратной функцией, будут меньше.
отэффективность запросаИсходя из вышеизложенного, производительность запросов с использованием метода хеш-поля относительно более стабильна. Поскольку значение, рассчитанное crc32, имеет вероятность конфликта, но вероятность этого очень мала, можно считать, что среднее количество сканируемых строк на запрос близко к 1. В конце концов, метод хранения в обратном порядке по-прежнему использует метод префиксного индекса, а это означает, что количество строк развертки все равно будет увеличено.

05 Резюме

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

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

06 Ссылка

time.geekbang.org/column/article/71492
cnblogs.com/Mr-Echo/p/12730797.html