国家開発銀行
シー‐ディー‐ビー【CDB】
読み方：しーでぃーびー
《Center for Developmental Biology》理化学研究所の一部門である多細胞システム形成研究センターの略称。
はっせいさいせいかがく‐そうごうセンター〔ハッセイサイセイクワガクソウガフ‐〕【発生・再生科学総合センター】
読み方：はっせいさいせいかがくそうごうせんたー
理化学研究所の一部門である多細胞システム形成研究センターの旧称。
CDB
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/09/09 15:40 UTC 版)
- cdb
- cdb - ダニエル・バーンスタイン の開発した定型データベースライブラリ。
 |
このページは曖昧さ回避のためのページです。一つの言葉や名前が二つ以上の意味や物に用いられている場合の水先案内のために、異なる用法を一覧にしてあります。お探しの用語に一番近い記事を選んで下さい。このページへリンクしているページを見つけたら、リンクを適切な項目に張り替えて下さい。 |
cdb
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/03 06:14 UTC 版)
ナビゲーションに移動 検索に移動| 開発元 | ダニエル・バーンスタイン |
|---|---|
| 最新版 |
0.75
/ 2000年2月19日 |
| プラットフォーム | クロスプラットフォーム |
| 種別 | ライブラリ |
| ライセンス | パブリックドメイン |
| 公式サイト | http://cr.yp.to/cdb.html |
cdb（英: constant database）は ダニエル・バーンスタインによって開発された、単純なデータベースの作成と高速な問い合わせのためソフトウェアであり、cdbで扱うことのできるファイル形式の名称でもある。cdbは、4GBまでのハッシュ化データベースを扱うことができる。データベースはテキストファイルから簡単に作成することができる。
cdb はデータベースをいったん作成したら、そのあとで内容を更新（データの追加・削除・変更）することはできない。更新が必要なときはデータベース全体を作り直すことになる。一方で、更新の機能を持つ一般のデータベースと比較して、cdbでの問い合わせやデータベースの作成は非常に高速である[1]。
cdb は、ダニエル・バーンスタインの開発したソフトウェアである、qmail、djbdns、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ビットをハッシュテーブルのエントリ数で割った値をもとに決定される。
脚注
- ^ “Benchmark Test of DBM Brothers (PDF)”. 2009年5月30日閲覧。
- ^ dbskkd-cdb Google-code
- ^ Postfix CDB Howto
- ^ TinyCDB
関連項目
外部リンク
固有名詞の分類
- Cdbのページへのリンク
