zrange 是 redis sorted set 中的一個(gè)指令贾铝，最近線上有個(gè)查詢從 mysql 切到了 redis只恨，在使用 mysql 的 offset滤钱、limit 查詢時(shí)幢踏，當(dāng) offset 過(guò)大時(shí)會(huì)有性能問(wèn)題，不禁疑惑玻褪，用 redis 的 zrange 是否會(huì)有類(lèi)似的問(wèn)題呢肉渴？
看了下 redis sorted set 實(shí)現(xiàn)，當(dāng)一個(gè) sorted set 的元素?cái)?shù)量比較多带射，或者集合中的成員是比較長(zhǎng)的字符串時(shí)黄虱，底層會(huì)使用跳表來(lái)實(shí)現(xiàn)，關(guān)于跳表是什么不再贅述庸诱，網(wǎng)上相關(guān)文章很多捻浦，可以參考下。http://redisdoc.com/sorted_set/zrange.html 上說(shuō) zrange 的復(fù)雜度是 O(log(N)+M)桥爽， N 為有序集的基數(shù)朱灿，而 M 為結(jié)果集的基數(shù)。為什么是這個(gè)復(fù)雜度呢钠四？
ZRANGE key start stop [WITHSCORES]盗扒，zrange 就是返回有序集 key 中，指定區(qū)間內(nèi)的成員缀去，而跳表中的元素最下面的一層是有序的(上面的幾層就是跳表的索引)侣灶，按照分?jǐn)?shù)排序，我們只要找出 start 代表的元素缕碎，然后向前或者向后遍歷 M 次拉出所有數(shù)據(jù)即可褥影，而找出 start 代表的元素，其實(shí)就是在跳表中找一個(gè)元素的時(shí)間復(fù)雜度咏雌。跳表中每個(gè)節(jié)點(diǎn)每一層都會(huì)保存到下一個(gè)節(jié)點(diǎn)的跨度凡怎，在尋找過(guò)程中可以根據(jù)跨度和來(lái)求當(dāng)前的排名，所以查找過(guò)程是 O(log(N) 過(guò)程赊抖，加上遍歷 M 個(gè)元素统倒，就是 O(log(N)+M)，所以 redis 的 zrange 不會(huì)像 mysql 的 offset 有比較嚴(yán)重的性能問(wèn)題氛雪。
