Mysql インデックスと Redis ジャンプテーブルについての簡単な説明

まとめ

インタビュー中、MySQL インデックスの問題について議論しているときに、B+ ツリー、B ツリー、バランスト バイナリ ツリーの違いについては話せるが、B+ ツリーとハッシュ インデックスの違いはわからない人がいることに気付きました。これは単なる暗記であり、インデックス作成の本質を理解していないことは明らかです。この記事は、この背後にある原則を分析することを目的としています。ぜひメッセージを残して議論してください。

質問

以下の質問について混乱したり、漠然としか理解していない場合は、読み続けてください。この記事は間違いなく役立つと思います。

• MySQLインデックスの実装方法
• mysql インデックス構造の B+ ツリーとハッシュの違いは何ですか?どのようなシナリオに適していますか?
• データベースインデックスを実装する他の方法はありますか?
• Redisジャンプテーブルはどのように実装されるか
• スキップ リスト、B+ ツリー、LSM ツリーの違いは何ですか?

分析

まず、なぜ MySQL インデックスと Redis スキップ テーブルを一緒に説明する必要があるのでしょうか。それは、指定されたキーに従ってデータ セットの場所 (または対応する値) をすばやく見つけるという同じ問題を解決するからです。

この観点から問題を考えると、B+ ツリー インデックスとハッシュ インデックスの違いがまだわからないのでしょうか?

データセットを見つける問題

これで、データ セットの検索の問題を解決するために、問題領域の境界を明確に定義できました。この点に関してどのような問題を考慮する必要がありますか?

1. どのような検索方法をサポートする必要があるか、単一キー/複数キー/範囲検索、
2. 挿入/削除効率
3. 検索効率（つまり時間計算量）
4. ストレージサイズ（スペースの複雑さ）

よく使われる検索構造をいくつか見てみましょう

ハッシュ

ハッシュはキーと値の形式です。ハッシュ関数を使用すると、キーに応じて値をすばやく見つけることができます。

B+ ツリー

B+ ツリーはバランスのとれた二分木から進化しました。アルゴリズムの授業で B+ ツリーやスキップ リストのような構造について学ばなかったのはなぜでしょうか?なぜなら、それらはすべてエンジニアリングの実践から得られたものであり、理論に基づいて妥協されているからです。

B+ ツリーは、まず第一に順序付けられた構造です。ツリーが高くなりすぎて検索効率に影響するのを防ぐために、単一のデータではなくページのデータがリーフ ノードに格納され、検索効率が向上します。範囲クエリをより適切にサポートするために、B+ ツリーはリーフ ノードに非リーフ ノード データを冗長的に格納します。ページめくりをサポートするために、リーフ ノードはポインタによって接続されます。

ジャンプテーブル

ジャンプ リストは、Redis のソート セット データ構造を実装するために、リンク リストに基づいて拡張されます。レベル 0: 元のデータが格納されます。順序付けされたリンク リストです。各ノードはチェーン上にあります。レベル 0+: ノードはポインターを介して直列に接続されます。元のデータのサブセットです。レベルが高くなるほど、直列に接続されるデータが少なくなります。これにより、検索効率が大幅に向上します。

要約する

LSM構造に興味がある方は、cassandra vs mongo (1) ストレージエンジンをご覧ください。

Cassandra vs Mongo (1) ストレージエンジン

まとめ

ストレージエンジン:

Bツリー

キャッシュ管理

キャッシュ管理の中核は置換アルゴリズムにあります。一般的な置換アルゴリズムには、FIFO (先入れ先出し) と LRU (最長時間未使用) があります。リレーショナルデータベースは、主にLIRS（Low Inter-reference Recency Set）を使用して、LRUに基づいて改良されてきました。
キャッシュは2つのレベルに分かれています。第1レベルではLRUを使用します。最近使用されたデータは第1レベルに入ります。データが短期間に2回以上アクセスされると、ホットデータとなり第2レベルに入ります。これにより、テーブル全体のスキャンを実行するときに、キャッシュ内の大量のホット データが置き換えられる状況を回避できます。

エルエスエム

ログ構造化マージツリー: 構造化マージツリーの中心的な考え方は、データをメモリからディスクにすぐに書き込むのではなく、まずメモリに保存し、一定量のデータが蓄積された後にディスクにフラッシュすることです。

LSM 対 B ツリー

LSM は、B ツリーに基づいて書き込みパフォーマンスを向上させるために読み取りパフォーマンスをある程度犠牲にし、ブーム フィルターなどの他の実装を使用して読み取りパフォーマンスを補います。

1. 書く

B ツリーに書き込む場合、最初のステップは対応するブロックの場所を見つけて、新しいデータを挿入することです。書き込まれるデータが増えるにつれて、B ツリー構造を維持するためにノードを分割する必要があります。これにより、データを挿入するときにランダム書き込みの可能性が高まり、パフォーマンスが低下します。

LSM はメモリ内に小さなソートされたツリーを形成し、ディスクにフラッシュするときにそれを継続的にマージします。すべての書き込みはディスクではなくメモリ内で行われるため、書き込みは非常に効率的です。

2. 読む

B ツリーは、ルート ノードからリーフ ノードへのバイナリ クエリから開始され、一度に 1 つのノードを読み取ります。対応するページがメモリ内にない場合は、ディスクが読み取られてデータがキャッシュされます。

LSM ツリーの構造全体は順序付けられていないため、データがどこにあるかはわかりません。順序付けられた小さな構造ごとにバイナリ クエリを実行する必要があります。データが見つかった場合は、それを返します。データが見つからない場合は、次の順序付けられた構造を探し続けます。そのため、LSM は読み取りパフォーマンスを犠牲にします。しかし、LSM が大規模データ ストレージ システムとして使用できる理由は、読み取りパフォーマンスを他の方法で向上できるからです。たとえば、読み取りパフォーマンスは、ディスク読み取りよりもメモリ/キャッシュ ヒット率に大きく依存します。

カサンドラ

Cassandra は、読み取りパフォーマンスよりも書き込みパフォーマンスが優れている NoSql データベースです。書き込みパフォーマンスが優れている理由の 1 つは、LSM ストレージ エンジンを使用していることです。

モンゴ

MMAPv1

Mongo 3.2 以前では、B ツリー型に基づく MMAPv1 ストレージ エンジンがデフォルトで使用されていました。

パディング

MMAPv1 ストレージ エンジンは、「レコード割り当て」と呼ばれるプロセスを使用して、ドキュメントの保存用のディスク領域を割り当てます。 MongoDB と Cassandra の違いは、元のドキュメントを更新する必要があることです。元のドキュメントのスペースが不十分な場合は、ドキュメントを新しい場所に移動し、対応するインデックスを更新する必要があります。これにより、不要な更新やデータの断片化が発生します。

上記の状況を回避するために、ドキュメントのスペースを事前に割り当てる境界の概念があります。しかし、これはリソースの無駄遣いにつながる可能性があります。 Mongo は、64M、128M、256M...2G の 2 の累乗増加戦略に従って、最大 2G まで事前割り当てします。データサイズが小さい場合には問題は明らかではありませんが、2G に達すると、ディスク使用量が大きくなるという問題が明らかになります。

これは、長いレコード データを個別に保存するリレーショナル データベースとも異なります。

ロック

MMAPv1 はコレクション レベルのロックを使用します。つまり、一度に 1 つのコレクションのみを追加、削除、または変更できます。同時操作を実行すると待機が発生します。

ワイヤードタイガー

3.2 以降のデフォルトのストレージ エンジンも B-Tree に基づいています。ロックフリーやリスクポインターなどの並行テクノロジを使用して、マルチコアマシンでより適切に動作するようにしています。

ロック レベルはドキュメントです。また、ディスク使用量を削減するために圧縮が導入されました。

要約する

以上がこの記事の全内容です。この記事の内容が皆様の勉強や仕事に何らかの参考学習価値をもたらすことを願います。123WORDPRESS.COM をご愛顧いただき、誠にありがとうございます。