Sorted Set的實現(xiàn)是hash table(element->score, 用于實現(xiàn)ZScore及判斷element是否在集合內),和skip list(score->element,按score排序)的混合體。 skip list有點像平衡二叉樹那樣,不同范圍的score被分成一層一層,每層是一個按score排序的鏈表。
ZAdd/ZRem是O(log(N)),ZRangeByScore/ZRemRangeByScore是O(log(N)+M),N是Set大小,M是結果/操作元素的個數(shù)??梢?,原本可能很大的N被很關鍵的Log了一下,1000萬大小的Set,復雜度也只是幾十不到。當然,如果一次命中很多元素M很大那誰也沒辦法了。