コンスタント・データベースの構造
19960914
Copyright 1996
D. J. Bernstein, djb@pobox.com

cdb は連想配列です。文字列("keys")を文字列("data")に配置します。

cdb は開いているハッシュ・テーブルを直線的に調べるための 256 個のポイ
ンタを含みます。ハッシュ・テーブルは(キー,データ)の組合わせへのポイン
タを含みます。cdb はディスク上で一つのファイルに格納されます:

    +----------------+---------+-------+-------+-----+---------+
    | p0 p1 ... p255 | records | hash0 | hash1 | ... | hash255 |
    +----------------+---------+-------+-------+-----+---------+

256 個の初期ポインタはそれぞれ位置と長さを示します。位置はハッシュ
・テーブルの始まりのバイト位置です。長さはハッシュ・テーブルにおける
スロットの個数です。

レコードは特に並べ替えをせずに逐次的に格納されます。一つのレコードは
キーの長さとデータの長さとキーとデータを示します。

ハッシュ・テーブルのスロットはそれぞれハッシュ値とバイト位置を示しま
す。バイト位置が 0 であればそのスロットは空です。そうでなければ、
そのスロットはキーがそのハッシュ値を持っているレコードを示します。

位置、長さ、ハッシュ値は4バイトのリトル・エンディアン形式で格納され
ている32ビット値です。このようにして、cdb は4ギガバイトまで適応します。

レコードは以下のように置かれます。レコードにキーのハッシュ値を計算し
ます。ハッシュ値を 256 で割った余りはハッシュ・テーブルの数です。
ハッシュ値を256 で割った商をそのテーブルの長さで割った余りはスロット
数です。レコードを見つけるかあるいは空のスロットへ動かすかするまで、
そのスロット、その次の高いスロットなどを探索します。

cdb のハッシュ関数は 5381 のハッシュで始まる "h = ((h << 5) + h) ^ c"
です。