ソート済みのレコードの連結リストにスキップリストを付与したものがスキップデータベースである。その具体的な書式についてここで完全に定義する。
スキップデータベースは、二つのセクションからなる。メタデータセクションとレコードセクションである。
メタデータセクションは、ファイルの先頭128バイトを締める。以下のフィールドを含む。
- マジックデータ。
- オフセット0から10バイトの文字列。"TkrzwSDB\n" とそれに続くヌル文字からなる。
- パッケージのメジャーバージョン
- オフセット10から1バイトの整数
- パッケージのマイナーバージョン
- オフセット11から1バイトの整数
- オフセット幅
- オフセット12から1バイトの整数
- ステップユニット
- オフセット13から1バイトの整数
- 最大レベル
- オフセット14から1バイトの整数
- クロージャフラグ
- オフセット15から1バイトの整数
- レコード数
- オフセット24から8バイトのビッグエンディアン整数
- 実効データサイズ
- オフセット32から8バイトのビッグエンディアン整数
- ファイルサイズ
- オフセット40から8バイトのビッグエンディアン整数
- 最終更新時刻
- オフセット48から8バイトのビッグエンディアン整数
- データベースタイプ
- オフセット56から4バイトのビッグエンディアン整数
- オペイクデータ
- オフセット64から64バイトの任意の文字列。
オフセット幅の説明は以前にもしたが、レコードのアドレスを何バイト使って表すかを示す。デフォルトは4なので、4GBまでのファイルが作れる。5にすると1TBまで、6にすると256TBまで、7や8にする奴は居ないと思うが、それぞれさらに256倍ずつで最大サイズを増やせる。その分、スキップリストの個々の要素のサイズが増えるので、空間効率は悪化する。
クロージャフラグは、データベースがきちんと閉じられていれば1、そうでなければ0を示す。スキップデータベースはテンポラリファイルで構築してrenameで元ファイルと置き換えるので更新でデータが壊れるということはあり得ないのだが、更新操作が途中で死んだというこが検出できるようにしておくことは重要だろう。最終更新時刻は、最後に更新が成功した時刻を記録している。これもデバッグや障害対応に使うことがあるかもしれない。
データベースタイプとオペイクデータは特に使い道がないのだが、ユーザが自由に設定できるメタデータとして活用いただきたい。
レコードセクションはオフセット128からファイルの最後までを締める。レコードセクションはキーの昇順にソートされた複数のレコードのシーケンスからなる。各レコードは以下の書式で記録される。
- マジックデータ
- 1バイトの整数
- スキップリスト
- キーのサイズ
- 可変長整数
- 値のサイズ
- 可変長整数
- キーのデータ
- 任意の文字列
- 値のデータ
- 任意の文字列
マジックデータは0xFFで固定である。本来は不要だが、データの破壊時に高い確率でそれを検出できるので、保険としてつけておく。可変長整数については今まで何度か述べたが、MSBの1ビットを次のバイトを読むかどうかのフラグとして、残り7ビットで整数値を表す書式である。多くの場合で短いが最長サイズに制限を設けたくないという場合に有用だ。
さて、デフォルトの設定での個々のレコードのフットプリントについて語っておこう。そういえば、フットプリントという用語についてちゃんと説明しなかった。直訳すれば足跡という意味だが、データコンテナの文脈では、レコードの実効データ（key-value構造の場合はキーと値のサイズの合計）以外に確保される領域の合計のことを示す。実効データは（圧縮でもしない限りは）削れないが、フットプリントは最小化するのが設計者の目標の一つになる。話を戻すが、スキップリストのフットプリントは、チューニングパラメータに大きく左右される可変部分と、それ以外の固定でかかる部分に分けられる。固定でかかるのは、マジックデータの1バイト、キーのサイズの1バイト（キーが127バイト以下の場合）、値のサイズの1バイト（値が127バイト以下の場合）の合計で、3バイトである。つまり、スキップリストを除いたフットプリントは極少と言っていい。
チューニングに左右される部分について検討する。スキップリストの要素はインデックスで決まるレベルと同じ数になる。インデックスが0である最初のレコードは例外的に最大レベルの要素数を持つが、それ以外のレコードは、ユニット数で割り切れる場合にはレベルが1で、ユニット数の2乗で割り切れる場合はレベルが2で、ユニット数の3乗で割り切れる場合はレベル3でといった具合になる。つまり、レコード数をNとすると、スキップリストの要素数の合計は、N/4^1 + N/4^2 + N/4^3 + N/4^4 + N/4^5 ... ということになる。平均をとると全体をNで割るから、Σ(k=1,N) 1/4^k って式になるのかな。いくつに収束するのか知らんけど、1/4よりほんのちょいでかいくらいであることは分かる。で、スキップリストの各要素は4バイトなので、平均すると各レコードは1バイトちょっとのフットプリントをスキップリストのために使う。それを固定フットプリントの3と足すので、各レコードのフットプリントは4バイトとちょっとということになる。ハッシュデータベースのバケットを除いた最小フットプリントである9バイトと比べてもかなり小さいことが分かる。最適化したツリーデータベースのフットプリントは3バイトを切るのでそれには負けるが、一般的な状況ではスキップデータベースの空間効率は最高の部類だろう。
