[[目次]]
1. テーブルインデックス#
テーブルインデックスは、属性のコピーであり、主に高速化のために使用されます。
テーブルインデックスは、次の 2 つの要素を考慮しています。
- メンテナンスコスト
- 高速化の効果
2. B + ツリー#
B + ツリーは、自己バランス型のデータ構造であり、検索、挿入などの操作の時間複雑度は通常 $O (\log {n})$ であり、このデータ構造は比較的大きなデータブロックに最適化されています。
B + ツリーは、以下の特徴を持つM分探索木です：
- 完全なバランス（すべての葉ノードのレベルが同じ）
- ルートノード以外のノードは、
M/2-1 <= #keys <= M-1のキーを持つ - すべてのキーが **
k個のノードにはk+1** 個の非空の子ノードがあります。
B + ツリーでは、葉ノードは最終的に必要なキーを格納する場所です。したがって、最終的な値を葉ノードに基づいて検索する場合、次の 2 つの方法があります。
- 値の場所を指すポインタを使用して保存します。
- 直接葉ノードに格納します。
B-Tree と B+Tree の比較#
B - ツリーと B + ツリーの最も重要な違いは、B - ツリーのキーが葉ノード以外にも存在することです。したがって、B - ツリーはストレージスペースの使用において明らかに優れています。
そのため、次のような問題が発生する可能性があります。
- B - ツリーでは、ノード間を行き来する必要がありますが、B + ツリーでは直接スキャンできます。
- B - ツリーでは、値をノードに格納する方法を使用すると、クエリが遅くなる可能性があります。
可視化#
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
挿入#
挿入するために葉ノードを見つけます。サイズに基づいて挿入します。
ノードに十分なスペースがある場合は、挿入を停止します。十分なスペースがない場合は、次の 2 つの手順を実行します。
- ノードを中央値で 2 つのノードに分割します。
- その中央値を親ノードにプッシュします。親ノードが存在しない場合は、親ノードを作成します。その後、親ノードに同じ操作を実行します。
削除#
削除するために葉ノードを見つけます。
葉ノードがキーを削除した後、少なくとも半分の容量がある場合は、削除を停止します。
葉ノードにキーがM/2-1個しかない場合、次の 2 つの戦略があります。
- 隣接するノードから値を持ってくることを試みます。
- 試みが失敗した場合、2 つのノードを結合しようとします。
選択条件#
ツリー構造のクエリには利点と欠点があります。
重複キー#
重複するキーを解決するためには、次の 2 つの方法があります。
- すべてのキーの後にレコード ID を追加して、各キーが一意であることを保証します。
- オーバーフローノードを使用して、これらの重複情報を保存します。
クラスタ化インデックス#
通常、テーブルは主キーに基づいてインデックスが作成されます。
ただし、一部のデータベースでは、クラスタ化インデックスを使用して、テーブルに非表示の主キーを追加します。他のデータベースでは、このインデックスを使用できない場合があります。
3. B + ツリーの設計選択肢#
ノードサイズ#
通常、ストレージデバイスが遅いほど、使用するノードサイズが大きくなります。
- HDD：約 1MB
- SSD：約 10KB
- インメモリ：約 512B
マージの閾値#
一部の DBMS では、常に半分の容量のノードをマージしない場合があります。
なぜなら、マージ操作を遅延させると、再バランスのコストを減らすことができるからです。
いくつかの比較的小さなノードを維持し、定期的にツリーを再構築する方が良い場合があります。
可変長キー#
- ポインタを使用して値の場所を保存します。B + ツリーには値へのポインタのみが格納されます。
- 可変長のノードを使用します。
- すべての値を固定サイズで B + ツリーに保存します。
- マップ形式で保存します。
ノード内検索#
- 線形
- ノードを線形にスキャンします。
- SIMD テクノロジーを使用してスキャンするデータ量を増やすことができます。
- 二分
二分探索を使用して検索します。 - 補間
値に基づいて位置を知ることができます。
4. 最適化#
接頭辞圧縮#
共通の接頭辞を抽出して圧縮します。
重複排除#
インデックスが一意でないすべての値に対して、これらの値を 1 つのキーに統合することができます。
接尾辞切り捨て#
この方法では、ノード内で比較可能な小さな接頭辞長を選択して、検索を行います。
ポインタの置き換え#
B + ツリー内のページ ID をバッファプールに固定し、重複したディスクの読み取りを回避し、アクセスを高速化することができます。次に、ページ ID のポインタをメモリ内の実際の値に置き換えることで、バッファプールの変換をバイパスして直接アクセスできます。
一括挿入#
ツリーを再構築する最速の方法は、下から上にツリーを構築することです。