BTREEとHASHの違い【インデックス】

インデックスの

• BTREE
• HASH

の違いについて調べたことざっくりメモ。

分かりやすいように例で説明する。

BTREEなら以下のようにする。

1. 事前に以下のようなツリーを作る
   
2. 上から順番に16が
   • 9より小さいか？
   • 9より大きくて18より小さいか？
   • 18より大きいか？
     のどれに当てはまるか見ていく。それが終わったら次の階層で
     • 12より小さいか？
     • 12より大きくて15より小さいか？
     • 15より大きいか？
       のどれに当てはまるか見ていく。

･･･みたいなやり方をするのがBTREE。

HASHなら以下のようにする。

1. 事前に箱の中身の数字をハッシュ化して、箱の外側にハッシュ化した数値を書いておく
   • 「ハッシュ化する」と書くとややこしいので、箱の中身の数字を2倍した数字を書いておくということにする
   • なので16の箱には32と書いておく
2. 16を探す場合は、まず16を2倍する。
3. すると答えは32なので32と書いてある箱を探す。（外に番号が書いてあるのですぐに探せる。）

このようにHASHだと「どれと一致するか」しか探せないので、一致検索しかできない。

まとめ

おわり

参考にしたページ：

http://www.intellilink.co.jp/article/column/oss-postgres02.html