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) の新しい使い方のまとめ

推薦する

HTMLポップアップ透明レイヤーインスタンスのサイズを設定でき、比例することができます

コードをコピーコードは次のとおりです。 <!DOCTYPE html PUBLIC "...

CSS 背景と境界タグの例の詳細な説明

1. CSS背景タグ1.背景色を設定するbackground-ground-color プロパティは...

vue-nuxt ログイン認証の実装

目次導入リンク始めるコードを読み進めてくださいプロキシ設定傍受を要求する異なるプレフィックスを持つイ...

ハイパーリンクを表示して開く方法

<br />インターネット上の無数の情報は基本的に HTML ドキュメントで構成されてお...

HTML構造化実装方法

DIV+css構造 CSSレイアウトを学んでいますか?まだ純粋な CSS レイアウトを完全に習得でき...

HTML テーブル マークアップ チュートリアル (42): テーブル ヘッダーの水平方向の配置属性 ALIGN

水平方向では、テーブル ヘッダーの配置を左、中央、右に設定できます。基本的な構文<TH ALI...

MySQLのパラメータについてお話しましょう

序文:以前の記事では、特定のパラメータの機能についてよく紹介してきました。しかし、MySQL パラメ...

ローカルストレージにブール型の値を保存する際の落とし穴を解決する

LocalStorageはブール値を保存します今日、ブール値データを保存するために localsto...

axiosリクエストをvueでカプセル化する方法

実際、Vueでaxiosをカプセル化するのは非常に簡単ですまず、srcパスにhttpフォルダを作成し...

linuxdeployqt を使用して Ubuntu で Qt プログラムをパッケージ化する問題を解決する

いくつかの Qt インターフェース プログラムを作成しましたが、Qt 環境がインストールされていない...

vue-cli4.5.xはプロジェクトを素早く構築します

1. vue-cliをインストールする vue.js で vue.js を実行します。 2. プロジ...

印刷広告を成功させるための「3I」基準

国内の多くの広告主にとって、印刷広告の制作と評価は、しばしばかなり主観的です。自分の感情や美的感覚に...

JavaScript ファイルの読み込みとブロックの問題: パフォーマンス最適化のケーススタディ

まず質問させてください。HTML ページを作成するときに、外部から JS ファイルをインポートする場...

Alibaba Cloud centos7にmysql8.0.22をインストールする詳細なチュートリアル

1. MySQLインストールパッケージをダウンロードするまず、https://dev.mysql.c...

自動行折り返し機能付き CSS Flex レイアウトのサンプル コード

フレックス コンテナーを作成するには、要素に display: flex プロパティを追加するだけで...