External Sorting - Database Management Systems
Database Management Systemsの13章。
マインドマップから再構成したまとめ
背景
- データ量 > メモリ
- メモリ上でソートできない
- I/O を最小にするアルゴリズムが必要
Two way merge sort
- 学習用の例。書き込みに 1 ページ、読み込み用に 2 ページの計 3 ページしかメモリを使わずに merge sort
- 欠点
- 4ページ以上メモリが潤沢に存在しても使われない
- コスト
- おおまかに 2N * log2N I/O
- データを subfile （run）にわけてソート。
External merge sort
- b ページ使えるとしてそれをフル活用
- コスト
- log(b-1)N
B+-Tree をソートに使う
- ソート key に B+-tree の index があればそれを使う。
- Clustered index だとかなり幸せ
所感
- two way merge sort が 2 ページしか入力に使わないという部分が理解できず悩んだ。（解決済み）
