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

下面為大家介紹3種高級數據結構分別為：跳躍表，紅黑樹和B樹，接下來詳細看一下這3種數據結構。

1.跳躍表

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

2.紅黑樹

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

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

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

2）根是黑色。

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

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

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

3.B樹

B樹有一種說法是二叉查找樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于走右結點。但是實際上這樣翻譯是一種錯誤，B樹就是 B-tree 亦即B-樹。

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

其實，這些所謂的高級數據結構往往是一些簡單的數據結構衍生出來的，我們想要學習高級的數據結構，就必須打好基本的數據結構的基礎，在本站的數據結構和算法教程中有對各種基本數據結構的詳細講解，我們可以以此為根基，深入鉆研數據結構這門學科。