RedisのSorted Setで挿入コストが低い木構造（ただし実質有限）を入れ子区間モデルで。

2015-10-21

再帰的な処理はなしで、一撃であるノードの子ノードを全部取りたい、挿入も楽にやりたいな～というのが発端です。

概要:入れ子区間モデルっぽいのを使う

前回のメモアプリでは、各メモへのリプライという機能があり、多分木が並んでる感じになっています。

メモは、基本的に直前に作成、更新されたものから順番に並んでいます。メモのidをメンバーにしたSorted Setを用意し、順番にスコアを与えます。

最大のscoreは数値データを一つ用意して、インクリメントしたものを使用しています。

作成、更新されたものに最大のscoreを与えることによって、更新順序での表示を実現しています。

メモには

があり、親メモの作成、更新時には先頭に配置されるという仕組みでした。一方でリプライはリプライ元のメモより後ろに表示するような動作です。

SQL界では木構造を表現し、なおかつその子を再帰的な処理なしで取得するために、入れ子集合モデルというものがあります。

それを用いるとだいたいこのようになります。

あるメモの子は、そのメモの左端 < n < そのメモのscoreのscoreをもちますので、SortedSetのrange関係のメソッドを用いれば一撃で取れます。

SortedSetではZRANGEBYSCORE zset min maxと普通にminとmaxを渡すとmin <= score <= maxという評価でmemberを持ってきてしまいます。

ZRANGEBYSCORE zset (min (maxとかくと、min < score < maxとなり、親も、次にいるかもしれない関係の無いメモも含まずに取得できます。

Rubyのredis-objectsでも同様です。

# redis-objects
sorted_set.rangebyscore("(#{edge}", "(#{parent_score}")

入れ子集合モデルは便利ですが、挿入時に他のノードにも更新をかけなくてはならないという欠点があります。その欠点をどうにかしたのが入れ子区間モデルで、scoreに実数を使います。

このように、挿入されたリプライメモのみが更新対象となります。挿入されたメモの左端は、親の左端か次のメモのscoreのどちらか大きい方になります。

挿入時には親のscore、親の左端、次のメモのscoreを見る必要がありますが、特に更新は必要ありません。

親メモは必ずscore - 1の左端を持つので、子のscoreは単純に移動分だけの増加で大丈夫です。

この場合だけ左端までの距離が不定なため、移動するすべてのメモの再計算が必要になります。

リプライ持ちのメモを更新した時は、リプライごとごっそり移動します。

なので、左端は絶対scoreではなく、自分のscoreからの距離で算出しているため、これが一番らくでした。

このアプリをつくっているちょっと前に読んでいた**「SQLアンチパターン」で入れ子集合モデルが紹介されていて、それの改造版の入れ子区間モデルが「達人に学ぶDB設計徹底指南書」**に載っていると紹介されていました。

たまたま持っていたので読んでみると（買ったけどそこまで読んでなかった）、なるほど～という感じで、その時はそれで終わったのですが、これを作ってるときにふと思いだして使ってみるとぴったりフィット。

思ってもみなかったところで読んだことが使えるとうれしい。本、もっと読もう。読んでどんどん使おう。