Let's C#で数値計算: LightDB（軽量・高速な簡易データベース）

多くのデータベースシステム（DBMS）では検索を高速に実行するため、データ本体とは別に、別途インデックスを作成します。
一般にインデックスは B-Tree という特別な構造（平衡多分木）を持ったファイルになります（詳細は B-Tree 等で検索してください）。
LightDB は多くの DBMS が採用している B-Tree 構造を持ったインデックス操作を .Net クラスとして組み込んだものです。

DBMS のインデックスはキーフィールドの値と、そのキーを含むレコードへの位置情報を管理します。
LightDB ではキーフィールドとデータレコードを一体化して管理します（別途管理することもできます）。

プログラミング手順

[新規ファイルにキーとデータ（レコード）を追加]

     //
     // LightDB インスタンス作成:
     //    キー部分は int[] で配列サイズ 1 
     //    データ部分は double[] で配列サイズ 2 
     //
     LightDB<int, double> db = new LightDB<int, double>(1, 2);

     // データベースファイル "sample.ldb" を新規にオープン
     db.OpenNew("sample.ldb");

     // キーとデータをセットしてデータベースファイルに追加
     int    [] key  = new int   [1];
     double [] data = new double[2];
     while(....) 
     {
        // データベースに追加するキーとデータのセット
        key[0] = キー
        data[0] = データ１
        data[1] = データ２
        // キーとデータをデータベースファイルに追加する。
        db.AddRecord(key,data);
     }

     // ファイルのクローズ
     db.Close();

[既存ファイルからキーを指定してデータを検索]

     //
     // LightDB インスタンスの作成は、前例と同じ。
     //
     LightDB<int, double> db = new LightDB<int, double>(1, 2);

     // 既存データベースファイル "sample.ldb" をオープン
     db.Open("sample.ldb");

     // キーを指定して対応するデータを検索
     int    [] key  = new int   [1];
     double [] data = new double[2];
     while(....) 
     {
        // データベースから検索するキーのセット
        key[0] = キー
        // キー(key)を指定して対応するデータ(data)をデータベースファイルから読み込む。
        if(db.ReadRecord(key,data)==0)
        {
            // 読み込めた場合の処理
            データ１ = data[0];
            データ２ = data[1];
             ..............
        }
     }

     // ファイルのクローズ
     ldb.Close();

簡単例： BigMatrix と BigVector

	// メモリー上に作成できないような巨大行列を扱う例
        public class BigMatrix : LightDB<int, double>
        {
            public BigMatrix(string dbPath)
                : base(2, 1)
            {
                Open(dbPath);
            }
        };

	// BigVector は大抵の場合一次元配列で代用可能ですが、行列と同様に以下のように定義できます。
        public class BigVector : LightDB<int, double>
        {
            public BigVector(string dbPath)
                : base(1, 1)
            {
                Open(dbPath);
            }
        };

継承せずに、 LightDB A = new LightDB<int,double>(2,1); のように直接インスタンスを作成してもかまいません。 <int,double>(2,1) はキーフィールドが int でデータフィールドが double の配列で、サイズはそれぞれ 2 と 1 を意味します。 つまり、２個のキーフィールド [i,j] で１個の double 値 A[i,j] を検索する、連想記憶配列を作成することになります。 連想記憶配列を作成すれば、後は通常の行列やベクトルとまったく同じように使用可能です。 違いは配列サイズの制限が無いこと、[i,j] で検索できなかった場合は値 ０ が返ることなどです。

　※ 例はインデクサ（A[i,j]とあたかも配列のようにアクセスする方法）によるレコードアクセスですが、他にメソッドを使用したさまざまな機能が提供されています。
　※ データベースファイル名（と拡張子）は任意です。

        public void Test()
	{
            int n = 50000;

            BigMatrix  A = new BigMatrix("A.ldb"); // 行列、A[i,j] 形式でアクセスする連想配列データベース。
            double []  b = new double[n];
            double []  c = new double[n];

            // データのセット（書込み、値は計算時間に無関係なので適当…）
            DateTime tm = DateTime.Now;
            for(int i=0;i < n;++i)
            {
                b[i] = n - i;
                for (int j = 0; j < n; ++j)
                {
                    A[i, j] = i + j;  // 配列要素値は "A.ldb" に保存されます。
                }
            }
            Console.WriteLine("書き込み時間=" + (DateTime.Now-tm));
            // 掛け算の計算（読み込み）
            tm = DateTime.Now;
            for (int i = 0; i < n; ++i)
            {
                double s = 0;;
                for (int j = 0; j < n; ++j)
                {
                    s += A[i, j] * b[j];  // A[i,j] 要素は "A.ldb" から読み込まれます。
                }
                c[i] = s;
            }
            Console.WriteLine("読み込み時間=" + (DateTime.Now - tm));

            A.Verify(false);
            A.Close();
	}

書き込み時間=01:32:04.1101026
読み込み時間=01:17:06.7549277

LightDb データベースファイルの情報
 LightDB version    = 1
 全ページ数         = 31250004
 ページバイトサイズ = 1952
 先頭削除ページ     = 0
 ファイルサイズ     = 61000007808
 キータイプ         = 6[SINT]
 キーバイトサイズ   = 8
 データタイプ　     = 10[DOUBLE]
 データバイトサイズ = 8
 ルートページ       = 538089
 最大アイテム数     = 80

内部メモリー（キャッシュ）の検査

LightDB ファイル構造の検査
 有効レコード数  = 2500000000
 有効ページ数    = 31250003
 削除ページ数    = 0
 B-Tree の高さ   = 5
 レコード占有率  = 99.999990%

１レコードの平均読み込み時間は ((60+17)*60+6)/(50000*50000) => 1.8504e-6 秒ということになります。

書込み時間と読み込み時間が同程度になっていますが、 例えばn = 10000;程度で計測すると、書込み時間が約3分で読み込み時間は約2分弱となります。

上記テストは 32bit アプリケーションで実行しましたが、メモリー自体の負荷は少ないので 64bit アプリケーションで実行しても 結果に大きな違いは出てきません。

結果の「レコード占有率 = 99.999990%」とは、各ページが格納しているアイテム（レコード）がほぼ１００％であることを 意味します（後述の「LightDB ファイルの構造」を参照してください）。つまり、データベースに隙間が殆どないということです。

また「B-Tree の高さ = 5」は、キーの検索に必要なディスクアクセスが最大でも 5 回で済むことを意味します。

[BigMatrix使用例： 連立方程式の解法]