rknfish

rknfish

i need more love
github

講義#08:ツリーインデックス

コースを参照する

ノートを参照する

スライドを参照する

カバー

[[目次]]


1. テーブルインデックス#

テーブルインデックスは、属性のコピーであり、主に高速化のために使用されます。

テーブルインデックスは、次の 2 つの要素を考慮しています。

  • メンテナンスコスト
  • 高速化の効果

2. B + ツリー#

B + ツリーの属性

B + ツリーは、自己バランス型のデータ構造であり、検索、挿入などの操作の時間複雑度は通常 $O (\log {n})$ であり、このデータ構造は比較的大きなデータブロックに最適化されています。

B + ツリーは、以下の特徴を持つM分探索木です:

  • 完全なバランス(すべての葉ノードのレベルが同じ)
  • ルートノード以外のノードは、M/2-1 <= #keys <= M-1のキーを持つ
  • すべてのキーが **k個のノードにはk+1** 個の非空の子ノードがあります。

B + ツリーの例

B + ツリーでは、葉ノードは最終的に必要なキーを格納する場所です。したがって、最終的な値を葉ノードに基づいて検索する場合、次の 2 つの方法があります。

  1. 値の場所を指すポインタを使用して保存します。
  2. 直接葉ノードに格納します。

B-Tree と B+Tree の比較#

B - ツリーと B + ツリーの最も重要な違いは、B - ツリーのキーが葉ノード以外にも存在することです。したがって、B - ツリーはストレージスペースの使用において明らかに優れています。

そのため、次のような問題が発生する可能性があります。

  1. B - ツリーでは、ノード間を行き来する必要がありますが、B + ツリーでは直接スキャンできます。
  2. B - ツリーでは、値をノードに格納する方法を使用すると、クエリが遅くなる可能性があります。

可視化#

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

挿入#

挿入するために葉ノードを見つけます。サイズに基づいて挿入します。

ノードに十分なスペースがある場合は、挿入を停止します。十分なスペースがない場合は、次の 2 つの手順を実行します。

  1. ノードを中央値で 2 つのノードに分割します。
  2. その中央値を親ノードにプッシュします。親ノードが存在しない場合は、親ノードを作成します。その後、親ノードに同じ操作を実行します。

削除#

削除するために葉ノードを見つけます。

葉ノードがキーを削除した後、少なくとも半分の容量がある場合は、削除を停止します。

葉ノードにキーがM/2-1個しかない場合、次の 2 つの戦略があります。

  • 隣接するノードから値を持ってくることを試みます。
  • 試みが失敗した場合、2 つのノードを結合しようとします。

選択条件#

ツリー構造のクエリには利点と欠点があります。

重複キー#

重複するキーを解決するためには、次の 2 つの方法があります。

  1. すべてのキーの後にレコード ID を追加して、各キーが一意であることを保証します。
  2. オーバーフローノードを使用して、これらの重複情報を保存します。
    オーバーフローノード

クラスタ化インデックス#

通常、テーブルは主キーに基づいてインデックスが作成されます。

ただし、一部のデータベースでは、クラスタ化インデックスを使用して、テーブルに非表示の主キーを追加します。他のデータベースでは、このインデックスを使用できない場合があります。


3. B + ツリーの設計選択肢#

ノードサイズ#

通常、ストレージデバイスが遅いほど、使用するノードサイズが大きくなります。

  • HDD:約 1MB
  • SSD:約 10KB
  • インメモリ:約 512B

マージの閾値#

一部の DBMS では、常に半分の容量のノードをマージしない場合があります。

なぜなら、マージ操作を遅延させると、再バランスのコストを減らすことができるからです。

いくつかの比較的小さなノードを維持し、定期的にツリーを再構築する方が良い場合があります。

可変長キー#

  1. ポインタを使用して値の場所を保存します。B + ツリーには値へのポインタのみが格納されます。
  2. 可変長のノードを使用します。
  3. すべての値を固定サイズで B + ツリーに保存します。
  4. マップ形式で保存します。

ノード内検索#

  1. 線形
    • ノードを線形にスキャンします。
    • SIMD テクノロジーを使用してスキャンするデータ量を増やすことができます。
  2. 二分
    二分探索を使用して検索します。
  3. 補間
    値に基づいて位置を知ることができます。
    補間

4. 最適化#

接頭辞圧縮#

共通の接頭辞を抽出して圧縮します。

接頭辞圧縮

重複排除#

インデックスが一意でないすべての値に対して、これらの値を 1 つのキーに統合することができます。

重複排除

接尾辞切り捨て#

この方法では、ノード内で比較可能な小さな接頭辞長を選択して、検索を行います。

切り捨て 1

切り捨て 2

ポインタの置き換え#

B + ツリー内のページ ID をバッファプールに固定し、重複したディスクの読み取りを回避し、アクセスを高速化することができます。次に、ページ ID のポインタをメモリ内の実際の値に置き換えることで、バッファプールの変換をバイパスして直接アクセスできます。

一括挿入#

ツリーを再構築する最速の方法は、下から上にツリーを構築することです。

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。