原氏が次世代のコアだというインデックスファブリックについて

ちょっと調べてみた。次世代のデータベーステクノロジのコアになるだろうと原氏が「富国論」の中で指摘しているインデックスファブリックは、VLDBカンファレンスで2001年に発表されたというので検索したら、この論文がすぐに見つかった。

この中で説明されているのがどういうものかというと、従来のようにリレーショナルデータベースで明確に構造を定義してデータを放り込むのではなく、構造なんか定義しないで、構造もデータと一緒に文字列で格納してしまおう、というもの。言ってみれば、構造、データ、インデックスが渾然一体となっているので、構造は柔軟に変わっていけるし、その上超高速アクセスが可能ですというのだ。さらにこの発想がすごいのは、特定のデータベーステクノロジを前提にしていないので、フラットファイルやリレーショナル、オブジェクト、XMLデータベースなんでもござれというのだ。

こんなことを可能にしちゃうのが、このインデックスファブリック(写真)だという。これは、Patricia Trieというデータ構造をベースにしているが、本来メモリ内で保持されるものなため、それをディスクアクセスにも適した構造にしたのがインデックスファブリックというものだそうだ。データ構造に詳しい人は、論文を参照して欲しいが、ざっと説明すると、2次元のツリー構造になっていて、垂直に順にたどれるだけでなく、任意の水平レベルにもアクセスできるようになっているのだ。

これがどういうことかというと、言ってみれば、”請求書・得意先・名称・山田鉄鋼”のような構造＆データに最短経路でアクセスできるという。そもそもツリー構造は上からたどるものだが、水平なショートカットがたくさんあるようにイメージされてもいいだろう。

この構造だと、ツリー自体はバランスが取れていないのだが、水平なツリーと組み合わせることで仮想的にバランスが取れている。B-Treeを作った人は分かると思うが、こちらの方が更新コストもかなり低くできるだろう。

そしてさらに、このアイデアが今すぐに使えるすごい点は、ディスクアクセスの最小単位となるブロックに合わせて、関連ノードを一緒に放り込むことで、探索が必要なノードを一回のIOでまとめて取れますよということだ（IOがいかに今日課題かは私のコラムを参照）。ちなみにリレーショナルデータベースでは、通常、1行を1ブロックに格納しようとします。

より複雑なクエリを処理するプロセッサについては今後の課題だが、どんな複雑なものも単純なものの組み合わせなので、大丈夫だろうということだ。

確かに、結構いいとこだらけの面白そうな技術だ。ただ、いまいちピンと来ない部分がある。基本的に文字列を対象にしているのはまあいいとして、ツリーというのは本質的にいくつもの制約がある。人間関係、道路、通信ネットワーク、そういったグラフ構造は表現できないのだ。そして何よりも、人の脳のニューロンネットワークはグラフ構造だ。ツリーはハードディスクと相性がいい。グラフ構造は、むしろメモリ（フラッシュメモリ）などの次世代ディスクと相性がいい。そういう意味で、なんとなく、次世代？と首をかしげている・・・。