# CMU DB 8. Trees Indexes II
tags: CMU DB
風邪でやらなくなってから時間が空いたけど再開．継続出来る人はすごい(しみじみ)
授業
More B+ Trees
キーに複製対する対処法は
- tupleにrecord IDを付け加える
- 葉に新たなtupleを付け加えて複製キーを持てるようにする
大半のDBMSは自動でintegrityの制約を矯正するため(参照の制約ためでなく)indexを作成する
Additional Index Magic
- partial index
- covering index
- functional/expression index
Tries/Radix Trees
B+木内部ノードのキーはあるキーがindexに存在するかは教えてくれないので，葉ノードを走査する必要がある．つまり，少なくとも1つのbuffer pool持つ可能性があることを意味している．
Trie indexは全体を比較する代わりに接頭辞を1つ1つ調べるためのキーの離散的な表現．digital search treeやprefix treeとしても知られている．
形はキーの空間と長さにしか依存しない．
全ての操作は$k$をキーの長さとして，$O(k)$を持つ．
Inverted Indexes
単語から目的特性をにあるそれらの単語を持っているrecordへの写像を保持するindex
結論
B+ treeは未だにtree indexを取るための方法である．
感想
前回に比べて内容が薄いと思った．同じ木構造を使っても色々実装があるのだな．
