この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 6日目の記事です。
はじめに
どうも、最近終わったはずの卒研に追加要求が出てきて非常にしんどい気持ちになっているけんつです。
今回は Tree Index です。
実はこれ、この記事を書き終わってから書いているのですが、この記事だけ異様に時間がかかっているので何書いてんだろうなって自分でも思ってます。
Tree Indexes
Indexes
テーブルインデックスとはテーブルの列に対するサブセットのレプリカである。
また DBMS はテーブルのコンテンツとインデックスが常に同期的されていることを保証する必要がある。
DBMS の責務は他にもあり、クエリが実行された際に適切なインデックスの利用することもその一つである。*1
一般的に要素の、つまりタプルの検索に使用されることが多いがこれにはメリットだけでなく、インデックスを多く生成すればそれだけストレージで管理する要素数が増えてしまうのでトレードオフとなる。*2
B+ Tree
インデックスを構築するにも様々なデータ構造があるが DBMS 特に RDBMS で一般的な B+ Tree を取ることを考える。
まず B+ Tree とは、データのソートを維持し、検索、追加、削除を O(log n) で行うことができる平衡探索木を指す。
また順序を維持する必要がある DBMS では大体 B+ Tree でインデックスが構成される。
B+ Tree 自体は B Tree をベースに B Link Tree の相互参照ポインタなど他の B Tree データ構造がもつ特性を合わせて実装される。
更に正確に言うのであれば、B+ Tree は次のような特性を持つ M-way Search Tree のことを指す。
- 全てのリーフ濃度の深さは同じになっている
- root 以外の内部ノードは最低でも半分以上データが入っている。
- k個のキーを保持する内部ノードは k+1 個の null でない子要素を保持する。
B+ Tree の全てのノードには、Key-Value のペアの配列が含まれる。
- すべてのノード配列はキーでソートされる
- 内部ノードの値配列には他のノードへのポインタを保持する
- リーフノード値に対する２つのアプローチとして、レコードIDとタプルデータが存在する。
B+ Tree の操作
Insert
- まずリーフである L を探索する
- ソートされた順序で L にデータを追加する
- 追加できない場合は L を L1, L2 と分割して、それぞれの要素が均等になるように再構築して中間キーをコピーする
- 内部ノードを分割する場合は、要素を均等に分配し中央のキーを親ノードにする。
Delete
- リーフ L を探索する
- エントリを削除する
- 削除後 L が含む要素数が上限値の半分より多い場合は削除を完了する
- その他の場合では隣接するリーフノードを動かすことができる場合も存在する
- 上のパターンで再構築できなかった場合は、 L と隣接ノードをマージして親を削除する
B+ Tree の設計
ノードサイズ
- B+ Tree のノードサイズはディスクの速度に依存する。可能な限り多くのタプルをノードをディスクからメモリ上に配置することを考慮する。
- ディスクの速度が遅いほどノードサイズを大きくする
- いくつかの手法ではより多くのキーに対する参照を保持するのとスキャンが遅くなることのトレードオフを考える必要がある
マージの境界線
可変長キーの扱い
- ポインタ： キーをタプルへのポインタとして保存する。(ほとんど使用されない)
- 可変長ノード: B Tree の各ノードサイズを可変にする。メモリ管理のコストが上がるためあまり使用されない
- キーマップ: ノード内の Key-Value のリストにマップするポインタの配列を含ませる。スロットページに似たアプローチを取る
ユニークでないインデックス
- 重複キー: 同じノードレイアウトを使用するが、重複キーを複数保存する
- 値リスト: それぞれのキーを一回だけ保存して一意な値リストを維持する
ノード内検索
- 線形探索: ノードの Key-Value エントリーを探索するべきキーが見つかるまでフルスキャンする。
- 二分探索: その名の通り。事前にノードがソートされている必要がある。
- 補間探索: ノード内の既知のキー値に基づいて検索の開始位置を概算する。その位置から線形探索する。これも事前にソートされている必要がある。
B+ Treeの最適化
インデックスの追加的な利用
- 暗黙的なインデックス： 殆どの DBMS で行われている様にインデックスを自動生成して主キー等に適用されるものがある
- 部分的なインデックス： テーブルのサブセットに対してインデックスを貼る。これによってインデックスそのもののサイズとそれの管理コストが減る可能性がある
- カバーインデックス: クエリを実行する上で必要な全ての属性はインデックスを利用できるため、タプルを取得する必要がない場合がある
- インデックスを含む列: インデックスのみのクエリをサポートするためにインデックスに追加の列を埋め込む。
- 関数/式インデックス: 関数、式の出力を元の値でなくキーとして保存する。そのインデックスがどういったクエリで使用できるかは DBMS が決める必要がある
スキップリスト
スキップリストは中間ノードをスキップする複数のレベルにおける追加ポイントを持つソートされた単方向リストを指す。
一般的に O(log n) で検索を行うことが出来る。これは B+ Tree 以外のインデックスを構築するためのデータ構造として利用することが出来る。
これが B+ Tree を超える点として、B+ Tree より少ないメモリで構成できる点やインサートデリートでデータ構造を再構成する必要が無い点にある。
また逆に B+ Tree と比較した場合の欠点として、ローカリティを最適化しないために、ディスク/キャッシュフレンドリーでは無い点や、双方向リストを実装しない限り逆方向への探索がコストかかるから。
おわりに
卒研やら内定者懇親会へ行ったりしていたら気がつけばこの記事を書くことに一週間も費やしてしまった。
全く理解できていないので、一周した後に加筆修正する必要がありそう。