B+-Tree in Practice - Database Management Systems
Database Management Systemsの10章。
マインドマップから再構成したまとめ
Bulk loading
複数のデータから B+-Tree を 1 から構築するとき。
- 通常の insert アルゴリズムだと root から 1 データずつ insert。効率悪い
- ある程度まとめてデータを insert する方法が Bulk loading
- データを key でソートしてからまとめて insert していく
B+-Tree の prefix key compression が面白かった。商用のDBではほぼ実装されているらしい。
Prefix key compression
- B+-Tree は木の高さが低い方が良い
- I/Oが少なくなるから。
- 木の高さはデータ数と、1ページあたりのindex entry 数に比例
- つまり1ページに index entry をたくさん詰め込めば fanout が大きくなり高さが低くなる
- key が短ければたくさん詰め込める
- となり合う、key は search key との大小比較で使われるだけ。
- "David-san" と "Daniel-kun" の大小比較では "Dav" と "Dan" として格納しておいても OK。（おおまかに）
B+-Tree
Duplicate Handling
key に対して複数 record 存在する場合はどのように格納するのか？
方法1: ISAM のように overflow pages に格納
方法2: leaf page に他のデータと同じようにおく。
key->(data, rid) のような構造でデータを保持したい場合は key に rid も含めた形で unique index を保つ。（自信なし）
そうすれば delete 時に同じ key に対する (data, rid) の組の走査のコストがかからない。
所感
- B+-Tree に何故か興奮する
