1994年−1995年
1994年10月、約1年掛けて試作版ができあがりました。
これはVBで書かれたもので、性能的に実用に耐えるものではありませんでしたが、それでも、DBエンジンが備えるべき機能とそのアルゴリズムを検証するには十分でした。
当時のOSは確かWindows3.1だったかと思いますが、この上で動くアプリケーションを開発するのに言語はVBを選択しました。開発予定の画面数が数百画面を想定しており（実際には1200画面以上になりました）工数削減を考えてのことです。（この選択で、あとからずいぶん泣かされることになりましたが）
このアプリケーションに組み込んで更に1年掛けてテストを繰り返しました。
1995年8月頃だったと思います。アプリケーションの開発も進み、いよいよ大量データによる本格的なテストを始めた矢先、とんでもないことが起きてしまいました。
同一キー値のサーチ問題
いわゆる同一キー値のサーチ問題と言われるもので、テスト中に突然アプリケーションがダンマリになってしまい、原因を調べるとDBエンジンがループしているように見えるのです。何分かすると回復するのですが、これでは使い物になりません。
私たちのDBエンジンは、木構造と言われるインデックスを採用しています。このインデックスは、インデックスブロック（IB）という単位で階層構造になっていて、IBにはキー値と下位のIB番号が昇順に格納されています。一番下位のIBに実際のデータのレコード番号を持つという構造です。IBの階層も、数千万レコードのデータベースでもせいぜい10階層もあれば管理できるシンプルな構造になっています。
通常のサーチの場合、目的とするキー値を指定することにより、IBを検索することで同じキー値を持つ目的のレコードを高速に見つけることができます。
ところが、１レコードの内容を更新する場合は、キー値だけでなくレコード番号も指定する必要があります。キー値だけでは同一キー値を持つレコードの特定が出来ないからです。そこで問題になるのが、このレコード番号が最下層のIBにしか格納されていないと言うことです。
試作版のこのロジックを調べると、同一キー値の場合、先頭のレコードから一つ一つレコード番号を最下層のIBまでたどって比較していました。もし値がセットされていない項目のインデックスの場合、何万レコードすべてがスペースという同一キーになっていますので、結果、全件検索と同じ動作になってしまいます。
さて、これをどう直せばいいのか。
すぐにバイナリーサーチというアルゴリズムを応用すればいいのは分かったのですが、階層構造の中の最下層の値のバイナリーサーチというのは初めてです。
10月の頭からアルゴリズムを考え始めて11月の終わりまでかかりました。
すぐにコード化してテストすると、ものの見事に、ループすることなく高速に動作するようになったのです。その後一箇所ロジックを修正しただけで、今も立派に働いてくれています。 KAI