ダブル配列 （ Double-Array ） とは， トライ （ Trie ） のデータ構造の一つで， 「小さい辞書で高速な検索」が特長になります． トライを表現したデータ構造ですから， 「入力文字列の前方部分列と一致するキーの検索」が可能です． 使い方としては，フィルタリングや構文解析，形態素解析などがあります．
ライブラリとしては，おそらく Darts が有名です．
Darts: Double-ARay Trie System
DynDA は，動的なダブル配列なので， キーを一つずつ追加，削除できるようになっています． また，更新によって発生した無駄な領域を除去する機能があります． 試験的に公開しているだけなので，レコードの格納には対応していません．
DynDA は GNU Lesser General Public License に従います．
dynda-001.tgz - 5,895 bytes
dynda-000.tgz - 5,874 bytes
MinGW gcc 3.4.2 で動作確認をしています．
dynda.h からの抜粋になりますが， 以下のような構造体を提供します．
// ダブル配列のハンドル typedef struct Dary *hDary;
// ダブル配列の状態
typedef struct Dstat
{
unsigned max; // 末尾の要素
unsigned mblk; // 使用中のブロック数
unsigned nblk; // ブロック数
unsigned mtail; // 配列 TAIL の使用中の長さ
unsigned ntail; // 配列 TAIL の長さ
unsigned size; // ダブル配列に割り当てられたバイト数
unsigned nemp; // 未使用要素の数
unsigned nkey; // 登録されているキーの数
} Dstat, *hDstat;
各ブロックは，256 個の要素で構成されます． また，BASE, CHECK には， それぞれ 4 bytes が割り当てられます．
dynda.h からの抜粋になりますが， 以下のような関数を提供します．
// 辞書の作成，もしくは読み込み int Dary_Open( hDary *h, const char *path );
// 辞書の破棄 int Dary_Close( hDary h );
// 辞書の保存 int Dary_Save( hDary h, const char *path );
辞書の作成と破棄，入出力のための関数です．
// 辞書情報の取得 int DADic_Status( hDADic h, hDAStat st );
辞書の情報を取得するための関数です．
// 検索 int Dary_Search( hDary h, const char *s );
// 追加 int Dary_Insert( hDary h, const char *s );
// 削除 int Dary_Delete( hDary h, const char *s );
キーを検索，追加，削除するための関数です．
// 配列 BC の整理 int Dary_AdjustBC( hDary h );
// 配列 TAIL の整理 int Dary_AdjustTail( hDary h );
配列 BC, TAIL から無駄な領域を除去するための関数です．
// エラーメッセージ void Dary_Error( int code );
エラーコードに対応する文字列を stderr に出力する関数です．
sample.c を参考にしてください．
余裕があれば，レコードの格納や Prefix Search などを実装しようと思っています．
青江順一． トライとその応用． 情報処理．pp. 244-251．1993．
森田和宏，泓田正雄，大野将樹，青江順一． ダブル配列における動的更新の効率化アルゴリズム． 情報処理学会論文誌．Vol. 42．No. 9．pp. 2229-2238．2001．
森田和宏，泓田正雄，大野将樹，青江順一． ダブル配列におけるキー削除の効率化手法． 情報処理学会論文誌．Vol. 44．No. 5．pp. 1311-1320．2003．
大野将樹，森田和宏，泓田正雄，青江順一． ダブル配列による自然言語辞書の高速更新法． 言語処理学会第 11 回年次大会．P5-5．2005．
矢田晋，森田和宏，大野将樹，泓田正雄，吉成友子，青江順一． 接頭辞ダブル配列における空間効率を低下させないキー削除法． 情報処理学会論文誌．Vol. 47．No. 6．pp. 1894-1902．2006．
矢田晋，森田和宏，泓田正雄，平石亘，青江順一． ダブル配列におけるキャッシュの効率化． FIT2006．pp. 71-72．2006．