跳躍表
有序鏈表
有序鏈表是鏈表中的所有元素按照升序或者降序排列。如下圖所示：
如果要查找上圖中的25。得從頭開始一個(gè)一個(gè)往下遍歷對(duì)比。那么時(shí)間復(fù)雜度將會(huì)是O(n)。對(duì)有序鏈表的插入和刪除操作，也得先遍歷找到對(duì)應(yīng)的元素或者位置才能操作，插入和刪除基本不耗時(shí)間，查找才是性能瓶頸。
跳躍表
對(duì)有序鏈表查詢性能的優(yōu)化。
將有序鏈表中的部分節(jié)點(diǎn)抽出來分幾層，每一層也是一個(gè)有序鏈表。查找的時(shí)候從最高層開始找，當(dāng)?shù)竭_(dá)某個(gè)節(jié)點(diǎn)的時(shí)候，如果next的值大于要查找的值或者next是null，則去下面一層繼續(xù)查找，以此類推。
如上圖中的跳躍表，如果要查找元素29:
- 首先去第二層查找，當(dāng)?shù)竭_(dá)元素25到時(shí)候，它到next是null，所以進(jìn)入第一層；
- 元素25在第一層的next是33，大于元素29，所以進(jìn)入第0層；
- 元素25在第0層的next是29，匹配找到。
壓縮列表
壓縮列表ziplist本質(zhì)上就是一個(gè)字節(jié)數(shù)組。數(shù)組是一種線性的數(shù)據(jù)結(jié)構(gòu)。每一個(gè)元素可以是整數(shù)或者字節(jié)數(shù)組。注意：ziplist本身是一個(gè)字節(jié)數(shù)組，它的元素也可以是字節(jié)數(shù)組。
因?yàn)閿?shù)組在插入/刪除的時(shí)間復(fù)雜度，所以ziplist一般在元素?cái)?shù)量不多的情況下使用。另外因?yàn)樗脑乜梢源鎯?chǔ)字節(jié)數(shù)組，字節(jié)數(shù)組對(duì)于上層應(yīng)用來說就是字符串，所以在字符串比較短的情況下才使用ziplist。
ziplist的結(jié)構(gòu)
zlbytes: 表示壓縮列表總的字節(jié)數(shù)，占4個(gè)字節(jié)。那么壓縮列表總的字節(jié)數(shù)最多是2^32-1 個(gè)字節(jié)。
zltail： 壓縮列表的尾部元素，占4個(gè)字節(jié)。
zllen： 壓縮列表的元素個(gè)數(shù)，占2個(gè)字節(jié)。那么壓縮列表總的元素個(gè)數(shù)組多是2^16-1個(gè)。
entryX：壓縮列表里面的元素，可以是整數(shù)或者字節(jié)數(shù)組，長度不限。
zlend：壓縮列表的結(jié)尾，固定值為0xFF，占1個(gè)字節(jié)
所以根據(jù)壓縮列表的結(jié)構(gòu)可以知道，它的總大小不能超過(2^32 - 1)個(gè)字節(jié)。它的元素個(gè)數(shù)不能超過(2^16 - 1)。
ziplist里面entry的結(jié)構(gòu)：
previous_entry_length: 表示前一個(gè)元素的字節(jié)長度。占1個(gè)或者5個(gè)字節(jié)。如果前一個(gè)元素的字節(jié)長度小于254字節(jié)時(shí)，占1個(gè)字節(jié)；否則就占5個(gè)字節(jié)。占5個(gè)字節(jié)的時(shí)候，第一個(gè)字節(jié)是固定的0xFE，后面四個(gè)字節(jié)才是表示長度。所以這么說來，單個(gè)元素的字節(jié)數(shù)也不能超過(2^32 - 1)。
encoding： 表示當(dāng)前元素（也就是content的內(nèi)容）存儲(chǔ)的是字節(jié)數(shù)組還是整數(shù)。長度可變。
應(yīng)用
在有序集合zset的實(shí)現(xiàn)里面，跳躍表和壓縮列表都有用到。
根據(jù)上面都描述，壓縮列表的使用場(chǎng)景一般是短字符串，且元素個(gè)數(shù)不能太多。所以在zset里面有幾個(gè)配置：
zset-max-ziplist-entries: 默認(rèn)值128， 當(dāng)元素個(gè)數(shù)小于這個(gè)值都時(shí)候使用壓縮列表。否則使用跳躍表。
zset-max-ziplist-value：默認(rèn)值64，當(dāng)每個(gè)元素的字符串長度小于這個(gè)值的時(shí)候使用壓縮列表，否則使用跳躍表。
滿足這兩個(gè)條件中的任意一個(gè)條件，就會(huì)轉(zhuǎn)換到跳躍表。而轉(zhuǎn)換到跳躍表之后，即便把元素刪除，也不好回退到壓縮列表。
