索引ファイルを作る
ここ１３年ほど（！）使っている一連の検索ライブラリについて解説したいと思います。 以前は、ISAMとかBTreeとか呼ばれたりもしていましたし、今ならSQLを使って解決するような命題ですが、 Ｃ言語から簡単に呼び出せるライブラリとして今日も活躍しています。
キー検索とは？
２分岐検索や、バランス木などについては、多くのアルゴリズム本がありますので、そちらを参照してください。 ここでは、問題の解き方を掘り下げながら、新しいファイルフォーマットを考えます。
データがレコード形式で保存されていて、ある文字列をキーに、レコードを探したいというのは、よくある需要です。
他にも、特定条件に一致するレコードをを全部抽出したいという需要もありますが、ここでは、キー検索にまとを絞って考えます。
この問題を単純化すると、ある文字列と特定の数値を登録しておいて、その文字列から数値を求めるということになります。
それほど難しくなさそうなのですが、挿入、削除しても、高速に取り出せるようにするには、ちょっとした工夫が必要です。
第一世代 ＣＲＣをシフトする
一番最初に必要に迫られ、このコードを作ったのは１９９７年でした。 以前からメモリ上でデータを探し出すとき、ハッシュはよく利用しておりました。 このハッシュという方式は、実装が比較的簡単なのですが、衝突検出があるという部分と、ファイル実装には向かないと書かれている書籍もあり、ファイルに実装するような中規模以上（まあ、１０万件〜１００万件）の検索には使っていませんでした。それ以前は、買い物ライブラリを使用していたのです。
しかし、Ｃ言語でゴハンを食べている身、「書けないプログラムがあってはならぬ」ということで、この部分にも手を出しました。最初の思いつきは、ハッシュを何ＢＩＴかに区切って、これで分岐していき、３２ビット使い切ってハッシュが一致したら、片方向リンクでいいんじゃないかというものでした。
この方針、思いつきはよかったようで３年ほどは使っていました。ただ、ハッシュとしてＣＲＣを使っていたので、分散性がイマイチで、１００万件を超えるデータ登録を行ったところで、データ衝突が始まり速度が低下するというものになっていました。このときは６ビットごとに分割（つまり１レコードで６４方向に分岐）を５回で、３０ビット、残り２ビットは捨てていました。これでも、１０億くらいあるので、まさか１００万ちょいで、衝突が多発するとは思ってなかったのです。調べてみると、ＣＲＣとはそういうモノだそうな。
第二世代 アスキー木で１０年しのぐ
２０００年頃、ＣＲＣよりいい関数を探さないとなあと思っていたころ（実は、これは簡単に見つかります）突然、ハッシュの大問題、衝突を解消する方法を思いついたのです。これが、「アスキー木」と名づけたもので、ハッシュではなく、元のキーそのもので分岐していけば、キー文字列最終まで分岐し続ければ衝突などしないではないかというものです。
１文字が８ビットですから、これを上位下位４ビットごとに分けて（つまり１レコード１６方向分岐）キーそのもので木を構成しようというものです。上位、下位の順にデータを登録すれば、データの前後関係もわかりそうです。前方一致検索などもできそうです。いいコトづくめです。さっそく実装し、かれこれ２０１０年まで１０年近く使ってきました。問題点としては、第一世代よりもインデックスファイルのサイズが大きくなったことですが、まあ、昨今のハードディスク容量からすれば問題になるようなものではありませんでした。
第三世代 ハッシュ復活
で、２０１０年ふと気づいたのです。「アスキー木」を実装してから１０年近くたつのに、データの前後関係や前方一致検索を使う機会がほとんどなかったのです。うちの仕事では、単純一致検索で事足りる需要ばかりだったのです。すると、データ部分には前後関係を保持するために消費している部分があるはずだということが気になり、もっと速度を上げることができるのではないかと思うようになりました。
そこで、以前開発を打ち切っていたＣＲＣシフト木のソースを取り出し、アスキー木のインターフェースなどを取り入れつつ改良を試みました。もちろんＣＲＣ方式は廃止です。もうひとつの大きな改良としては、木の「太さ」を幹ほど太くするというものです。自然の木は幹は１本で太く、枝がたくさんあります。ＣＲＣシフト木もアスキー木も、分岐テーブルは、最初の幹から先端まで一定です。つまり、幹も枝も同じ太さだったのです。こんなところでバランスの悪いことをしていたのです。
どうせ、根っこのところは１つしかありませんから、ドーンとファイルサイズをとってもいいわけです。今回は、根っこのみ１６ビット分岐（６５５３６方向分岐）にすることにします。ただ、インデックスファイルができた時点で２５６Ｋバイト＋αにはなってしまいます。昔プログラマーとしては、１．４４Ｍフロッピーの２０％程度かあなどと考えますが、最近の写真１枚にもみたないサイズなのでよしとします。ここを６ビットから１６ビットにすることで、２回くらいのseek()関数read()関数が節約でき高速検索が期待できます。
アスキー木 vs ハッシュ木
せっかくつくるのですから、以前のアスキー木より性能が出ていなくては困ります。 そこでいろいろな条件でベンチマークを取ってみました。 まずは、キー文字列の長さを３２文字、存在する文字は0x20-0x7eまでの全てという条件でデータを乱数で１０万件作り、これを全部登録し、検索する時間を計測してみました。
| データ登録時間 | データ検索時間 | ファイルサイズ | |||
| アスキー木 | ハッシュ木 | アスキー木 | ハッシュ木 | アスキー木 | ハッシュ木 |
| 3031[ms] | 2281[ms] | 1312[ms] | 719[ms] | 7,700,520bytes | 8,487,488bytes |
ハッシュ木のほうが登録・検索とも高速です。ところが、当初ファイルサイズも小さくなると思っていたのですが、甘い期待は裏切られました。データ配置構造はハッシュ木のほうが上だと思うのですが、ハッシュ値の６４ビットを格納するエリアと、衝突データリンク保持のための３２ビットエリアがデータ１件ごとに必要であり、この部分が無視できないようです。
しばらく考えてみると、この実験はアスキー木に有利だったことがわかりました。データが８ビット中９５パターンも分散するような良いデータはなかなかありません。半角カタカナでフリガナ検索したとしても８ビット中現れるコードは６４パターン、６ビット分です。メールアドレスなら、数字＋アルファベット＋＠などでせいぜい４０パターン、電話番号なら１０パターンです。そして、アスキー木は偏ったデータではインデックスが大きくなるという特性があるのを忘れていました。そこでメールアドレスデータを想定した、８ビットデータ中に４０パターンしか出てこないデータで同様の検証をしてみました。
| データ登録時間 | データ検索時間 | ファイルサイズ | |||
| アスキー木 | ハッシュ木 | アスキー木 | ハッシュ木 | アスキー木 | ハッシュ木 |
| 3375[ms] | 2282[ms] | 1515[ms] | 718[ms] | 8,568,120bytes | 8,471,168bytes |
ハッシュ木は、検索対象がハッシュなので、登録するデータに依存することなく、速度・データサイズとも変化は微小です。 これに対して、アスキー木は、データが偏ると速度低下を起こし、なおかつファイルサイズも大きくなっていることがわかります。しかし考えてみると、１０万件のデータの有無を調べて、ある場合、そのレコード番号を回答するという処理が0.7秒ちょっとで終わるというのは世のＰＣは速いもんですね。１件あたり７．２μ秒程度ってことになります。
もちろん登録件数が増えれば、探し出す元資料が大きくなるのですから、１件あたりの時間も伸びることになります。ツリー構造なので、登録データが２倍になっても時間が２倍になることはありませんが。そこで、登録件数を変えていって、登録時間と、検索時間がどのように変わるか調べてみました。
登録速度は４０万件のところで、ハッシュ木が急激に落ち込み、逆転しています。 これが、デッドスポット的なものなのか、それとも計測誤差なのかはわかりません。 あくまでイメージですが、枝分かれし始めるデータ件数があり、登録速度は階段状に変化するのかもしれません。
全般にわたり、ハッシュ木のほうが高速です。ハッシュ木に１６０万件のデータを登録したとしても、アスキー木に５万件登録したものより高速に検索できることがわかります。
しかし、ここまでくると、はたしてローカルＰＣでＮＴＦＳ上で実行していることが正しいのか微妙です。FreeBSDやLinux上で、使うＦＳによっても結果が違ってくるかもしれません。しかし、ハードウェアを同じ条件にして、ＯＳやＦＳを交換しながらベンチマークをとるのは大変です。・・・・まてよ、ＫＶＭを使って・・・・
無作為研究所トップページに戻る