Redis の sorted set にかんするメモ
ほんとにチラ裏ですが。
http://japan.cnet.com/blog/kenn/2011/01/13/entry_30011467/ をみてて、なんで redis の ZRANK はやいのかなーとおもって、しらべたののメモです。
skip list については、http://www.geocities.jp/m_hiroi/light/pyalgo19.html このへんがわかりいいとおもいました。
INSERT: O(log(n))
REMOVE: O(log(n))
ですよ、と。
hash で member → score のデータを保持してる。
skip list で score → member のデータも保存してる
skip list の実装は William Pugh のオリジナルのコピーだけど、ちがいも3つほどあるよ。
で、ZRANK がなんではやいのかというと、各 skip list の要素の中に span っていうのがついてて、skip した数がわかるようになってるからって話だった。
で、どういう風にうごいてるのかなーってのはわかったんだけど、実際にリーダーズボードをつくるときは ZRANK だと、「その要素の順位」はわかるけど、それだけでは同率の人の順位がわからないから、ZRANGEBYSCORE $score $score LIMIT 0 1 でそのスコアの要素の先頭をもとめて、その要素にたいして ZRANK するかんじなのかな、とおもった。
で、Radis についてなんですが、基本的に、データ構造の操作の処理とかぜんぶ redis.c の中にはいってるし、よめば普通によめるかんじのソースなので、よむといいとおもった。
あと、しらべてたら、普通にリーダーズボードを redis で実装する、っていう記事と gem あった。
http://blog.agoragames.com/2011/01/01/creating-high-score-tables-leaderboards-using-redis/