Berkely NDBMの仕組み

NDBM と SDBM の仕組み 平 成 17 年 6 月 24 日 有限会社ピーチツリー 幸山 １．はじめに NDBM と SDBM の DB ライブラリのソースコードを概説する。 SDBM は、 Ozan Yigit 氏により NDBM の改良版として作成された。作成される DB ファイルは、ディレクトリファイル(xxxx.dir)とリ ーフページファイル(xxxx.pag)がある。 リーフページファイルにキーとその値のデータが格納さ れている。ディレクトリファイルには、ビット列のデータが格納される。後述するが、このビッ ト列は、 ビットパターンのツリーを概念的に表し、 つリーフページのブロック番号も示してい か る。 実装は、トリッキーかつシンプルである。トリッキーと感じるのは、ディレクトリファイ ルに格納されるビット列のデータに、 くつもの意味と役割を持たせているためである。