B+ ツリー そして LSM ツリー の構成要素について話すとき、これらは 2 つの基本的なデータ構造です。 データベース。 B+ ツリーは、検索と挿入にかかる時間を短縮する必要がある場合に使用されます。一方、LSM ツリーは、書き込みが集中するデータセットがあり、読み取りがそれほど多くない場合に使用されます。
この記事では、について説明します ログ構造化マージ ツリー 別名 LSM ツリー 。 LSM ツリーは、Amazon の DynamoDB、Cassandra、ScyllaDB など、多くのスケーラビリティの高い NoSQL 分散キー値型データベースの基礎となるデータ構造です。
LSM ツリー
LSM ツリーの単純なバージョンは、2 レベルのツリー状のデータ構造で構成されます。
- Memtable であり、完全にメモリ内に常駐します (T0 としましょう)
- ディスクに保存された SStable (T1 としましょう)
シンプルな LSM ツリー
新しいレコードが memtable T0 コンポーネントに挿入されます。挿入によって T0 コンポーネントが特定のサイズのしきい値を超える場合、エントリの連続セグメントが T0 から削除され、ディスク上の T1 にマージされます。
LSM ワークフロー
LSM は主に 3 つの概念を使用して読み取りおよび書き込み操作を最適化します。
- ソートされた文字列テーブル (SSTable) : データはソート順にソートされるため、データが読み取られるたびに、その時間計算量は最悪の場合でも O( Log(N) ) になります。ここで、N はデータベース テーブル内のエントリの数です。
1.SSTテーブル
- メムテーブル :
- インメモリ構造
- データを並べ替えて保存します
- ライトバックキャッシュとして機能します
- 特定のサイズに達すると、そのデータは SSTable としてデータベースにフラッシュされます。
- ディスク内の SSTable の数が増加し、レコードにキーが存在しない場合
- そのキーを読み取るときに、すべての SSTable を読み取る必要があるため、読み取り時間の複雑さが増加します。
- この問題を解決するには、ブルーム フィルターが登場します。
- ブルーム フィルターは、レコード内にキーが欠落しているかどうかを 99.9% の精度で知らせることができる、スペース効率の高いデータ構造です。
- このフィルターを使用するには、書き込み時にエントリーを追加し、最初にリクエストが来たときにより効率的にリクエストを処理するために、読み取りリクエストの先頭でキーをチェックします。
Memtable 表現
- 圧縮 :
- データを SSTable としてディスクに保存しているので、 N SSTable と各テーブルのサイズは M
- それでは最悪の場合 読む 時間計算量は O( N* ログ(M) )
- したがって、SSTable の数が増えると、 読み取り時間の複雑さ も増えます。
- また、データベース内の SSTable をフラッシュしているだけの場合、同じキーが複数の SSTable に存在します。
- ここでコンパクターの使用が始まります
- Compactor はバックグラウンドで実行され、SSTable をマージして複数の行を削除し、最新のデータを含む新しいキーを追加して、新しいマージ/圧縮された SSTable に保存します。
3.1. SSTable がディスクにフラッシュされました
3.6.コンパクターは 2 つの SSTable を 1 つの SSTable に圧縮しました
結論：
- 書き込みはメモリ内ツリー (Memtable) に保存されます。サポートされているデータ構造 (ブルーム フィルターとスパース インデックス) も必要に応じて更新されます。
- このツリーが大きくなりすぎると、ソートされた順序でキーとともにディスクにフラッシュされます。
- 読み取りが入ってくると、ブルーム フィルターを使用してそれをチェックします。ブルーム フィルターが値が存在しないことを示した場合、キーが見つからなかったことをクライアントに伝えます。ブルーム フィルターが値が存在することを意味する場合は、最新のものから最も古いものへ SSTable の反復を開始します。
- LSM の時間計算量
- 読む時間: O(log(N)) ここで、N はディスク内のレコードの数です。
- 書き込み時間: ○(1) メモリ内に書き込むとき
- 削除時間: O(log(N)) ここで、N はディスク内のレコードの数です。
- LSM ツリーは、3 つ以上のフィルターを使用して、より効率的なデータ構造に変更できます。それらの一部には、bLSM、Diff-Index LSM があります。