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

インデックスの

  • BTREE
  • HASH

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

 

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

  • 例えば1~20までの数字が入った箱が20個あるとする。
  • 箱の中身は開けてみるまで分からない。
  • そんなとき、16が入った箱を当てるにはどうすればいいか?なるべく時間をかけずに。

 

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だと「どれと一致するか」しか探せないので、一致検索しかできない。

まとめ

 
違い BTREE HASH
検索のスピードは? ツリー状にデータを検索していく
→データによって時間に差がある
どんなデータでも「これだ!」と一発で探せる
=一定時間で探せる
一致 (=)検索ができるか?
大小比較 (<, <=, >, >=)検索ができるか? ×
不一致 (!=, <>)検索ができるか? ×

 

おわり

 

参考にしたページ:

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

SQL
スポンサーリンク
この記事を書いた人
penpen

1991生まれ。WEBエンジニア。

技術スタック:TypeScript/Next.js/Express/Docker/AWS

フォローする
フォローする

コメント

タイトルとURLをコピーしました