Cdb
cdbデータベースはデータセット全体を単一のファイルに格納する。このファイルは先頭から順に「固定長ヘッダ」「データ」「256個のハッシュテーブル」の3部で構成される。cdbは、キーの完全一致によるルックアップのみが行える設計になっており、他の方法でデータを検索したい場合にはデータベース全体をスキャンする必要がある。
ルックアップは以下のアルゴリズムにより行われる:
キーをハッシュする。
対応するハッシュテーブルと、そのハッシュテーブル中のどのスロットから検索を開始するかを決定する。
ハッシュテーブルのスロットを順番にテストする。 スロットが空の場合: キーは存在しない。検索を終了する。 スロットのハッシュとキーのハッシュが一致した場合: 対応するレコードを読み、キーが一致するかどうかを確認する。一致すれば、データが見つかったことになり、検索を終了する。 次のスロットへ進む。ハッシュテーブルの末尾に到達した場合は先頭に戻る。
同じキーで複数のデータが登録されている場合は、空のスロットに出会うまで検索を続けることで全てのデータを取り出すことができる。