數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過(guò)這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來(lái)的結(jié)構(gòu)類(lèi)型。基本的數(shù)據(jù)結(jié)構(gòu)我們都接觸過(guò)，總體而言還是比較簡(jiǎn)單的，本文我們就來(lái)聊一聊相對(duì)而言比較難的高級(jí)數(shù)據(jù)結(jié)構(gòu)。

下面為大家介紹3種高級(jí)數(shù)據(jù)結(jié)構(gòu)分別為：跳躍表，紅黑樹(shù)和B樹(shù)，接下來(lái)詳細(xì)看一下這3種數(shù)據(jù)結(jié)構(gòu)。

1.跳躍表

跳躍列表是對(duì)有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機(jī)化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過(guò)部分列表。是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于紅黑樹(shù)和AVL樹(shù)(對(duì)于大多數(shù)操作需要O(logn)平均時(shí)間)，但是實(shí)現(xiàn)起來(lái)更容易且對(duì)并發(fā)算法友好。redis 的 sorted SET 就是用了跳躍表。

2.紅黑樹(shù)

我們對(duì)平衡二叉樹(shù)的定義往往是模棱兩可的，在這里大概說(shuō)一下，左右子樹(shù)高度差用 HB(k) 來(lái)表示，當(dāng) k=0 為完全平衡二叉樹(shù)，當(dāng) k<=1 為AVL樹(shù)，當(dāng)k>=1 但是接近平衡的是紅黑樹(shù)，其它平衡的還有如Treap、替罪羊樹(shù)等，總之就是高度能保持在O(logn)級(jí)別的二叉樹(shù)。紅黑樹(shù)是一種自平衡二叉查找樹(shù)，也被稱為"對(duì)稱二叉B樹(shù)"，保證樹(shù)的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN，但實(shí)際上很難遇到）。它是復(fù)雜的，但它的操作有著良好的最壞運(yùn)行時(shí)間：它可以在O(logn)時(shí)間內(nèi)做查找，插入和刪除。

紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色為紅色或黑色。在二叉查找樹(shù)強(qiáng)制一般要求以外，有如下額外要求：

1）節(jié)點(diǎn)是紅色或黑色。

2）根是黑色。

3）所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)，亦即空節(jié)點(diǎn)）。

4）每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色的。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）

5）從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

3.B樹(shù)

B樹(shù)有一種說(shuō)法是二叉查找樹(shù)，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)。但是實(shí)際上這樣翻譯是一種錯(cuò)誤，B樹(shù)就是 B-tree 亦即B-樹(shù)。

B-樹(shù)（B-tree）是一種自平衡的樹(shù)，能夠保持?jǐn)?shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問(wèn)、插入數(shù)據(jù)及刪除的動(dòng)作，都在對(duì)數(shù)時(shí)間內(nèi)完成。B-樹(shù)，概括來(lái)說(shuō)是一個(gè)一般化的二叉查找樹(shù)，可以擁有多于2個(gè)子節(jié)點(diǎn)（多路查找樹(shù)）。與自平衡二叉查找樹(shù)不同，B-樹(shù)為系統(tǒng)大塊數(shù)據(jù)的讀寫(xiě)操作做了優(yōu)化。B-樹(shù)減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度。B-樹(shù)這種數(shù)據(jù)結(jié)構(gòu)可以用來(lái)描述外部存儲(chǔ)。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)的實(shí)現(xiàn)上，比如MySQL索引就用了B+樹(shù)。

其實(shí)，這些所謂的高級(jí)數(shù)據(jù)結(jié)構(gòu)往往是一些簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)衍生出來(lái)的，我們想要學(xué)習(xí)高級(jí)的數(shù)據(jù)結(jié)構(gòu)，就必須打好基本的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中有對(duì)各種基本數(shù)據(jù)結(jié)構(gòu)的詳細(xì)講解，我們可以以此為根基，深入鉆研數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科。