MySQL インデックス VS ElasticSearch インデックス

TodayMySQL データベース 列では、MySQL インデックスと ElasticSearch インデックスの比較を紹介します。

まえがき

この期間中、製品の検索機能をメンテナンスしていますが、# が表示されるたびに、 # 管理コンソール上で #elasticsearch 彼がどのようにしてこのような効率的なクエリ効率を達成しているのか非常に興味があります。

これは、ローカル マシンで

MySQL を使用して主キーでクエリを実行するよりもさらに高速です。

関連情報を検索しました:

があります。この種の質問に対する回答はインターネット上にたくさんあります。一般的な意味は次のとおりです:

ES は
• Lucene に基づく全文検索エンジンです。データをセグメント化します。 MySQL と比較すると、大量のインデックス データの管理が得意ですが、データや関連するクエリを頻繁に更新するのは苦手です。

説明があまり丁寧ではなく、関連する原則の分析もありませんが、指数については繰り返し言及されているため、指数の観点から両者の違いを比較してみましょう。

MySQL インデックス

MySQL から始めましょう。インデックスという言葉は誰もがよく知っているはずです。インデックスは通常、一部のクエリ シナリオに存在し、典型的な時間の空間です。交換の場合もございます。

以下内容以 Innodb 引擎为例。复制代码

一般的なデータ構造

MySQL のインデックスを自分で設計すると仮定すると、どのようなオプションがありますか?

ハッシュ テーブル

最初に考えるべきはハッシュ テーブルです。これはクエリと書き込みのための非常に一般的で効率的なデータ構造であり、

Java に対応します。 HashMap

このデータ構造についてはあまり説明の必要はありません。書き込み効率が非常に高いです。

O (1) 、たとえば、id=3 のデータをクエリしたい場合、3 をハッシュし、この配列内の対応する位置を見つける必要があります。

しかし、

1≤id≤6 のような間隔データをクエリしたい場合、ハッシュ テーブルはそれを十分に満たすことができません。順序付けされていないため、すべてのデータは次のとおりである必要があります。どのデータがこの間隔に属しているかを知ることができます。

順序付き配列

順序付き配列のクエリ効率も、

id=4 # をクエリする場合には非常に高くなります。 ## データの場合、二分検索を使用するだけでデータ O(logn) を効率的に見つけることができます。 同時に、データも順序付けされているため、当然間隔クエリをサポートできます。そのため、順序付けされた配列はインデックスとしての使用に適しているように見えますか?

もちろんそうではありません。もう 1 つの大きな問題:

id=2.5

でデータを挿入すると、後続のデータをすべて同時に 1 ビット移動する必要があり、書き込み効率が非常に低くなります。 Balanced Binary Tree

順序配列の書き込み効率は高くないので、書き込み効率の高いものを見てみましょう。二分木は考えるのが簡単ですが、ここではバランス型を使用します例としての二分木の例:

バランスの取れた二分木の特性により:

左側のノードが小さくなります右側のノードは親ノードよりも大きく、右側のノードは親ノードよりも大きくなります。

したがって、

id=11

のデータをクエリしたいと仮定すると、最終的には 10—>12—>11 をクエリするだけで済みます。時間計算量は O(logn) であり、データを書き込む場合も同様に O(logn) です。 しかし、まだ間隔範囲検索は十分にサポートされていません。

5≤id≤20

のデータをクエリしたいとすると、最初に 10 個のノードの左側のサブツリーをクエリする必要があります。次に、10 ノードの左側のサブツリーをクエリします。最終的にすべてのデータをクエリできるのは、右側のサブツリーだけです。 結果として、そのようなクエリ効率は高くありません。

ジャンプ テーブル

スキップ テーブルは、上記のハッシュ テーブル、順序付けされた配列、バイナリ ツリーほど一般的ではないかもしれませんが、実際には、

Redis

の sort set はスキップ テーブルを使用して実装されます。 <p>ここでは、ジャンプ テーブルによって実現されるデータ構造の利点を簡単に紹介します。 </p> <p>誰もが知っているように、<strong>順序付きリンク リスト</strong> をクエリすることすら効率的ではありません。二分探索に配列添字を使用できないため、時間計算量は <code>o( n) になります。

しかし、以下に示すように、リンク リストを巧みに最適化して、二分検索を偽装して実装することもできます。

# プライマリを抽出できます。最下位データのインデックスとセカンダリ インデックス データ量に応じて、N レベルのインデックスを抽出できます。

クエリを実行するとき、ここのインデックスを使用して、二分検索を偽装して実装できます。

id=13 のデータをクエリしたいとします。必要なのは 4 つのノード 1->7->10->13## だけです。 # to query データの場合、数が大きいほど効率の向上がより顕著になります。

同時に、間隔クエリもサポートされています。これは、先ほどの単一ノードのクエリと似ています。開始ノードをクエリし、それを順番に走査するだけです (

リンクリストはターゲットノードへの順序です) データの全範囲がクエリされます。

同時に、インデックスには実際のデータを格納せず、ポインターのみを格納するため、データが格納される下部のリンク リストと比較して、占有されるスペースは無視できます。

バランス型バイナリツリーの最適化

しかし実際には、

MySQL の Innodb はスキップ テーブルを使用せず、 と呼ばれるテーブルを使用します。 B ツリー データ構造。

このデータ構造は、基本的なデータ構造として大学の先生がよく言う二分木のようなものではなく、実際のプロジェクトでの需要シナリオに応じて基本的なデータ構造を発展させたものであるためです。

たとえば、ここの

B ツリーは、バランスの取れた二分木から進化したものと考えることができます。

先ほど、バイナリ ツリーの間隔クエリ効率は高くないと述べましたが、これは最適化できます。元のバイナリ ツリー 最適化後: すべての非リーフ ノードはデータを格納せず、リーフ ノードのインデックスとしてのみ機能し、すべてのデータはリーフ ノードに格納されます。

このようにして、すべてのリーフ ノードのデータが順番に保存され、間隔クエリを適切にサポートできます。

最初に開始ノードの位置をクエリしてから、リーフ ノードを順番に走査するだけです。

データ量が膨大な場合、インデックス ファイルをメモリに格納できないことは明らかです。非常に高速ですが、多くのリソースを消費するため、

MySQL

はインデックス ファイルをディスクに直接保存します。

これは、後述する elasticsearch インデックスとは少し異なります。

#インデックスはディスクに保存されるため、ディスクの IO をできる限り削減する必要があります (ディスク IO の効率はメモリの効率とは桁違いです)

上の図からわかるように、データのクエリには少なくとも 4 回の IO 時間が必要です。明らかに、IO 回の回数はツリーの高さと密接に関係しています。ツリーの高さが低いほど、 、IO 回数が少ないほどパフォーマンスが向上します。

木の高さを低くするにはどうすればよいでしょうか?

#二分木を三項木に変更してみると、木の高さが大幅に下がり、数値が下がります。データクエリ時の IO は自然に減少し、クエリ効率が大幅に向上します。

実はこれが B ツリーの起源です。

インデックスの使用に関するいくつかの提案

実際、上の図の

B ツリー

を理解することで、日々の作業の細部を最適化することもできます。 ; たとえば、なぜ最も必要なのか 良いものは順番に増えていくのでしょうか？

書き込む主キー データが順序付けされていないと仮定すると、後で書き込まれるデータの ID が前に書き込まれたデータの ID よりも小さくなる可能性があります。これは、

B ツリー# を維持するときに必要になる可能性があります。 ## インデックス。モバイルはすでにデータを書き込んでいます。

データを増分的に書き込む場合は、このような考慮事項は必要なく、毎回順番に書き込むだけで済みます。

そのため、データベースの主キーは可能な限り増加傾向にする必要があり、最も合理的なのは、分割テーブルの状況を考慮せずに主キーを自動インクリメントすることです。

全体として、アイデアはスキップ テーブルのアイデアに似ていますが、使用シナリオに基づいて調整が行われています (たとえば、すべてのデータはリーフ ノードに格納されます)。 ES インデックス

MySQL

チャットの後、

Elasticsearch

がインデックスをどのように使用するかを見てみましょう。

前方インデックス

ESでは、

転置インデックス

と呼ばれるデータ構造が使用されます。転置インデックスについて正式に話す前に、彼の反対のがランク付けされることについて話しましょう。索引 ＃＃＃。

上の図は例です。doc_id を通じて特定のオブジェクトをクエリする方法は、Forward Index## を使用して呼び出されます。 # は、実際にはハッシュ テーブルとしても理解できます。

本質は、キーを通じて価値を見つけることです。

たとえば、

doc_id=4 を通じて、データ name=jetty wang,age=20 をすばやくクエリできます。

逆インデックス

次に、

name に li が含まれるデータをクエリしたい場合は?このように効率的にクエリを実行するにはどうすればよいでしょうか?

上記の順方向インデックスを使用するだけでは明らかに何の効果もありません。すべてのデータを順番に走査して、名前に

li が含まれているかどうかを判断することしかできません。これは非常に非効率です。

しかし、インデックス構造を再構築すると:

クエリを実行するとき、

name には li# が含まれます。 ## データの場合は、このインデックス構造を通じて Posting List に含まれるデータをクエリし、マッピングを通じて最終データをクエリするだけで済みます。 このインデックス構造は実際には

逆インデックス

です。 用語辞書

しかし、このインデックス構造で

li

を効率的にクエリするにはどうすればよいでしょうか? Term を追加する限り、これまでの経験と組み合わせることができます。順番に、バイナリ ツリー検索ツリーのデータ構造を使用して、o(logn) の下のデータをクエリできます。 テキストを独立した

Term

に分割するプロセスは、実際には単語の分割とよく呼ばれるものです。 すべての

Term

を結合したものが Term Dictionary であり、単語辞書とも呼ばれます。

英語の単語の分割は比較的簡単です。単語を分割するには、テキストをスペースと句読点で区切るだけです。中国語は比較的複雑ですが、それをサポートするオープンソース ツールも多数あります (この記事の主題ではないので、単語の分割については興味のある方はご自身で検索してください)。

• テキストの量が膨大な場合、単語分割後の

Term

が大量に存在することになります。このような転置インデックス データ構造がメモリに保存されていれば、間違いなくしかし、MySQL のようにディスクに保存されている場合、効率はそれほど高くありません。 用語インデックス

したがって、妥協方法を選択できます。

用語辞書

全体をメモリに入れることはできないため、用語辞書 インデックスを作成してメモリに置きます。 このようにして、

用語辞書

を効率的にクエリでき、最終的に投稿リストを用語辞書を通じてクエリできるようになります。 MySQL の

B ツリー

と比較すると、ディスク IO も数倍削減されます。

This

Term Index

この

トライ ツリー

を使用できます。これはよく言われることです辞書ツリーを保存します。 辞書ツリーの詳細については、ここを参照してください。

j

で始まる

Term

を検索する場合、最初のステップは # を検索することです。メモリ内の ##Term Index は、Term Dictionary 辞書ファイル内の j で始まる Term の位置をクエリします (この位置はファイル ポインタである場合があります) 、おそらく間隔範囲）。 次に、この位置範囲内のすべての Term を取り出します。これらはソートされているため、二分検索によって特定の位置をすばやく見つけることができます。このようにして、## をクエリできます。 #投稿リスト。

最後に、投稿リストの位置情報を介して、元のファイルから目的のデータを取得できます。 さらなる最適化

もちろん、ElasticSearch では、多くの対象を絞った最適化も行っています。2 つのフィールドを取得する場合、

bitmap

最適化を使用できます。

たとえば、name=li と age=18 のデータをクエリする必要があります。このとき、それぞれの結果 投稿リスト を取得する必要があります。この2つのフィールドを通じて。

最も簡単な方法は、2 つのコレクションを別々に走査して重複データを削除することですが、これは明らかに非効率です。

現時点では、bitmap メソッドを使用して保存することができ (ストレージ スペースも節約できます)、同時に固有の ビットと ** 計算を使用して、結果 を取得します。 **

[1, 3, 5] ⇒ 10101

##[1, 2, 4, 5] ⇒ 11011

このように、2 つのバイナリ配列を合計することで結果を取得できます:

10001 ⇒ [1, 5 ]##最終的に、

Posting List

は [1, 5] として解決され、当然、これははるかに効率的です。 MySQL には、同じクエリ要件に対する特別な最適化はありません。最初に少量のデータでデータをフィルタリングし、次に 2 番目のフィールドをフィルタリングするだけです。当然、効率は次のとおりです。あまり良くありません

ES

高いです。 もちろん、Posting List も

ES

の最新バージョンで圧縮されます。特定の圧縮ルールについては、公式ドキュメントを確認してください。ここで詳しく紹介されています。 要約最後に、要約しましょう:

上記の内容を通して、問題は問題ではないことがわかります。製品がどれほど複雑か、最終的には、それらはすべて基本的なデータ構造で構成されていますが、さまざまなアプリケーション シナリオに合わせて最適化されるため、データ構造とアルゴリズムの基礎をしっかりと固めた後は、いつでもすぐに使い始めることができます。新しいテクノロジーやミドルウェアを検討すると、最適化の方向性を自分で知ることもできます。

いよいよパイを描きます。将来的には、

ES

転置インデックスの考え方に基づいたスタンドアロンの検索エンジンを自分で書くだけで作ってみます。理解を深められるでしょうか。

関連する無料学習の推奨事項: mysql データベース

(ビデオ)

以上がMySQL インデックス VS ElasticSearch インデックスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。