предисловие

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

Это даже больше, чем в моем локальном использованииMySQLЗапросы по первичному ключу также выполняются быстрее.

Для этого я искал соответствующую информацию:

В интернете есть много ответов на такого рода вопросы, что примерно означает следующее:

• ЭС основан наLuceneМеханизм полнотекстового поиска, который сегментирует данные и сохраняет индекс, хорошо справляется с большим объемом данных индекса по сравнению сMySQLОн не подходит для частого обновления данных и связанных запросов.

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

индексы MySQL

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

以下内容以 Innodb 引擎为例。

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

Предположим, мы проектируем его самиMySQLиндекс, какие есть варианты?

хеш-таблица

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

Эта структура данных не нуждается в особом представлении, эффективность ее записи очень высока.O(1), например, мы хотим запроситьid=3, вам нужно выполнить хэш-операцию над 3, а затем найти соответствующую позицию в этом массиве.

но если мы хотим запросить1≤id≤6Для таких интервальных данных хеш-таблица не может быть полностью удовлетворена, поскольку она неупорядочена, необходимо просмотреть все данные, чтобы узнать, какие данные принадлежат этому интервалу.

отсортированный массив

Эффективность запросов упорядоченных массивов также очень высока, когда мы хотим запроситьid=4Когда данные хранятся, для эффективного поиска данных можно использовать только двоичный поиск.O(logn).

В то же время, поскольку данные также упорядочены, они, естественно, могут поддерживать интервальные запросы, поэтому кажется, что упорядоченные массивы подходят для использования в качестве индексов?

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

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

Так как эффективность записи упорядоченного массива невелика, давайте посмотрим на высокую эффективность записи, и легко думать о двоичном дереве; здесь мы возьмем в качестве примера сбалансированное двоичное дерево:

Благодаря свойствам сбалансированных бинарных деревьев:

Левый узел меньше родительского узла, а правый узел больше родительского узла.

Итак, допустим, мы хотим запроситьid=11данные, просто запрос10—>12—>11Данные могут быть окончательно найдены, а временная сложностьO(logn), аналогично при записи данных тожеO(logn).

Но он по-прежнему не очень хорошо поддерживает поиск по диапазону интервалов. Предположим, мы хотим запросить5≤id≤20Когда данные сохраняются, необходимо сначала запросить левое поддерево из 10 узлов, а затем запросить правое поддерево из 10 узлов, и, наконец, можно запросить все данные.

В результате эффективность запросов невысока.

пропустить стол

Таблица пропуска может быть не так распространена, как хеш-таблица, упорядоченный массив и двоичное дерево, упомянутые выше, но на самом делеRedisсерединаsort setРеализована таблица пропуска.

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

Все мы знаем, что даже дляупорядоченный связанный списокЭффективность запроса невысока, так как он не может использовать индекс массива для бинарного поиска, поэтому временная сложность составляетo(n)

Но мы также можем разумно оптимизировать связанный список, чтобы замаскировать бинарный поиск, как показано ниже:

Мы можем извлечь индекс первого уровня и индекс второго уровня для данных нижнего уровня.В соответствии с разным объемом данных мы можем извлечь индекс N-уровня.

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

Предположим, теперь вы хотите запроситьid=13данные, просто пройдитесь1—>7—>10—>13Только четыре узла могут запрашивать данные, и когда их больше, повышение эффективности будет более очевидным.

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

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

Оптимизация сбалансированного бинарного дерева

Но на самом делеMySQLсерединаInnodbВместо использования таблицы пропускаB+древовидная структура данных.

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

такой как здесьB+Можно считать, что дерево произошло от сбалансированного бинарного дерева.

Только что мы упоминали, что эффективность интервального запроса бинарного дерева невысока, и его можно оптимизировать для этого момента:

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

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

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

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

Это немного отличается от упомянутого ниже индекса elasticsearch.

Так как индекс хранится на диске, нам нужно максимально сократить IO с диском (эффективность дискового IO не того порядка, что памяти)

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

Так как же уменьшить высоту дерева?

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

На самом деле это происхождение дерева B+.

Несколько советов по использованию индексов

На самом деле, через приведенный выше рисунокB+树Он также может оптимизировать некоторые мелкие детали повседневной работы; например, почему это должно быть упорядоченным шагом?

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

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

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

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

индекс ЭС

MySQLТеперь, когда мы закончили разговор, давайте посмотримElasticsearchКак пользоваться индексом.

положительный индекс

В ES метод называется倒排索引Структура данных ; давайте поговорим о противоположности ему, прежде чем формально говорить об инвертированном индексе正排索引.

Возьмите приведенный выше рисунок в качестве примера, мы можем пройтиdoc_idСпособ запроса к конкретному объекту называется с помощью正排索引, по сути, тоже можно понимать как хеш-таблицу.

Суть в том, чтобы найти значение по ключу.

например, черезdoc_id=4можно быстро найтиname=jetty wang,age=20эти данные.

Перевернутый индекс

Затем, если, в свою очередь, я хочу запроситьnameсодержитliКакие данные? Как сделать запрос эффективно?

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

Но если мы перестроим структуру индекса:

когда спрашиваешьnameсодержитli, вам нужно только запросить данные через эту структуру индексаPosting ListДанные, содержащиеся в данных, затем запрашиваются для окончательных данных путем сопоставления.

Эта индексная структура на самом деле倒排索引.

Term Dictionary

Но как эффективно выполнять запросы в этой структуре индексаliНу, в сочетании с нашим предыдущим опытом, пока мы будемTermУпорядоченное расположение, вы можете использовать структуру данных дерева поиска двоичного дерева вo(logn)Запросите данные ниже.

Разбить текст на отдельные частиTermНа самом деле процесс — это причастие, которое мы часто произносим.

и положить всеTermВ совокупности это одноTerm Dictionary, также известный как словарь слов.

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

Когда объем нашего текста огромен, после сегментации словTermИх тоже будет много.Если хранить в памяти такую ​​инвертированную индексную структуру данных, то ее точно будет мало, но если что-то вродеMySQLПри таком хранении на диске эффективность не так высока.

Term Index

Таким образом, мы можем выбрать компромиссный метод, так как невозможно объединить всеTerm Dictionaryв память, то мы можемTerm DictionaryСоздайте индекс и поместите его в память.

Это позволяет эффективно запрашиватьTerm Dictionary, и, наконец, пройтиTerm DictionaryЗапрошеноPosting List.

относительноMySQLсерединаB+树Это также уменьшит в несколько раз磁盘IO.

этоTerm IndexМы можем использовать что-то вроде этогоTrie树Это то, что мы часто говорим字典树хранить.

Дополнительные сведения о словарных деревьях см.здесь.

если мыjначалоTermДля поиска, первый шаг - передатьTerm Indexзапрос сjвозглавлялTermсуществуетTerm DictionaryГде в файле словаря (это место может быть указателем файла, возможно, диапазоном интервалов).

Сразу после размещения всехTermВыньте, поскольку он был отсортирован, вы можете быстро найти конкретное место с помощью двоичного поиска; таким образом, вы можете запроситьPosting List.

наконец прошлоPosting ListИнформация о местоположении в исходном файле может быть извлечена из целевых данных.

больше оптимизаций

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

Например, теперь вам нужно запроситьname=li and age=18Данные, то нам нужно передать эти два поля в соответствующие результатыPosting Listвыиграть.

Самый простой способ — обойти две коллекции по отдельности и удалить повторяющиеся данные, но это явно неэффективно.

Тогда мы можем использоватьbitmapспособ хранения (и экономии места для хранения), используя при этом врожденные位与 Рассчитать результат.

[1, 3, 5]⇒10101

[1, 2, 4, 5]⇒11011

Результат суммирования двух двоичных массивов таким образом:

10001⇒[1, 5]

окончательное решениеPosting Listза[1, 5], этот КПД, естественно, гораздо выше.

Тот же запрос нуждается вMySQLОсобой оптимизации в нем нет, но сначала фильтруются данные с малым объемом данных, а потом фильтруется второе поле, и эффективность естественно не высокая.ESвысокий.

Конечно в последней версииESтоже правильноPosting ListСжатие, конкретные правила сжатия можно просмотретьофициальная документация, который здесь подробно не описан.

Суммировать

Наконец, подведем итоги:

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

Наконец нарисуйте пирог, я постараюсь следоватьESИдея инвертированного индексирования — это автономная поисковая система, и вы можете углубить свое понимание, только написав ее самостоятельно.

Чтобы получить больше удовольствия от чтения, посетитездесь:woohoo.notion.so/эластичное шептало…

Ваши лайки и репост - лучшая поддержка для меня