Database Management Systemsの11章。
Hash-Based Indexing
- 特徴
- search= が速い 1 I/O
- sarch range ができない
- 総合的には Tree-Based Indexing が上
- Static Hashing
- ISAM と同様の考え方で Hash-Based
- 1 〜 N - 1 の primary bucket pages にデータを入れていく。ページ内は sorted を維持する場合が多い
- ページからあふれたら over flow pages を追加していく
- primary bucket pages は初期化時にサイズが分かるので連続領域に取る事ができ有利
- 弱点
- 急激データ増加 : overflow pages でパフォーマンスが悪化
- 急激データ減少 : primary bucket pages がスカスカで容量が無駄に。（Rehashするとか）
- Extendible Hashing
- Static Hashing の弱点を取り除きたい
- bucket pages は directory で管理される
- hash(key) の下位 d bit が directory が保持する bucket への pointer を決定する
- bucket があふれたら d -> d + 1 とし directory のサイズを 2倍にする。
- ポインタのつけ替えなどをする（これは図がないと説明が大変難しい）
- 利点
- bucket があふれたときに動的に rehash に近い事を低コストでできる。
- Static Hashing と違い bucket の追加が可能。
所感
- Extendible Hashing は自分では思いつかないだろう。
