毫無疑問數(shù)據(jù)結(jié)構(gòu)是復(fù)雜的，讓人頭大的，大學(xué)時唯一掛科的就是數(shù)據(jù)結(jié)構(gòu)，上學(xué)時不用心，不曉得自己的職業(yè)生涯要一直被數(shù)據(jù)結(jié)構(gòu)支配。

或多或少，面試抱佛腳時，數(shù)據(jù)結(jié)構(gòu)都會背一背刷一刷，HashMap的紅黑樹，Redis的跳表一個個都跑不了。

當(dāng)回歸日常時，學(xué)習(xí)及理解數(shù)據(jù)結(jié)構(gòu)真的有什么收益嗎

舉個例子，最近看到IO多路復(fù)用的時候，說到select，poll與epoll對比時

有兩個點(diǎn)
1.epoll通過維護(hù)一個鏈表來記錄就緒事件，無需遍歷所有文件描述符來獲取所有就緒事件，而是通過事件通知機(jī)制，將就緒事件添加到鏈表中，epoll_wait()函數(shù)獲取所有就緒事件。

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //將所有需要監(jiān)聽的socket添加到epfd中while(1) {int n = epoll_wait(...);for(接收到數(shù)據(jù)的socket){//處理}
}

2.epoll通過紅黑樹來維護(hù)所有文件描述符。

當(dāng)我看到第2點(diǎn)時，反應(yīng)是居然是你，真的有你，可算再次遇到你了，除了HashMap中，終于又和你體會到了鋪面而來的重逢喜悅感，另外帶著一種原來你真的挺有用的欣慰感。

紅黑樹、B+樹以及跳表這三個數(shù)據(jù)結(jié)構(gòu)，之前在我心目中，地位是一樣的，需要面試的時候，對于他們我口若懸河，頭頭是道，而日常開發(fā)就是，對不起，我們好像不太認(rèn)識。

紅黑樹HashMap，B+樹MySQL索引，跳表Redis跳表，我?guī)缀蹩煲阉麄儺嫷忍柫?#xff0c;背后的原理，為什么是這樣的，卻從來都想不起再去深究。

隨著開發(fā)的生涯越走越遠(yuǎn)，我很欣慰自己沒有原地踏步，那么為什么呢？

紅黑樹

紅黑樹不算是嚴(yán)格的二叉平衡查找樹，標(biāo)準(zhǔn)的二叉平衡查找樹父子上下節(jié)點(diǎn)的高度最大不會超過1，為了維護(hù)這個平衡，當(dāng)新增或者刪除數(shù)據(jù)時，標(biāo)準(zhǔn)的平衡二叉查找樹需要耗費(fèi)更多的資源，不可避免需要進(jìn)行多次旋轉(zhuǎn)。
紅黑樹使得二叉查找樹能保持大體的平衡，不至于退化成鏈表，又不至于頻繁的轉(zhuǎn)換操作，在與平衡二叉樹的時間復(fù)雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實(shí)現(xiàn)起來也更為簡單。

紅黑樹在二叉查找樹的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)。所以紅黑樹適用于搜索，插入，刪除操作較多的情況。

應(yīng)用場景

紅黑樹常用于存儲內(nèi)存中的有序數(shù)據(jù)，增刪很快，內(nèi)存存儲不涉及 I/O 操作。

• HashMap
• IO多路復(fù)用-epoll
• Linux公平調(diào)度器

跳表

1.對有序列表查詢性能的優(yōu)化。

2.跳表的基本思想是將有序鏈表分層，每個節(jié)點(diǎn)在不同層中擁有不同數(shù)量的前向指針。上層鏈表是下層鏈表的子集，且上層鏈表中的元素順序與下層鏈表一致。

3.通過增加指針和添加層級的方式，跳表可以實(shí)現(xiàn)對數(shù)級別的查找效率。

4.實(shí)現(xiàn)簡單

原以為除了Redis ZSet中，也不會再見到跳表了，直到看到LevelDB時，了解到其Memtable中使用的也是跳表實(shí)現(xiàn)。

使用場景

• Redis zset
• LevelDB底層數(shù)據(jù)結(jié)構(gòu)

B+樹

號稱為文件系統(tǒng)而生的數(shù)據(jù)結(jié)構(gòu)。

多路平衡二叉樹，選用B+樹最大的理由，我理解是樹的高度，高度，還是tm的高度。
B+樹只需要3層就能存儲大約2kw的數(shù)據(jù)，定位一個數(shù)據(jù)，也就是頁大的讀取IO次數(shù)，最多3,4次，換成紅黑樹或者跳表，大概需要10倍左右；
對于文件系統(tǒng)、數(shù)據(jù)庫的場景，需要從磁盤讀取數(shù)據(jù)，IO的耗費(fèi)相對于內(nèi)存來說是不可接受的。

使用場景

B+ 樹在處理磁盤I/O、范圍查詢和大數(shù)據(jù)量管理方面優(yōu)勢明顯

• 數(shù)據(jù)庫：MySQL innodb索引，PostgreSQL索引，Oracle索引等基本主流的數(shù)據(jù)庫
• 文件系統(tǒng)：NTFS、ReiserFS、大名鼎鼎的HDFS等文件系統(tǒng)