作為開(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ù)次磁盤(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)存中，這樣可以減少IO操作次數(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用跳表？

既然B+樹(shù)這么多優(yōu)點(diǎn)，為啥Redis要用跳表實(shí)現(xiàn)ZSET呢（不只是跳表，詳見(jiàn)下面鏈接）？而不是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ù)的插入和刪除需要考慮平衡性，所以還是成本挺高的。

總結(jié)

以上，就是關(guān)于《InnoDB為什么不用跳表，Redis為什么不用B+樹(shù)？》這個(gè)問(wèn)題的我的一些理解，其實(shí)這個(gè)問(wèn)題想要回答好還挺難的。

首先要知道為啥Innodb使用紅黑樹(shù)，其次還要了解Redis中的Zset數(shù)據(jù)結(jié)構(gòu)，還需要知道跳表的原理。