Indexable B-treeを作る - $koherent->diary

新幹線で東京に移動している間に前の記事、Google App Engineでランキングやページングを実現するに信じられないくらいのブックマークがついていてびっくりしているのですが、新幹線の中でぼーっと考えているとより高速なランキングを作る方法に気付きました。それはIndexable B-treeを作るということです（Indexable B-treeなんてものがあるのかもわからないです。もしかしたら別の名前で呼ばれているかもしれません）。

今は時間がないので実装して試せないのが残念なのですが、アイディアだけ書いておきます。

B-treeではm分木になっており、各ノードには複数の子ノードへのポインタの配列とどの子ノードに進めばいいかを判別するために子ノードからたどれる値の最小値が入っています。これに加えて、その子ノードからたどれる値の個数も記録しておけばIndexableにできるのではないかと思います。更新時も再帰的に親ノードの個数を書き換えていけばOKです。子ノードからたどれる値の個数ではなく、その子ノードよりも小さい値のノードもすべて含んで、集計した合計個数を格納しておくこともできます。この場合、更新負荷は大きくなりますが（Datastoreで実装する場合には、アクセス回数は変わらないと思います）、参照は早くなります。

B-treeだと何がうれしいかというと、圧倒的にDatastoreアクセスの回数を減らすことができることです。通常のB-treeのように1024分木とか4096分木とかにしてしまえば、10万、100万単位の値からでも、2〜4回程度のDatastoreアクセスで順位（インデックス）を算出することができます。

ただし、一つのノードあたりのバイト数は大きくなってしまうので、Datastore上に実装する場合にその読み書きにどれくらいの時間がかかるかが問題です。エンティティのサイズは、1024分木で数十KB程度になると思います。エンティティのサイズが大きくなってパフォーマンスが落ちてしまうのであれば、mを小さくして（例えば64分木などにして）高速化をはかることもできます。どのmが一番パフォーマンスが良いかは試してみないとわかりません（各バイト数でのエンティティの読み書き速度さえわかれば、計算で概算することはできます。どこかにそんなデータないでしょうか？）。

今すぐにでも実装して検証したいのですが、今週は仕事が詰まっているため時間をとれそうにありません。残念です…。時間が取れ次第検証して、使えそうならライブラリとして公開したいと思います。