Hash-Based Indexing - Database Management Systems

study db database

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 は自分では思いつかないだろう。

リンク

一人読書会 - Database Management System


Database Management Systems