[B! zip list][skip list] yassのブックマーク

yass id:yass

zip listとskip listに関するyassのブックマーク (2)

一体いつからRedisがSorted Setの実装にSkip Listしか使ってないと錯覚していた？ - 愛と勇気と缶ビール
デフォルトの設定 (zset-max-ziplist-entries, zset-max-ziplist-value) では該当するSorted Setのエントリ数が128個以下該当するSorted Setに含まれるmember (not score) のデータ長が全て64byte以下という2つの条件が成立している場合、Sorted Setの表現にはSkip ListではなくZip Listというデータ構造が使われる。ZADD, ZCOUNT等の実装もどちらのデータ構造を使っているかのフラグで分岐している。 Zip Listはポインタを使わずデータとそのオフセットだけで表現された双方向リストであるため、空間効率はよいが全体のサイズが大きくなるとすぐ使えなくなる。 Redisにおいては、Sorted Setへのinsertに際して上記条件のどちらかが満たされなくなった場合にZip Li
yass 2013/08/09
" デフォルトでは *該当するSorted Setのエントリ数が128個以下 *該当するSorted Setに含まれるmember (not score) のデータ長が全て64byte以下という2つの条件が成立している場合、Sorted Setの表現にはZip Listというデータ構造が使われる"

redis

sorted set

skip list

data structure

zip list
リンク
What are the underlying data structures used for Redis?
I'm trying to answer two questions in a definitive list: What are the underlying data structures used for Redis? And what are the main advantages/disadvantages/use cases for each type? So, I've read the Redis lists are actually implemented with linked lists. But for other types, I'm not able to dig up any information. Also, if someone were to stumble upon this question and not have a high level su
yass 2013/03/27
"Redis uses Skip Lists as the underlying data structure for Sorted Sets. "

Redis

data structure

skip list

hash

djb2

zip list

binary search
リンク
1