Composite&Starategy OOデータモデルとdb4o
db4oの上にB+treeを活用したインデックスを実装しています。昨日の晩に一通り出来上がったのでdb4objectsのスタッフにチェックしてもらっているところです。
さて、これがそのB+treeインデックスのドメインモデルです。改めて見てみると、デザインパターンの王道、CompositeとStrategyパターンの組み合わせになっています。ということは、これはインデックスの選択肢を増やすというだけでなく、そのソースを使用したチュートリアルにも最適ではないかとひらめきました。
1/23日夜に、「じゃあおれが作るよ」という話になってから10日足らずで、B+treeのインデックスを実装できたという事実は、改めてdb4oの凄まじさを味あわさせてくれました。これをRDBMSやファイルで実装しようとしたら、めまいがします。できたとしても「変更」恐怖症・過敏症になりそうな。やる前から腱鞘炎がうずきそうです。
さて、きちんとしたチュートリアルは改めて整備するとして、ここでは３つポイントを挙げてみます。
- "B+-Tree"オブジェクトが巨大なツリーを形成したとき、どうやって必要な部分をメモリ内に取り出し、不要部分を永続化するか
- ノード内のキー配列検索スピードを向上させるために、プリミティブ型を使用したいが、なおかつ柔軟性を持たせるためにOOデザインができないか
- アクセスの多いホットなノードはキャッシュされ、逆に少ないコールドなノードはGCの対象になるようにし、OutOfMemoryエラーは決して引き起こさないようにするにはどうしたらよいか
- ノードの分裂と統合が発生したとき、その子ノードが親ノードへの参照を持っていると、それら全てのノードの参照を更新しなければならないが、これはディスクアクセスを増やすので、効率的な方法は無いか
１と３の解決策・・・db4oは一旦呼び出されたオブジェクトを、WeakReferenceとしてキャッシュしています。これはGCが呼び出されたら速やかにコレクトされる候補になる弱い参照です。objectContainer.ext().isCached(objectId)でキャッシュされているか確認できます。まずこのdb4oの内部機能を理解したうえで課題について考えてみると、B+-treeの各ノード間のリレーションを強い参照、つまり参照を宣言せずに、db4oのWeakReferenceを活用するようにすれば、１と３を同時に解決できます。
２の解決策・・・これはjava.lang.Comparableを継承しているBkeyインターフェースで解決しています。AbstractNodeがcharキーを持っていると、long、floatなど全てのプリミティブ型について別々にモデルを作っていかなくてはなりません。これは”絶対イヤ”です。AbstractNodeから見ると、あくまであるキーとの比較ができさえすればいいのですから、Bkeyとしてキーを宣言しておきます。そして実際のインスタンスはcharキーを持つCharBkeyというBkeyを実装したオブジェクトにするわけです。これに伴うデメリットは、Bkeyを辿ってcharに辿りつくので、永続化されているオブジェクトをメモリ内に呼び出す（Activate）時と更新時にその分のオーバーヘッドが生じることです。そのため、CharIndexNodeとCharLeafNodeというそれぞれIndexNodeとLeafNodeを継承するクラスにcharを宣言しておき、タイミングよくActivate時にはそこから取り出してBkeyにセットし、逆に更新時にはBkeyからcharにセットしています。これによってオーバーヘッドはほとんど無くなりました。
４の解決策・・・ノードへのアクセスは、追加・検索・削除いずれの場合も、まずは該当するLeafNodeの検索から始まります。ルートからリーフへ、その後検索時はリーフを右へ、追加・削除時は親を辿ってインデックスを上へという具合に続きます。つまり必ず親から子を呼び出すのです。従って子から親への参照はTransientとしておき、親が子をActivateした時に動的に参照を設定します。こうすることによって、分裂や統合が発生した場合は、db4oにキャッシュされている子ノードの親への参照を更新すればいいだけなので、ディスクへのアクセスは発生しません。
「オブジェクト指向の方法論をデータベースに適用する」このメリットが明らかに思える方はぜひ一度db4oをお試しください。きっと気に入ります。
db4o Japanese Community
http://www.db4o.com/japan/
japan@db4o.com
