ハッシュデータベースとツリーデータベースの設計については一段落したので、次にスキップリストデータベースの設計に移る。まずはスキップリストの概要についてまとめてみよう。
唐突だが、英和辞書がファイルに書かれていることを想定してみよう。辞書の各項目がテキストの各行として並べられ、見出しに英単語、それに続いて空白と「--」、その後に英単語の説明文が来るという書式を想定する。
apple -- りんご applet -- 小さいアプリケーション banana -- バナナ camera -- 写真機 dance -- 踊る end -- 終わる finger -- 指 ...
見出し語は辞書順で並んでいるので、この構造に対しては二分探索ができそうだ。ファイルの真ん中付近までオフセットを進めて、適当な長さを読み込んで、次の改行の直後まで読み飛ばせば、次の見出し語が取得できる。それが検索語よりも順序的に後なら、今読んだ場所とファイルの先頭の中間あたりにオフセットを飛ばす。そうでなければファイルの末尾と今のオフセットの中間あたりにオフセットを飛ばすといった感じになろうか。実際に人間が英和辞書を使う時には似たようなことをやっている。
この方法は、使える文字を制限したテキストデータだからできることだ。見出しや本文に改行が含まれる場合には破綻する。任意のバイナリを扱いたい場合には、区切り文字を使うのではなく、長さとデータの組の連続として表現する。"\x05apple\x09りんご\x06applet\x0b小さいアプリケーション" といった感じのバイナリになる。レコードの先頭に長さが記録されているので、その分だけ読み飛ばせば次のレコードの位置に進んでそれを読むことができるという構造だ。これはすなわち単方向連結リストである。連結リストに対してはシーケンシャルアクセスはできるがランダムアクセスはできない。ゆえに二分探索もできない。
スキップリストとは、連結リストに対してランダムアクセスができるようにするためのデータ構造である。各レコードの先頭に次のレコードに進むための位置情報だけではなく、はるか遠くのレコードにスキップするための位置情報も付与しておくのだ。1個目のレコードには、1個先、2個先、4個先、8個先、16個先、32個先といった感じで行先候補のオフセットが書かれている。飛んだ先にも同様にスキップ情報が書かれていれば、ファイル内のどの位置にも比較的に短い時間で到達できる。どのレコードも確実に次のレコードの位置だけは教えてくれるので、所望の場所の近くまで来たら1個先だけを選択していけば、確実に所望の位置に到達できる。二分探索するには、行先候補のキーを見て、検索条件以上である場合にだけ実際にその行先に飛べばよい。なお、スキップリスト自体は単に連結リストのランダムアクセスを可能にするデータ構造であり、ソート済みでないレコード群に対しても付与できる。二分探索をするには全てのレコードがソート済みであるのが条件になる。
今回実装する「スキップデータベース」は、キーの辞書順に並べたkey-valueのバイナリレコードのシーケンスを連結リストとみなしてスキップリストを付与して、それを使って二分探索による検索を可能にしたものである。以下の図を見ると想像しやすいだろう。
各レコードには、そのインデックスに応じてレベルが決められる。0なら最大レベル、1はレベル0、2はレベル1、3はレベル0、4はレベル2、8はレベル3、16はレベル4だ。一般化すると、インデックスの因数に含まれる2の個数がレベルになる。そして、レベルに応じた数だけ直後のレコード以外のスキップ先を持つことになる。レベル1の行先は2つ先、レベル2の行先は2つ先と4つ先、レベル3の行先は2つ先と3つ先と4つ先といった具合だ。一般化すると、レベルLのレコードは行先として2^1から2^Lまでを持つ。こうすると、ファイル内のどのレコードにも対数時間以内に確実に到達できる。ここでは2を基準に考えたが、この数をステップユニットと呼ぼう。ステップユニットは2以上の整数なら3でも4でも100でも良い。デフォルトは4だ。その場合、4未満を無視した因数に4が含まれる個数がレベルになり、レベルごとの行先は4^Lになる。
ステップユニットを小さくし過ぎてもスキップリストの分のデータが肥大化するだけで性能が上がらないことが知られていて、逆に大きすぎると検索性能が悪化するので、4から16ぐらいがちょうどいいっぽい。また、最大レベルもチューニングすることができ、そのデフォルトは14だ。つまり最大で4^14 = 268,435,456個のレコードがスキップできる。レコード数がそれより多い場合には、最大レベルを増やした方が性能が良くなる。最大レベルが必要よりも大きいと空間効率が悪化するが、ほとんど気にしなくてもいい程度だ。
スキップデータベースのもう一つの特長は、順位で検索できることだ。ソート済みなので、インデックスが順位そのものであり、インデックスを基準にランダムアクセスをすれば該当のレコードに到達できる。全てのレコードの中で中央値を取り出すことも、最大値を取り出すことも、1274番目を取り出すことも、O(log N) でできる。
ちなみに、上記の構造は空間効率が最適ではない。飛び先のレベルは全体的に1つずつ下げて以下の図のようにしても同じ性能を達成できる。でも、実装がいろいろと面倒になるので今回はそうしなかった。
さらに余談だが、更新されうる連結リストに対してスキップリストを付与する場合、乱択アルゴリズムを使う場合が多い。レベルを乱数で決めるのだ。インデックスでレベルを決める方法だと、レベルの高い重要なノードが消されてしまうと性能がガタ落ちしてしまう。そもそも挿入や削除が発生した時点でインデックスという概念は破綻するけども。今回はリストの更新がされないし、インデックスでレベルを決めれば絶対安定の性能が実現できるので、乱択にする必要はない。
さて、このスキップデータベースをDBMのインターフェイスで実現したいのだが、一つ問題がある。ソート済みのレコードを入力してくれないと、二分探索ができるデータベースにならないのだ。「Setに渡すレコードはキーでソートした順番でよろしく」と仕様に書くのも手だが、あまり使い勝手が良いとは言えない。そこで、任意の順番でレコードをSetできるようにしつて、データベース内部でソートを行なうようにしよう。ユーザは、適当な順序でSetを読んで任意の数のレコードを登録してから、Synchronizeメソッドを呼ぶ。そうすると、中でソートが勝手に行われた上で、スキップリストデータベースが構築される。その後は、Getで完全一致検索でレコードの値を取得したり、イテレータを任意の位置に飛ばして範囲検索をしたりできる。
Synchronizeで実行されるソートは、外部ファイルを使ったマージソートで行う。それによって、メモリよりも大きい規模のデータベースが構築できる。既存のレコードがある状態でもSetをした後にSynchronizeが呼ばれた場合、既存のスキップデータベースはマージソート対象のデータソースの一つとして登録される。その結果、従来のデータと新しいデータがマージされた結果を得ることができる。
さらに、スキップデータベースでは、重複キーを許すことにする。Synchronizeでマージを行う際には、同じキーのレコードの値を集めた上で、リデューサと呼ばれる関数にそれを渡す。リデューサが実際に登録するレコードの値を生成するのだが、渡された値を全て出力しても良いし、最初や最後の値を選んでも良いし、何らかの集計操作を行なってもよい。これはまさにMapReduceの処理そのものである。つまりスキップデータベースはMapReduceのフレームワークとみなすこともできる。なにそれカッコいい。
ツリーデータベースに比べると、スキップデータベースはオンライン処理ができないという欠点がある。上述のように、一連のレコード投入を行なってからSynchronizeをしてはじめて、投入したレコードが検索できるようになる。いわゆるバッチ更新しかできないということだ。その一方、メモリに載らない大規模のデータベースも構築できるし、作られたデータベースの空間効率が非常に良いし、利用する際のメモリ使用量がほとんどないという利点もある。辞書検索とか統計処理とかにはスキップデータベースが向いているだろう。
