Cdb_(software)
その他の使用法については、CDBを参照してください
「Cdb」ソフトウェア
「定数データベース」の略であるcdbは、Daniel J.Bernsteinによって作成されたライブラリとデータ形式の両方を指します。cdbは、ディスク上の連想配列として機能し、キーを値にマッピングし、単一のキーに対して複数の値を格納できるようにします。定数データベースでは、作成と読み取りの2つの操作のみが可能です。どちらの操作も、非常に高速で信頼性が高いように設計されています。以来、データベースは、それが使用中に変化しない、複数のプロセスがロックせずに単一のデータベースにアクセスすることができます。さらに、すべての変更により置換データベースが作成されるため、UNIXファイルシステムのセマンティクスを利用して信頼性を保証できます。
レコード位置、キーと値の長さ、およびハッシュ値は32ビットの量であるため、4ギガバイトに収まる必要が cdbは、djbdns、fastforward、mess822、qmail、およびucspi-tcpによって使用され、非常に効率的で信頼性が高く、単純なデータアクセスを提供します。
コンテンツ
1 構造
2 フォーマット
3 としょうかん
4 参考文献
5 外部リンク
構造
データベースには、単一のコンピューターファイルにデータセット全体（たとえば、単一の連想配列）が含まれています。これは、固定サイズのヘッダー、データ、およびハッシュテーブルのセットの3つの部分で構成されています。ルックアップは正確なキーのみを対象に設計されていますが、データベース全体をスキャンすることで他のタイプの検索を実行できます。ルックアップは、次のアルゴリズムを使用して実行されます。
キーをハッシュします。
このレコードを配置するハッシュテーブルとスロットを決定します。
ハッシュテーブルで示されたスロットをテストします。
スロットが空の場合、レコードは存在しません。検索を中止します。
スロットのハッシュがキーのハッシュと一致する場合は、レコードを探します。キーを読んで比較します。一致する場合はデータが見つかったので、検索を終了します。
レコードはこのスロットにありません。次のスロットに進み、必要に応じてハッシュテーブルの先頭に折り返します。
複数の値を持つキーのルックアップの場合、次のスロットで検索を再開するだけで、追加の値が見つかる場合が
フォーマット
すべての数値（オフセット、長さ、およびハッシュ値）は、符号なし32ビット 整数であり、リトルエンディアン形式で格納されます。キーとデータは不透明なバイト文字列と見なされ、特別な処理は行われません。
データベースの先頭にある固定サイズのヘッダーは、ファイル内の位置とスロット内の長さをリストすることにより、256個のハッシュテーブルを記述します。データは一連のレコードとして保存され、各レコードにはキーの長さ、データの長さ、キー、およびデータが保存されます。配置や並べ替えのルールはありません。レコードの後には、さまざまな長さの256個のハッシュテーブルのセットが続きます。ゼロは有効な長さであるため、データベースに物理的に格納されているハッシュテーブルは256未満である可能性がありますが、それでも256テーブルと見なされます。ハッシュテーブルには一連のスロットが含まれ、各スロットにはハッシュ値とレコードオフセットが含まれます。「空のスロット」のオフセットはゼロです。
ハッシュは符号なし32ビット整数で、値5381から始まります。キーの各バイトについて、現在のハッシュに33が掛けられ、キーの現在のバイトとXORされます。オーバーフロービットは破棄されます。スロットとテーブルは、ハッシュから簡単に計算されます。ターゲットテーブルは、ハッシュの下位8ビット（つまり、256を法とするハッシュ）であり、テーブル内のスロットは、テーブルの長さを法とするハッシュ（つまり、256を法とするテーブルの長さで割ったハッシュ）の残りのビットです。
としょうかん
公式のcdbライブラリコードはパブリックドメインです。個々のソースファイルはそのようにマークされており、パブリックドメインのdjbdnsパッケージでも入手できます。ただし、cdbパッケージの残りの部分は、ライセンスフリーのソフトウェアでした。つまり、逐語的に配布する必要が珍しいライセンスとフォーマットの単純さにより、他の人はライブラリを再実装し、パブリックドメインで利用可能なMichaelTokarevのTinyCDBライブラリなどのより一般的な条件でリリースするようになりました。
2009年には、すべてのcdbがパブリックドメインになりました。
特に、cdbの作成者は、cdbを共有ライブラリとして使用することを意図しこれは、Berkeley DBなど、事実上すべての類似したdbmのようなデータベースとは異なります。
参考文献
^ CDB仕様
^ 「TinyCDB-定数データベース」。www.corpit.ru 。
^ 「ディストリビューターからのよくある質問」。
外部リンク
cdb公式cdbWebサイト
定数データベース（cdb）内部の詳細な形式の説明
cdbを類似のパッケージと比較するQDBMベンチマーク