空間インデックスの前に一次元データ用のインデックス

TECH

前回は一次元と二次元の違いについて書いたので、今回は一次元のデータのためのメジャーなインデックス作成方式（データ構造）について書いてみたいと思う。

商用やフリーのデータベース管理システムで、一次元のデータに対してインデクスを作成するときは、B-Tree （及びその改良版）や、ハッシュテーブルをが使われることが多い。

インデックスを作成する目的と課題

インデックスを作る目的は、高速にデータの検索をできるようにすることだ。しかし、検索が速くできれば何でもいいというわけではない。検索は高速だけど、インデックスを作るときにものすごく時間がかかると、データを頻繁に追加するようなデータベースでは困る。また、検索は高速だけどメモリを大量に消費するというのも、メモリが少ないコンピュータでデータベースを動かすときには困る。

そのため、一般のコンピュータで使われるデータベースでは、検索を高速化することを主としながらも、「データの追加や削除もそこそこ高速にできる」ことや「メモリの消費量が少ない」ことも同時に求められる。闇雲に、検索だけ高速になればいいというものではない。

ただし、一般ではなくプロ仕様のデータベースでは、Google のように検索の速度に特化してチューンすることもある。そのあたりは用途に応じて最も特化されたインデックスの作成方式が使われる。ここでは、一般的なデータベースにおけるインデックスの作成方式についてのみ述べる。

B-Tree (B木)

B-Tree は検索や追加、削除の高速性とメモリ使用量のバランスがほどよく、またハードディスクのような二次記憶装置の特性と相性がいいという理由から、実際のデータベース（厳密にはデータベース管理システム: DBMS）で、インデックスを作成するために使われている。B-Tree は「二分木 (Binary Tree)」、さらにそれを発展させた「AVL木」というデータ構造がベースになっている。

二分木、AVL木についての説明は、下記に分かりやすいのがあるみたいなのでここではパス。木構造→二分木→AVL木の順で読めばなんとか分かるやも。

ちなみに、B-Tree 自体はインデックスではなく「データ構造」を表す言葉。B-Tree を使ってデータに対するインデックスを作る、という言い方が正確ではある。どうしても B-Tree を使って作ったインデックスのことを意味したい場合は、B-Tree インデックスとか呼ぶこともある（あんまり聞かない）。あと、日本語ではB木という表記がされるけど、音読すると「びーき」となって語呂が悪いため、この世界の人が音読するときは「びーつりー」ということが多い。

ハッシュテーブル

メモリを犠牲にしても、処理速度を超高速にしたいという場合に使われるデータ構造がハッシュテーブル。理論的には、メモリを無限に使えるのであれば、データの追加、削除、検索の処理を常に「データひとつにアクセスするだけで」実現できてしまう。データベースに入っているデータの量に関係なく、常に一定の処理速度で検索できるというのはある意味すごい。

ただ、現実には前述のように「無限のメモリ」は用意できないから、どんなに「データを追加しても検索速度が一定」という状態は実現できない。使えるメモリ量が少なくなると、それに応じて処理速度が下がる。それでも、メモリを潤沢に使えるのであれば、ハッシュテーブルは「データの追加・削除・検索」を非常に高速に実行できる。

ハッシュテーブルも超メジャーなデータ構造だから、あちこちに説明があるよね。ってことで、こいつもここでは説明はパス。