計算機科学におけるインデックス(index, 複数形 indexes, indices)は状況に応じて異なる意味合いを持つがインデックスに共通しているのは、ある一連のデータに対して順序関係を与えるための情報を持つことだ。そして順序関係を与えるために次の性質を持つことが要求されている。
- Equatable (同値判定可能)であること
- Comparable (比較可能)であること
- Hashable (ハッシュ計算)可能であること
Equatableであるというのは、== と != 演算ができるということだ。最初の特性としてインデックスは同じ値かどうかを確認できる。でなければ、索引である意味がないからだ。
さらにインデックスはComparableである。これは <, <=, >=, > によって判定できることを指す。基本的にComparableであればEquatableであるが、浮動小数点数のように反射律を満たさないものがあるので1、厳密にはComparableであってもEquatableでないものもある。Comparableであるとひとつ嬉しいことがある。それは比較可能なのでソートができるということだ。ソート済みのデータに対しては二分探索という で計算できる高速なアルゴリズムが適用できるので、非常に重要な性質となっている。
Hashableというのはインデックスの型 の同値性をハッシュ関数 というものを使ってビット単位で確認する以上に素早く判定できることを指す。これは偽陽性があってもいいが、結果はなるべく散らばることが好ましい。整数値であればそれ自身をそのまま採用してもいいし、文字列ならそれぞれの文字コードについて何らかの計算が必要かもしれない。複合データ型ならそのキーとなるデータのハッシュ値を採用することになるだろう。
Tip
概念的な話で難しいと感じるのであれば、インデックスは整数値であると考えてください。整数値はこれら3つを満たすもののひとつで、実際インデックスの値には整数値が用いられることが多いです。
プログラミングにおけるインデックス
多くのプログラミング言語が採用しているように、 がint (整数値)であるときのことを考えてみる。普段我々が使用している配列がこれに相当して、
a[0] = "Apple";
a[1] = "Lemon";
a[2] = "Grape";のような書き方ができ、"Lemon" よりも "Apple" のほうが先であることは見てわかるように、これら3つのデータに対しては順序関係が生まれている。 が整数値のためハッシュ値を求める関数は とできる(つまりそのまま使う)。
また、連想配列や辞書型(インデックスとして任意の型 を使用)と呼ばれるものについても、この特性が採用されていて、以下のコードにおいては
var dict = new Dictionary<string, int>();
dict["Apple"] = 100;
dict["Banana"] = 200;
dict["Avocado"] = 300;では、 が文字列である。文字列はComparableであり、さらにハッシュ関数 で string → int の変換ができるのでHashableでもある(C#であれば)。辞書型は 時間でデータを読み書きを実現するために内部的に木構造のバランスをとっているが、ここでキーがComparableかつHashableであるために高速にデータのやりとりが可能となっている。
データベースにおけるインデックス
データベース上のデータはひとつひとつのデータを見ればEquatableでComparableでHashableである。しかし、カラムの組み合わせとなると同値性をデータレベルで突き合わせなければならずコストのかかる作業となる。例えば、(TEXT, TEXT) の順序関係はどうなるだろうか？これを都度計算するのはコストがかかりそうだ。そこで、あらかじめ計算されたインデックスを割り当てておくことで高速に比較できるようになる。
もちろんインデックスを使わずとも高速に判定できるのであればそうするべきである。UUIDを比較するよりも整数値を比較するほうが速いのは当たり前だが、それに気づくのは決まってレコード数が数十万を超えてパフォーマンスを気にするようになってからなのである。
Footnotes
-
NaN != NaNである。RustではこれをPartialEqトレイトで回避している。 ↩