Die heutige Kolumne „MySQL-Datenbank“ stellt den Vergleich zwischen dem MySQL-Index und dem ElasticSearch-Index vor.
Vorwort
Während dieser Zeit habe ich die Suchfunktion des Produkts beibehalten. Jedes Mal, wenn ich elasticsearch auf der Verwaltungskonsole sehe, bin ich sehr gespannt, wie er funktioniert erreicht eine so effiziente Abfrageeffizienz.
elasticsearch 这么高效的查询效率我都很好奇他是如何做到的。
这甚至比在我本地使用 MySQL 通过主键的查询速度还快。
为此我搜索了相关资料：
这类问题网上很多答案，大概意思呢如下：
ES 是基于 Lucene 的全文检索引擎，它会对数据进行分词后保存索引，擅长管理大量的索引数据，相对于 MySQL 来说不擅长经常更新数据及关联查询。
跳表可能不像上边提到的散列表、有序数组、二叉树那样日常见的比较多，但其实 Redis 中的 sort set
🎜🎜Das ist sogar schneller als die Abfrage per Primärschlüssel mit MySQL auf meinem lokalen Rechner. 🎜🎜🎜🎜🎜🎜Ich habe nach relevanten Informationen gesucht: 🎜🎜🎜🎜🎜🎜Es gibt viele Antworten auf diese Art von Fragen im Internet. Die allgemeine Bedeutung ist wie folgt: 🎜
ES basiert auf Lucene und ist eine Volltextsuchmaschine, die Daten segmentiert und den Index speichert. Im Vergleich zu MySQL ist sie gut in der Lage, große Mengen an Indexdaten zu verwalten ist nicht gut darin, Daten und damit verbundene Abfragen häufig zu aktualisieren.
🎜Die Erklärung ist nicht sehr gründlich und analysiert nicht die relevanten Prinzipien, aber da der Index wiederholt erwähnt wird, vergleichen wir den Unterschied zwischen den beiden aus der Perspektive des Index. 🎜
MySQL-Index🎜🎜 Beginnen wir mit MySQL. Jeder muss mit dem Wort Index vertraut sein. Es kommt normalerweise in einigen Abfrageszenarien vor und ist ein typisches A Fall des Austauschs von Raum gegen Zeit. 🎜rrreee
Gemeinsame Datenstrukturen
🎜Angenommen, wir entwerfen den Index von MySQL selbst, welche Optionen gibt es? 🎜
Hash-Tabelle
🎜Das erste, woran wir denken sollten, ist die Hash-Tabelle, eine sehr verbreitete und effiziente Datenstruktur zum Abfragen und Schreiben, entsprechend Java ist HashMap🎜🎜🎜🎜🎜🎜Diese Datenstruktur sollte nicht allzu viel Einführung erfordern, ihre Schreibeffizienz ist sehr hoch O(1) code> Wenn wir beispielsweise die Daten von <code>id=3 abfragen möchten, müssen wir 3 hashen und dann die entsprechende Position im Array finden. 🎜🎜Aber wenn wir Intervalldaten wie 1≤id≤6 abfragen möchten, kann die Hash-Tabelle dies nicht gut erfüllen. Da sie ungeordnet ist, müssen wir alle Daten durchlaufen dieses Intervall. 🎜
Geordnetes Array
🎜🎜🎜🎜🎜Die Abfrageeffizienz geordneter Arrays ist ebenfalls sehr hoch. Wenn wir id=4 abfragen möchten Code > Daten, die Daten können <code>O(logn) nur durch binäre Suche effizient lokalisiert werden. 🎜🎜Da die Daten auch geordnet sind, können sie natürlich Intervallabfragen unterstützen. 🎜🎜Natürlich nicht, es gibt ein weiteres großes Problem code> Für die Daten mit id=2.5 müssen alle nachfolgenden Daten gleichzeitig um ein Bit verschoben werden. Dadurch wird die Schreibeffizienz sehr gering. 🎜
Ausgeglichener Binärbaum
🎜Da die Schreibeffizienz geordneter Arrays nicht hoch ist, werfen wir einen Blick auf diejenigen mit hoher Schreibeffizienz. Das ist leicht vorstellbar Binärbäume; Hier nehmen wir einen ausgeglichenen Binärbaum als Beispiel: 🎜🎜🎜🎜🎜🎜Aufgrund der Eigenschaften ausgeglichener Binärbäume: 🎜
🎜Der linke Knoten ist kleiner als der übergeordnete Knoten und der rechte Knoten ist kleiner größer als der übergeordnete Knoten. 🎜
🎜Angenommen, wir möchten die Daten von id=11 abfragen, müssen wir nur 10 –>12 –>11 abfragen, um sie schließlich zu finden die Daten, Zeit Die Komplexität beträgt O(logn), und beim Schreiben von Daten ist sie ebenfalls O(logn). 🎜🎜Aber die Intervallsuche wird immer noch nicht sehr gut unterstützt. Angenommen, wir möchten die Daten von 5≤id≤20 abfragen. Wir müssen zuerst den linken Teilbaum von 10 Knoten abfragen und dann den rechten Teilbaum von 10 Knoten. Erst am Ende können alle Daten abgefragt werden. 🎜🎜Daher ist die Abfrageeffizienz nicht hoch. 🎜
Skip-Tabelle
🎜Skip-Tabelle ist möglicherweise nicht so häufig wie die oben erwähnte Hash-Tabelle, das geordnete Array und der Binärbaum, aber tatsächlich Redis Die sort set in wird mithilfe einer Sprungliste implementiert. 🎜
Hier stellen wir kurz die Vorteile der durch Sprungtabellen implementierten Datenstruktur vor.
Wir alle wissen, dass selbst das Abfragen einer geordneten verknüpften Liste nicht effizient ist, da für die binäre Suche keine Array-Indizes verwendet werden können. Die Zeitkomplexität beträgt o(n)o(n)
假设我们写入的主键数据是无序的，那么有可能后写入数据的 id 小于之前写入的，这样在维护 B+树 索引时便有可能需要移动已经写好数据。
如果是按照递增写入数据时则不会有这个考虑，每次只需要依次写入即可。
所以我们才会要求数据库主键尽量是趋势递增的，不考虑分表的情况时最合理的就是自增主键。
整体来看思路和跳表类似，只是针对使用场景做了相关的调整（比如数据全部存储于叶子节点）。
ES 索引
MySQL 聊完了，现在来看看 Elasticsearch 是如何来使用索引的。
正排索引
在 ES 中采用的是一种名叫倒排索引的数据结构；在正式讲倒排索引之前先来聊聊和他相反的正排索引
Aber wir können es auch geschickt tun Optimieren Sie die verknüpfte Liste, um eine getarnte binäre Suche zu implementieren, wie unten gezeigt: 🎜🎜Wir können den Index der ersten Ebene und den Index der zweiten Ebene für die unterste Ebene extrahieren Datenebenenindex: Abhängig von der Datenmenge können wir N-Ebenen-Indizes extrahieren. 🎜🎜Wenn wir eine Abfrage durchführen, können wir den Index hier verwenden, um eine getarnte binäre Suche zu implementieren. 🎜🎜Angenommen, Sie möchten jetzt die Daten von id=13 abfragen, Sie müssen nur die vier Knoten von 1 –>7 –>10 –>13durchlaufen > Um die Daten abzufragen, ist die Effizienzverbesserung offensichtlicher, wenn die Anzahl größer ist. 🎜🎜Gleichzeitig wird auch die Intervallabfrage unterstützt. Ähnlich wie bei der Abfrage eines einzelnen Knotens müssen Sie nur den Startknoten abfragen und dann rückwärts (🎜Die verknüpfte Liste ist in Ordnung🎜) zum Zielknoten durchlaufen den gesamten Datenbereich abfragen. 🎜🎜Da wir gleichzeitig keine echten Daten im Index speichern, sondern nur einen Zeiger speichern, ist der belegte Platz im Vergleich zur verknüpften Liste unten, in der Daten gespeichert werden, vernachlässigbar. 🎜
Optimierung ausgeglichener Binärbäume
🎜Aber tatsächlich verwendet Innodb in MySQL keine Skip-Tabellen, Es wird jedoch eine Datenstruktur namens B+-Baum verwendet. 🎜🎜Diese Datenstruktur ähnelt nicht dem Binärbaum, den Universitätslehrer oft als Basisdatenstruktur bezeichnen, da diese Art von Datenstruktur aus der Basisdatenstruktur basierend auf Bedarfsszenarien in tatsächlichen Projekten entwickelt wird. 🎜🎜Zum Beispiel kann man davon ausgehen, dass der B+-Baum hier aus dem ausgeglichenen Binärbaum hervorgegangen ist. 🎜🎜Gerade haben wir erwähnt, dass die Intervallabfrageeffizienz von Binärbäumen nicht hoch ist. Dies kann optimiert werden: 🎜🎜Nach der Optimierung basierend auf dem ursprünglichen Binärbaum: Alle Nicht-Blätter speichern keine Daten, sie dienen lediglich als Indizes für Blattknoten und alle Daten werden in Blattknoten gespeichert. 🎜🎜Auf diese Weise werden die Daten aller Blattknoten der Reihe nach gespeichert und Intervallabfragen können gut unterstützt werden. 🎜🎜Sie müssen nur zuerst die Position des Startknotens abfragen und dann in den Blattknoten rückwärts durchlaufen. 🎜🎜Wenn die Datenmenge groß ist, kann die Indexdatei offensichtlich nicht im Speicher gespeichert werden. Obwohl sie schnell ist, verbraucht sie viele Ressourcen direkt auf der Festplatte. 🎜🎜Dies unterscheidet sich geringfügig vom später erwähnten Elasticsearch-Index. 🎜🎜Da der Index auf der Festplatte gespeichert ist, müssen wir die E/A auf der Festplatte so weit wie möglich reduzieren (die Effizienz von Festplatten-E/A liegt nicht in der gleichen Größenordnung wie die des Speichers) 🎜🎜Wie Sie sehen können In der obigen Abbildung müssen wir ein Datenelement mindestens viermal IO abfragen. Es ist offensichtlich, dass die Anzahl der IOs eng mit der Höhe des Baums zusammenhängt. Je niedriger die Höhe des Baums, desto geringer die Anzahl der IOs und desto besser ist die Leistung. 🎜🎜Wie können wir also die Höhe des Baumes reduzieren? 🎜🎜Wir können versuchen, den Binärbaum in einen Ternärbaum umzuwandeln, sodass die Höhe des Baums und die Anzahl der E/As stark reduziert werden Die Abfrage von Daten wird natürlich reduziert. Gleichzeitig wird auch die Abfrageeffizienz erheblich verbessert. 🎜
🎜Dies ist tatsächlich der Ursprung des B+-Baums. 🎜
Einige Vorschläge zur Verwendung von Indizes
🎜Tatsächlich können wir durch das Verständnis des B+-Baums in der obigen Abbildung Optimieren Sie auch unsere tägliche Arbeit. Einige kleine Details, z. B. warum es am besten ist, nacheinander zuzunehmen? 🎜🎜Angenommen, die von uns geschriebenen Primärschlüsseldaten sind ungeordnet, dann ist es möglich, dass die ID der später geschriebenen Daten kleiner ist als die zuvor geschriebene. Auf diese Weise kann es erforderlich sein, die bereits geschriebenen Daten bei der Wartung zu verschieben B+tree Index. Gute Daten. 🎜🎜Wenn Sie Daten inkrementell schreiben, müssen Sie diese Überlegung nicht berücksichtigen. Sie müssen jedes Mal nur sequentiell schreiben. 🎜
🎜Deshalb benötigen wir einen möglichst steigenden Trend des Primärschlüssels der Datenbank. Am sinnvollsten ist es, den Primärschlüssel automatisch zu erhöhen, ohne die Situation geteilter Tabellen zu berücksichtigen. 🎜
🎜Insgesamt ähnelt die Idee der einer Skip-Tabelle, außer dass relevante Anpassungen für das Nutzungsszenario vorgenommen wurden (z. B. werden alle Daten in Blattknoten gespeichert). 🎜
ES Index
🎜MySQL Schauen wir uns nach dem Chat an, wie Elasticsearch Indizes verwendet. 🎜
Vorwärtsindex
🎜In ES wird formal eine Datenstruktur namens Invertierter Index verwendet. Lassen Sie uns vor der Indizierung darüber sprechen der entgegengesetzte Vorwärtsindex. 🎜
Nehmen wir das obige Bild als Beispiel: Die Art und Weise, wie wir bestimmte Objekte über doc_id abfragen können, wird mit forward index aufgerufen. Tatsächlich kann dies auch der Fall sein als eine Art verstreute Liste verstanden. doc_id 查询到具体对象的方式称为使用正排索引，其实也能理解为一种散列表。
比如现在需要查询 name=li and age=18 的数据，这时我们需要通过这两个字段将各自的结果 Posting List
Die Essenz besteht darin, den Wert durch den Schlüssel zu finden.
Zum Beispiel können Sie über doc_id=4 schnell die Daten name=jetty wang,age=20 abfragen.
Invertierter Index
Wenn ich die Daten abfragen möchte, die li in name enthalten, gibt es welche diejenigen? Wie kann man auf diese Weise effizient abfragen?
Die bloße Verwendung des oben genannten Vorwärtsindex funktioniert offensichtlich nicht. Wir können nur alle Daten nacheinander durchlaufen und feststellen, ob der Name li enthält.
🎜Aber wenn wir eine Indexstruktur neu erstellen: 🎜🎜🎜🎜🎜🎜Wenn Sie die Daten abfragen möchten, die li in name enthalten, müssen Sie nur dies verwenden Indexstruktur Fragen Sie die in Posting List enthaltenen Daten ab und fragen Sie dann die endgültigen Daten durch Zuordnung ab. 🎜🎜Diese Indexstruktur ist eigentlich ein invertierter Index. 🎜
Begriffswörterbuch
🎜Aber wie kann man li in dieser Indexstruktur effizient abfragen, indem man unsere bisherigen Erfahrungen kombiniert, solange wir Term ist der Reihe nach angeordnet und die Datenstruktur des binären Baumsuchbaums kann zum Abfragen der Daten unter o(logn) verwendet werden. 🎜🎜Der Prozess der Aufteilung eines Textes in unabhängige Begriffe ist eigentlich das, was wir oft Wortsegmentierung nennen. 🎜🎜Und die Kombination aller Begriffe zusammen ergibt ein Begriffswörterbuch, das auch als Wortwörterbuch bezeichnet werden kann. 🎜
Die englische Wortsegmentierung ist relativ einfach. Sie müssen den Text nur durch Leerzeichen und Satzzeichen trennen. Chinesisch ist relativ kompliziert, aber es gibt auch viele Open-Source-Tools, die es unterstützen ist nicht der Schwerpunkt dieses Artikels, ich interessiere mich für die Wortsegmentierung. Sie können selbst suchen).
🎜Wenn unser Textvolumen riesig ist, wird es nach der Wortsegmentierung viele Begriffe geben. Wenn eine solche invertierte Indexdatenstruktur im Speicher gespeichert wird, wird dies definitiv nicht der Fall sein reicht aus, aber wenn es wie MySQL auf der Festplatte gespeichert wird, ist die Effizienz nicht so hoch. 🎜
Term Index
🎜Wir können also eine Kompromissmethode wählen. Da nicht das gesamte Term Dictionary im Speicher abgelegt werden kann, verwenden wir einen Index kann für das Begriffswörterbuch erstellt und im Speicher abgelegt werden. 🎜🎜Auf diese Weise kann das Term Dictionary effizient abgefragt werden, und schließlich kann die Posting List über das Term Dictionary abgefragt werden. 🎜🎜Im Vergleich zum B+-Baum in MySQL wird auch die Festplatten-IO um ein Vielfaches reduziert. 🎜🎜🎜🎜🎜🎜Wir können diesen Term Index verwenden, um ihn mithilfe eines Trie-Baums zu speichern, den wir oft als Wörterbuchbaum bezeichnen. Code>. 🎜🎜Weitere Informationen zu Wörterbuchbäumen finden Sie hier. 🎜🎜<img class="lazyload" src="https://img.php.cn/upload/article/000/000/052/b63caa59eed2dd20ddbd73c8ecac91f5-13.jpg" data- style="max-width:90%" data-height=" 600" alt="MySQL-Index VS ElasticSearch-Index" >🎜🎜🎜🎜Wenn wir nach <code>Term suchen, der mit j beginnt, besteht der erste Schritt darin, die Abfrage Term Index in Memory Code> zu verwenden die Position von <code>Term beginnend mit j in der Wörterbuchdatei Term Dictionary (diese Position kann ein Dateizeiger sein, der ein Intervallbereich sein kann) . 🎜🎜Dann entfernen Sie alle Begriffe in diesem Positionsbereich. Da sie sortiert wurden, können Sie die spezifische Position auf diese Weise schnell finden und die Posting-Liste abfragen . 🎜🎜Schließlich können die Zieldaten aus der Originaldatei über die Standortinformationen in <code>Posting List abgerufen werden. 🎜
Weitere Optimierungen
🎜Natürlich hat ElasticSearch auch viele gezielte Optimierungen vorgenommen. Wenn wir zwei Felder abrufen, können Sie bitmap verwenden zur Optimierung. 🎜🎜Wenn wir nun beispielsweise die Daten von name=li und age=18 abfragen müssen, müssen wir diese beiden Felder verwenden, um die entsprechenden Ergebnisse Posting Listabzurufen >. 🎜🎜🎜🎜🎜🎜🎜Der einfachste Weg besteht darin, die beiden Sammlungen separat zu durchlaufen und doppelte Daten zu entfernen, aber das ist offensichtlich ineffizient. 🎜
Zu diesem Zeitpunkt können wir die bitmap-Methode zum Speichern verwenden (und auch Speicherplatz sparen) und gleichzeitig die angeborenen -Bits und ** Berechnungen verwenden Holen Sie sich das Ergebnis . **bitmap 的方式进行存储（还节省存储空间），同时利用先天的位与 **计算便可得出结果。**
[1, 3, 5] ⇒ 10101
[1, 2, 4, 5] ⇒ 11011
这样两个二进制数组求与便可得出结果：
10001 ⇒ [1, 5]
最终反解出 Posting List 为[1, 5],这样的效率自然是要高上许多。
同样的查询需求在 MySQL 中并没有特殊优化，只是先将数据量小的数据筛选出来之后再筛选第二个字段，效率自然也就没有 ES 高。
当然在最新版的 ES 中也会对 Posting List 进行压缩，具体压缩规则可以查看官方文档，这里就不具体介绍了。
[1, 2, 4, 5] ⇒ 11011 Das Ergebnis kann durch Summieren zweier binärer Arrays erhalten werden:
10001 ⇒ [1, 5]🎜🎜Die Lösung lautet schließlich Die Posting-Liste ist [1, 5], daher ist die Effizienz natürlich viel höher. 🎜🎜Es gibt keine spezielle Optimierung für die gleiche Abfrageanforderung in MySQL. Es werden nur die Daten mit geringem Datenvolumen zuerst herausgefiltert und dann das zweite Feld. Natürlich ist die Effizienz nicht so gut wie bei ES code> hoch. 🎜🎜Natürlich wird Posting List auch in der neuesten Version von ES komprimiert. Spezifische Komprimierungsregeln können Sie der offiziellen Dokumentation entnehmen, die nicht im Detail vorgestellt wird Hier. 🎜
Zusammenfassung
🎜Lassen Sie uns abschließend zusammenfassen: 🎜🎜Aus dem obigen Inhalt ist ersichtlich, dass Komplexe Produkte bestehen letztendlich aus grundlegenden Datenstrukturen, die nur für unterschiedliche Anwendungsszenarien optimiert sind. Daher können Sie erst dann schnell loslegen, wenn Sie sich mit einer neuen Technologie oder Middleware befassen, oder sogar lernen, wenn Sie über eine gute Grundlage für Datenstrukturen und Algorithmen verfügen es selbst. Kann die Richtung der Optimierung kennen. 🎜🎜Abschließend werde ich versuchen, eine eigenständige Suchmaschine basierend auf der Idee des invertierten Index ES zu erstellen mein Verständnis vertiefen. 🎜🎜🎜Verwandte kostenlose Lernempfehlungen: 🎜MySQL-Datenbank🎜 (Video) 🎜🎜
Das obige ist der detaillierte Inhalt vonMySQL-Index VS ElasticSearch-Index. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
🎜🎜🎜🎜Es gibt viele Antworten auf diese Art von Fragen im Internet. Die allgemeine Bedeutung ist wie folgt: 🎜
🎜🎜🎜🎜Diese Datenstruktur sollte nicht allzu viel Einführung erfordern, ihre Schreibeffizienz ist sehr hoch 
🎜🎜🎜🎜Die Abfrageeffizienz geordneter Arrays ist ebenfalls sehr hoch. Wenn wir 
🎜🎜🎜🎜Aufgrund der Eigenschaften ausgeglichener Binärbäume: 🎜
Zum Beispiel können Sie über 
