CDBソフトウェアとは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > ソフトウェア > CDBソフトウェアの意味・解説 

cdb

(CDBソフトウェア から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/03 06:14 UTC 版)

ナビゲーションに移動 検索に移動
cdb
開発元 ダニエル・バーンスタイン
最新版
0.75 / 2000年2月19日
プラットフォーム クロスプラットフォーム
種別 ライブラリ
ライセンス パブリックドメイン
公式サイト http://cr.yp.to/cdb.html
テンプレートを表示

cdb: constant database)は ダニエル・バーンスタインによって開発された、単純なデータベースの作成と高速な問い合わせのためソフトウェアであり、cdbで扱うことのできるファイル形式の名称でもある。cdbは、4GBまでのハッシュ化データベースを扱うことができる。データベースはテキストファイルから簡単に作成することができる。

cdb はデータベースをいったん作成したら、そのあとで内容を更新(データの追加・削除・変更)することはできない。更新が必要なときはデータベース全体を作り直すことになる。一方で、更新の機能を持つ一般のデータベースと比較して、cdbでの問い合わせやデータベースの作成は非常に高速である[1]

cdb は、ダニエル・バーンスタインの開発したソフトウェアである、qmaildjbdns、ucspi-tcp などで使用されているほか、dbskkd-cdb[2]Postfix [3]などのソフトでも採用されている。

さらに高速で機能追加がなされたcdb互換ライブラリであるTinyCDBがリリースされている [4]

ファイル構造

cdbは内容を更新する機能を持たないため、データベースファイルは比較的単純な構造をしている。この単純な構造によって、高速なルックアップを実現している。

構造

cdbデータベースはデータセット全体を単一のファイルに格納する。このファイルは先頭から順に「固定長ヘッダ」「データ」「256個のハッシュテーブル」の3部で構成される。cdbは、キーの完全一致によるルックアップのみが行える設計になっており、他の方法でデータを検索したい場合にはデータベース全体をスキャンする必要がある。

ルックアップは以下のアルゴリズムにより行われる:

  • キーをハッシュする。
  • 対応するハッシュテーブルと、そのハッシュテーブル中のどのスロットから検索を開始するかを決定する。
  • ハッシュテーブルのスロットを順番にテストする。
    • スロットが空の場合: キーは存在しない。検索を終了する。
    • スロットのハッシュとキーのハッシュが一致した場合: 対応するレコードを読み、キーが一致するかどうかを確認する。一致すれば、データが見つかったことになり、検索を終了する。
    • 次のスロットへ進む。ハッシュテーブルの末尾に到達した場合は先頭に戻る。

同じキーで複数のデータが登録されている場合は、空のスロットに出会うまで検索を続けることで全てのデータを取り出すことができる。

形式

全ての数値 — オフセット、長さ、ハッシュ値 — は、符号無し32ビット整数であり、リトルエンディアンで格納される。キーと値は単なるバイト列として扱われる。

データベースの先頭にある固定長ヘッダは、256個のハッシュテーブルそれぞれの、ファイル中のオフセットとスロット数を並べたものである。ヘッダの次は、データがレコードの列として格納される。各レコードは、キーの長さ・値の長さ・キー・値で構成される。アライメントや並び順に規則は無い。その次には、可変長のハッシュテーブルが256個並ぶ。各ハッシュテーブルはスロットの列からなり、スロットはハッシュ値とレコードのファイル中のオフセットで構成される。「空のスロット」はオフセットが0のスロットとして表現される。

ハッシュ値は符号無し32ビット整数である。このハッシュ値は、5381から開始して、キーの各バイトについて、現在のハッシュ値を33倍した値と現在のバイトのXORを取っていくことにより求める。オーバーフローは破棄される。256個あるうちのどのハッシュテーブルに格納するかはハッシュ値の下位8ビットによって選択され、ハッシュテーブルのどこにスロットを置くかは、残りの上位24ビットをハッシュテーブルのエントリ数で割った値をもとに決定される。

脚注

関連項目

外部リンク





CDBソフトウェアと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

CDBソフトウェアのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



CDBソフトウェアのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのcdb (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS