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

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+: ノードはポインターを介して直列に接続されます。元のデータのサブセットです。レベルが高くなるほど、直列に接続されるデータが少なくなります。これにより、検索効率が大幅に向上します。

要約する

データ構造実施原則キークエリメソッド検索効率ストレージサイズ挿入と削除の効率
ハッシュハッシュテーブル単一キーをサポートO(1)に近い小型で、データ以外の追加ストレージはありませんオー(1)
B+ ツリーバランスのとれた二分木から拡張単一キー、範囲、ページングO(Log(n)データに加えて、左と右のポインタ、およびリーフノードのポインタもあります。 O(Log(n))、ツリー構造を調整する必要があり、アルゴリズムはより複雑になる
ジャンプテーブル順序付きリンクリストから拡張単一キー、ページングO(Log(n)データに加えてポインターがありますが、ノードあたりのポインターの数は 2 未満なので、B+ ツリーよりも占有スペースが少なくなります。 O(Log(n)、リンクリストを処理するだけで済むため、アルゴリズムは比較的単純です。

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 をご愛顧いただき、誠にありがとうございます。

以下もご興味があるかもしれません:
  • 初心者向けMySQLインデックス
  • 異なるインデックスを更新してMySQLのデッドロックルーチンを解決する
  • ユニークインデックスの S ロックと X ロックによる MySQL デッドロック ルーチンの理解
  • MySQLインデックスに関する重要な面接の質問をいくつか共有します
  • MySQLのインデックス
  • MySQL 学習 (VII): Innodb ストレージ エンジン インデックスの実装原理の詳細説明
  • シェルスクリプトを使用してMySQLにインデックスを追加する方法
  • MySQL バッチ挿入とユニークインデックスの問題に対する解決策
  • MySQL インデックスの効率的な使用ガイド

<<:  Vue+element ui はアンカーの配置を実現します

>>:  Linux での vi (vim) の新しい使い方のまとめ

推薦する

Windows はリモート デスクトップが長時間自動的に切断されるのを防ぎます

Windows リモート デスクトップを使用してサーバーに接続したことがある人なら、リモート デスク...

JavaScript でオブジェクトのプロパティを削除する方法

1. 削除delete は、オブジェクトのプロパティを残さずに削除する唯一の方法ですが、その「代替」...

Windows で mysql-8.0.18-winx64 をインストールするチュートリアル (画像とテキスト付き)

1. インストールパッケージをダウンロードするインストール パッケージは次の場所にあります:参考:...

今日は、珍しいけれど役に立つJSテクニックをいくつか紹介します

1. 戻るボタンhistory.back() を使用してブラウザの「戻る」ボタンを作成します。 &l...

JavaScript データのフラット化の詳細な説明

目次フラット化とは何か再帰トストリング減らすアンダーコア_.平坦化_。連合_。違い要約するフラット化...

CSS3のボックスサイズプロパティの興味深いボックスモデルについての簡単な説明

誰もがボックス モデルの構成を、内側から外側まで、コンテンツ、パディング、境界線、マージンについて知...

MySQL解凍版のインストール手順の詳しい説明

1. 公式サイトにアクセスします: D:\mysql-5.7.21-winx64\bin をダウンロ...

Pythonの関数知識についての簡単な説明

目次関数パラメータの2つの主要なカテゴリ位置パラメータ可変長パラメータ名前空間要約する関数パラメータ...

MySQL 5.7 共通データ型

——「MySQL in Simple Terms (第 2 版)」からのメモ数値型整数型バイト最小最...

Linux Cron によるパラメータ付き PHP コードのスケジュール実行

1. 引き続き PHP スクリプトを使用して実行します。コマンドラインに入力: php /home/...

Tik Tok サブスクリプション ボタンのアニメーション効果を実現する CSS

少し前にTik Tokを見ていて、フォローするときのボタンアニメーションがとても美しいと思ったのと、...

ウェブレスポンシブレイアウトにおけるiframe適応の方法

問題<br />レスポンシブ レイアウトでは、iframe 要素に注意する必要があります...

CSS で text-align と margin: 0 auto を使用して中央に配置する例コード

CSSでtext-align、margin: 0 autoを使用して中央揃えにするtext-alig...

スライドによるページめくり効果とクリックイベント問題をモバイル端末上で実装する

前述のこの記事はとても短いです〜主な目的は、モバイル端末上のクリックと js イベントのメカニズムに...

Linux whatisコマンドの使い方

01. コマンドの概要whatis コマンドは、システム コマンドの簡単な説明を含むいくつかの特別な...