# CMU DB 7. Trees Indexes I
tags: CMU DB
今回はB+木について扱うようです．
授業
データ構造は
- internal meta-data
- core data storage
- temporary data structures
- table indexes
に使われる．今回はtable indexesについて扱う．
table indexはテーブルの特性の複製で，効率的にアクセスできるように整列されている
DBMSはテーブルの内容とindexが論理的に同期されていることを保証している．
DBMSはそれぞれのクエリを実行するために使う最高のindexを見つけることが仕事．
データベースごとのindexの数にはトレードオフがある．
- storage overhead
- maintenance overhead
B+ Tree
- B-tree
- B+ tree
- B* tree
- B-link-tree
というのがある．
B+ treeは自己均衡型の木構造でデータを整列した状態にし，探索，連続アクセス，挿入，削除を$O(\log n)$で出来る
根以外のノードは少なくとも半分は埋まっている([M/2-1 <= #keys <= M-1])
[<node*>|<key>]のように並んでいる．
- 全ての
B+ treeノードはkey/valueのペアの配列によって構成されているkeysはインデックスが基づくattributeに由来するvaluesはそのノードがinnder nodesとleaf nodesのどちらに分類されているかで異なる- 配列はよく整列された
keyの順序で保持されている
leaf nodeのvaluesに関して以下の2種類のアプローチがある．
- record ids
- index entryの対応するタプルのポインタへのポインタ
tuple data
B-Treeは全てのノードにkeyとvalueがあるB+ treeはleaf nodesしかvalueを持たず，inner nodesは探索処理の手伝うだけ
このリンクが使える．
primary keyによって指定された整列順序でテーブルに格納される．heapでもindex管理でも大丈夫
DBMSにはいつもclustered indexを使っているものもある．もしprimary keyをテーブルが持っていないとき，DBMSは自動で隠れた行idのprimary keyを作る
他のDBMSはclustered indexを全く使えない．
Design Decisions
ストレージが遅いほど，最適なノードのサイズは大きくなる．
仕事量によって最適なサイズは異なることがありうる．
いくつかのDBMSでは半分満杯のときにノードを必ずしも統合しない．
統合の処置を遅らせることは再編の量を減らすかも知れない．
underflowが生じることを許して，定期的に全ての木を再構築する方もまた良い可能性がある．
変数の長さに関して以下の取り組み方がある．
- pointers
- variable
- length nodes
- padding
- key map/indirection
一意でないindexには以下の取り組みがある．
- duplicate keys
- value lists
intra-node searchには以下の取組がある．
- linear
- binary
- interpolation
Optimizations
- prefix compression
- 同じleaf nodeにある整列されたkeyは同じprefixを持つ傾向にある
- 共通のprefixを除いて，一意なsuffixのみをkeyに保持する
- suffix truncation
- inner nodeにあるkeyのindexへ繋がるように正しく道案内するために必要な最低限のprefixのみを保存する
- bulk insert
B+ treeを構築する最速な方法はkeyを整列し，下からindexを構築すること
- pointer swizzling
- ノードはindexの他のnodeを参照するためにpage idを使う
- DMBSは探索の間にpage tableからメモリの場所を下に入れなければならない．
- もしページがbuffer poolピン留めされていたら，page idの代わりに生ポインタを保持することが可能
- これはpage tableからアドレスを探すことを避ける
結論
由緒あるB+ treeはいつもDBMSによって良い選択肢である．
感想
頭にあまり入っていない...多分風邪引いた...
今回はB+ treeの話ばかりであまり面白くなかった
