ハッシュインデックスとは

Question

ハッシュインデックスとは、何なのでしょうか。
ここによると
ハッシュインデックスは、btreeのようにDBのインデックス(索引みたいなやつ)の種類の一つであり、与えられた数値を一定の規則に従って別の値に変換するハッシュを用いてキー(primary key？unique key?)をハッシュ化する。どのあたりが似ているのか分からないが、ハッシュテーブウ(配列っぽいやつ)に似ているという。

ハッシュインデックスとは、何なのでしょうか。

• b-treeに関する理解

ハッシュインデックスについて上記のように図にして説明していただけると有難いです。

Answer 1

ハッシュテーブルとインデックスについては知っている前提でいいのですか？
簡潔に言うとハッシュテーブルを使ったインデックスです。
その特性はこちらを見るとわかりやすいと思います。
8.3.8 B ツリーインデックスとハッシュインデックスの比較

###追記
B 木はデータ構造の名前なので図示できます。ハッシュインデックスはインデックスの実装の名前なのでメーカーによって違います。

Answer 2

ハッシュについては暗号化によく用いられる技術です。
ハッシュ関数（幾つかアルゴリズムがある）により得られたハッシュ値は、元のデータより小さなものになります。
※ハッシュ値は必ずしもユニークにはなりませんが、ユニークにならない頻度は極めて小さいものです。

このハッシュ値によるインデックスがハッシュインデックスです。
検索する対象データが小さくなるのとカーディナリティが高くなることにより、高速検索になります。

但し、ハッシュ値での並び替えは意味をなさないので、用途に応じて通常のインデックスとの使い分けが必要です。
特定が目的ならハッシュインデックス、候補が目的なら通常のインデックスと考えて差し支えないかと思います。

Comments

[aaaaaaaa]

ご回答ありがとうございます。

カーディナリティというのは、カラムの値の種類(種類というのは、値がYES、NOや男、女の何れかだったり{この場合は、カーディナリティは2}、1年間の日付なら1日から365日なのでカーディナリティは365)とレコードの数の比率で、レコードの数よりカラムの値の種類が多い時は、「カーディナリティが高く」、レコードの数よりカラムの値の種類が少ない時が「カーディナリティが低い」ということであっておりますか。

またbtreeに関する理解は、ネットや書籍などの情報のおかげで追記した質問文にあるような、簡単な理解(合っているのかはわかりませんが)をしておるのですが、btreeに比べてハッシュインデックスがどのように動作するのかいまいち理解できないのです。
図にするとb-treeと違いどのような動作をするのでしょうか。

[sazi]

カーディナリティについての認識は合ってます。
btree:
https://qiita.com/kiyodori/items/f66a545a47dc59dd8839
ハッシュテーブル:
https://qiita.com/tenten1010/items/da4084f937ad07e70164
btreeは二分探索木に適した構造。ハッシュテーブルはユニークさを前提とした構造。

[aaaaaaaa]

ご回答ありがとうございます。ハッシュテーブルのほうのqiitaは、質問前に読んだことがありますが、
なかなかハッシュテーヴルの動作がつかめなかったので質問したのです。
btreeは、質問文にもあるような図で何となく理解できるのですが、ハッシュテーブルにも処理を図にしたようなものはないのでしょうか。

[sazi]

理解したいのは検索アルゴリズムですか？
ハッシュインデクスはハッシュ値が、所謂ポインターと同義で、ピンポイントでアクセスしますから、b-treeのようなアルゴリズムは存在しません。
単純だから、図解しようとも思わないので、そういったサイトが見つからないのだと思います。
お気に召すかは分かりませんが、一応参考に。
https://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/search/006.html