[[目次]]
1. テーブルインデックス#
テーブルインデックスは、属性のコピーであり、主に高速化のために使用されます。
テーブルインデックスは、次の 2 つの要素を考慮しています。
- メンテナンスのコスト
- 高速化の効果
2. B + ツリー#
B + ツリーは、自己バランス型のデータ構造であり、検索、挿入などの操作の時間複雑度は通常 $O (\log {n})$ であり、このデータ構造は比較的大きなデータブロックに最適化されています。
B + ツリーは、次の特徴を持つM分探索木です：
- 完全にバランスしています（すべての葉ノードのレベルが同じです）
- ルートノード以外のノードは、
M/2-1 <= #keys <= M-1のキーを持ちます - 各ノードは、**
k個のキーを持つ場合、k+1** 個の非空の子ノードを持ちます。
B + ツリーでは、葉ノードは最終的に必要なキーを格納する場所です。したがって、最終的な値を葉ノードに基づいて検索する場合、次の 2 つの方法があります。
- 値が格納されている場所にポインタを記録します。
- 直接葉ノードに格納します。
B - ツリーと B + ツリーの比較#
B - ツリーと 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 のポインタをメモリ内の実際の値に置き換えることで、バッファプールの変換をバイパスして直接アクセスできます。
一括挿入#
ツリーの再構築は、下から上に向かって行う場合が最も速い方法です。