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/

Published: 2011-01-14(Fri) 12:51