前言
作為開(kāi)發(fā)人員郎嫁，我們每天都要開(kāi)發(fā)大量的接口秉继，其中包括了讀接口和寫(xiě)接口，而對(duì)于寫(xiě)接口來(lái)說(shuō)泽铛，除了要保證他的性能尚辑、可用性以外，還需要有一個(gè)重要的問(wèn)題盔腔，那就是考慮如何保證接口的冪等性
Innodb是MySQL的執(zhí)行引擎杠茬，MySQL是一種關(guān)系型數(shù)據(jù)庫(kù)，而Redis是一種非關(guān)系型數(shù)據(jù)庫(kù)弛随。這兩者之間比較大的區(qū)別是：關(guān)系型數(shù)據(jù)庫(kù)以表的形式進(jìn)行存儲(chǔ)數(shù)據(jù)瓢喉，而非關(guān)系型數(shù)據(jù)庫(kù)以Key-value的形式存儲(chǔ)數(shù)據(jù)。
在InnoDB中舀透，索引是采用B+樹(shù)實(shí)現(xiàn)的栓票，在Redis中，ZSET是采用跳表（不只是跳表）實(shí)現(xiàn)的愕够，無(wú)論是B+樹(shù)走贪，還是跳表，都是性能很好的數(shù)據(jù)結(jié)構(gòu)惑芭，那么坠狡，為什么InnoDB為什么不用跳表，Redis為什么不用B+樹(shù)遂跟？
我們都知道逃沿，MySQL是基于磁盤(pán)存儲(chǔ)的应闯，Redis是基于內(nèi)存存儲(chǔ)的疲迂。
而之所以Innodb用B+樹(shù)，主要是因?yàn)锽+樹(shù)是一種磁盤(pán)IO友好型的數(shù)據(jù)結(jié)構(gòu)冻辩，而Redis使用跳表越败，是因?yàn)樘韯t是一種內(nèi)存友好型的數(shù)據(jù)結(jié)構(gòu)触幼。

“B+樹(shù)”對(duì)磁盤(pán)友好硼瓣？

• 首先究飞，B+樹(shù)的葉子節(jié)點(diǎn)形成有序鏈表置谦，可以方便地進(jìn)行范圍查詢操作。對(duì)于磁盤(pán)存儲(chǔ)來(lái)說(shuō)亿傅，順序讀取的效率要高于隨機(jī)讀取媒峡，因?yàn)樗梢猿浞掷么疟P(pán)預(yù)讀和緩存機(jī)制，減少磁盤(pán) I/O 的次數(shù)葵擎。
• 其次谅阿，由于B+樹(shù)的節(jié)點(diǎn)大小是固定的，因此可以很好地利用磁盤(pán)預(yù)讀特性酬滤，一次性讀取多個(gè)節(jié)點(diǎn)到內(nèi)存中签餐，這樣可以減少I(mǎi)O操作次數(shù)，提高查詢效率盯串。
• 還有就是氯檐，B+樹(shù)的葉子節(jié)點(diǎn)都存儲(chǔ)數(shù)據(jù)，而非數(shù)據(jù)和指針混合体捏，所以葉子節(jié)點(diǎn)的大小是固定的冠摄，而且節(jié)點(diǎn)的大小一般都會(huì)設(shè)置為一頁(yè)的大小，這就使得節(jié)點(diǎn)分裂和合并時(shí)几缭，IO操作很少河泳，只需讀取和寫(xiě)入一頁(yè)。
• 所以年栓，B+樹(shù)在設(shè)計(jì)上考慮了磁盤(pán)存儲(chǔ)的特點(diǎn)和性能優(yōu)化拆挥，我曾經(jīng)分析過(guò)，當(dāng)Innodb中存儲(chǔ)2000萬(wàn)數(shù)據(jù)的時(shí)候某抓，只需要3次磁盤(pán)就夠了竿刁。
• 而跳表就不一樣了，跳表的索引節(jié)點(diǎn)通過(guò)跳躍指針連接搪缨，形成多級(jí)索引結(jié)構(gòu)食拜。這導(dǎo)致了跳表的索引節(jié)點(diǎn)在磁盤(pán)上存儲(chǔ)時(shí)會(huì)出現(xiàn)數(shù)據(jù)分散的情況，即索引節(jié)點(diǎn)之間的物理距離可能較遠(yuǎn)副编。對(duì)于磁盤(pán)存儲(chǔ)來(lái)說(shuō)负甸，隨機(jī)訪問(wèn)分散的數(shù)據(jù)會(huì)增加磁頭的尋道時(shí)間，導(dǎo)致磁盤(pán) I/O 的性能下降痹届。

Redis的跳表介紹

• 跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)呻待，通過(guò)使用多級(jí)索引來(lái)加快查詢操作的速度。每個(gè)節(jié)點(diǎn)包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針队腐，而每個(gè)節(jié)點(diǎn)還可以有多個(gè)指向下層節(jié)點(diǎn)的指針蚕捉，形成了一個(gè)多層級(jí)的鏈表結(jié)構(gòu)。
• 在跳表中柴淘，每一層的鏈表都是按照升序排列的迫淹，且每層的節(jié)點(diǎn)數(shù)量逐層減少秘通。最底層包含所有節(jié)點(diǎn)，而每個(gè)更高層都是前一層的子集敛熬，節(jié)點(diǎn)數(shù)更少肺稀。這樣一來(lái)，當(dāng)進(jìn)行查詢時(shí)应民，可以從最高層開(kāi)始比較節(jié)點(diǎn)的值话原，如果找到了目標(biāo)節(jié)點(diǎn)或者找到了比目標(biāo)節(jié)點(diǎn)更大的節(jié)點(diǎn)，就轉(zhuǎn)到下一層進(jìn)行查找诲锹，直到最底層找到目標(biāo)節(jié)點(diǎn)或者確認(rèn)目標(biāo)節(jié)點(diǎn)不存在繁仁。
• 跳表的核心思想是通過(guò)建立多級(jí)索引，提供了類似于二分查找的效果归园，從而將查詢時(shí)間從線性的 O(n) 降低到對(duì)數(shù)的 O(log n)改备。這是跳表相對(duì)于傳統(tǒng)鏈表的一個(gè)顯著優(yōu)勢(shì)。
• Redis 使用跳表來(lái)實(shí)現(xiàn)有序集合的存儲(chǔ)和操作蔓倍。每個(gè)有序集合的節(jié)點(diǎn)包含一個(gè)分值（score）和一個(gè)成員（member）悬钳。跳表中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)有序集合的成員，而節(jié)點(diǎn)的分值則用于進(jìn)行排序偶翅。
• 通過(guò)使用跳表默勾，Redis 在有序集合中可以快速執(zhí)行插入、刪除和范圍查詢等操作聚谁，而不需要像傳統(tǒng)的線性鏈表一樣遍歷整個(gè)集合母剥。這使得 Redis 在處理大規(guī)模有序數(shù)據(jù)時(shí)具有良好的性能。
• Redis 的跳表是一種用于實(shí)現(xiàn)有序集合的高效數(shù)據(jù)結(jié)構(gòu)形导，通過(guò)多級(jí)索引和鏈表結(jié)構(gòu)环疼，實(shí)現(xiàn)了快速的插入、刪除和范圍查詢操作朵耕。它是 Redis 在處理有序數(shù)據(jù)時(shí)的重要組成部分炫隶，為 Redis 提供了出色的性能和靈活性。

為什么Redis用跳表阎曹？
既然B+樹(shù)這么多優(yōu)點(diǎn)伪阶，為什么Redis要用跳表實(shí)現(xiàn)ZSET呢？而不是B+樹(shù)呢处嫌？

• 主要是因?yàn)镽edis是一種基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)栅贴。他其實(shí)不需要考慮磁盤(pán)IO的性能問(wèn)題，所以熏迹，他完全可以選擇一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)檐薯，并且性能也能接受的 ，那么跳表就很合適注暗。
• 因?yàn)樘硐鄬?duì)于B+樹(shù)來(lái)說(shuō)坛缕，更簡(jiǎn)單墓猎。相比之下，B+樹(shù)作為一種復(fù)雜的索引結(jié)構(gòu)祷膳，需要考慮節(jié)點(diǎn)分裂和合并等復(fù)雜操作，增加了實(shí)現(xiàn)和維護(hù)的復(fù)雜度屡立。
• 而且直晨，Redis的有序集合經(jīng)常需要進(jìn)行插入、刪除和更新操作膨俐。跳表在動(dòng)態(tài)性能方面具有良好的表現(xiàn)勇皇，特別是在插入和刪除操作上。相比之下焚刺，B+樹(shù)的插入和刪除需要考慮平衡性敛摘，所以還是成本挺高的。

延伸
《Innodb為什么不用紅黑樹(shù)乳愉？》
《Innodb為什么不用B樹(shù)兄淫？》
《為什么Redis 7.0中使用ListPack實(shí)現(xiàn)ZSet？》
《Redis的ZSet中zipList和skipList是什么蔓姚？》