前言

HashMap是怎么實現地？為什么JDK8之后要換成紅黑樹？MySQL的索引為什么要用B+樹？

這些問題在面試中是經常被問到的。今天抽空把這些數據結構進行總結。其實每種數據結構都是為了滿足某種場景的需求，都是有著某種內在的聯系的，今天我們將嘗試進行梳理和總結。此外，在我們對這些數據結構進行研究的時候，主要關注于其評價指標，包括查找，刪除，插入的時間復雜度。

這里解釋下，我只是對其進行了梳理和總結，里面的配圖是在網上找的，會在后面注明來源。

數組和鏈表

數組和鏈表是我們最先接觸到的數據結構，我們先來分析下

數組鏈表查找 O(1) O(n) 插入 O(n) O(1) 刪除 O(n) O(1)

注：我們一般設置一個哨兵節點，這樣在處理頭結點的刪除和插入的時候不至于進行特殊處理。

上面的鏈表說的是單鏈表，除此之外，我們還需要了解雙向鏈表和循環鏈表。

棧和隊列

這里需要注意，棧和隊列本質上是用數組/鏈表來實現的，不過二者是操作受限的線性表，其在特定的場景下可以發揮特有的作用。

跳表

跳表是什么？我們為什么需要跳表呢？

我們知道，二分查找的時間復雜度為lgn，性能是很好的，但是其只能局限在數組中，鏈表是不能使用二分查找的。那么有沒有辦法在鏈表中實現二分查找的特性呢？

如果數據是有序的，還是需要O(n)的時間復雜度。

那怎么提高查找效率呢？每兩個結點提取一個結點到上一級。

類推：

所以，當鏈表的長度 n 比較大時，在構建索引之后，查找效率的提升就會非常明顯。直觀上，我們可以看到查找的效率提高了提高，下面讓我們來具體分析提高的效率。

假設鏈表的長度為n，那么第一級索引的節點個數為n/2，第二級為n/4,那么第k級索引的節點個數為n/(2^k)。我們知道，最高的索引有2個節點，則k=lgn-1。在我們查詢數據的時候，如果每一層需要查找m個節點，則在跳表中查詢一個數據的時間復雜度就是 O(m*logn)。

且m=3，則時間復雜度為O(lgn)。

原因如下：假設我們要查找的數據是 x，在第 k 級索引中，我們遍歷到 y 結點之后，發現 x 大于 y，小于后面的結點 z，所以我們通過 y 的 down 指針，從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中，y 和 z 之間只有 3 個結點(包含 y 和 z)，所以，我們在 K-1 級索引中最多只需要遍歷 3 個結點，依次類推，每一級索引都最多只需要遍歷 3 個結點。

我們可以看到，通過建立索引，我們實現了快速查找，代價了浪費了空間，空間復雜度為O(n)。其實在實際的軟件開發中，鏈表中存儲的是比較大的對象，但是索引中存儲的是id，所以相比較之下是可以忽略的。

下面我們來分析插入和刪除的時間復雜度，先給結論，也是O(lgn)。

我們還需要注意的是要及時更新索引,紅黑樹是通過左右旋來保持穩定的，而跳表是通過隨機函數來保存平衡性的。

hashmap

我們知道，數組可以在O(1)的時間復雜度內完成查詢，但是需要O(n)的時間復雜度完成插入和刪除，而鏈表正好相反，那么我們是否可以綜合利用數組和鏈表的優勢，這就是hashmap。

二叉查找樹

前面我們看到，hashmap是十分高效的，但是其問題也是比較明顯的。

Hashmap中的數據是無序存儲的，若要輸出有序數據，則需要先進行排序，而二叉查找樹直接中序遍歷即可；
Hashmap擴容耗時多；
Hashmap在hash沖突的時候耗時多；
Hashmap的構造復雜，需要考慮散列函數的設計、沖突解決辦法、擴容、縮容等問題，而二叉查找樹只需要考慮平衡性問題；

所以綜合以上的考量，在某些場景下，我們需要二叉查找樹，其查找的時間復雜度為O(logn)。

平衡二叉樹和紅黑樹

前面我們學到二叉查找樹在某些情況下可能會失衡，即退化為鏈表，時間復雜度降低為O(n),所以我們需要對二叉查找樹進行平衡。

最先被使用的是AVL平衡二叉查找樹，其首先符合二叉查找樹的概念，然后左右子樹的高度差不超過1。這樣就可以很好的保證查找的時間復雜度了。但是其缺點也是很明顯的，需要不斷的對整棵樹進行調整。

這個時候我們就引入了紅黑樹：左右子樹的高度差不超過1倍。紅黑樹的高度，是2logn。其查找，插入，刪除的時間復雜度都是O(logn)。

堆

我們再來看另外一種特殊的二叉樹：堆。

我們知道堆是一種完全二叉樹，往往采用數據里存儲。堆在很多地方都有應用，比如

優先級隊列:用在赫夫曼編碼、圖的最短路徑、最小生成樹算法
TOPK問題
求動態數據中的中位數

此外，堆在排序算法中的表現也是很好的，時間復雜度是O(logn),空間復雜度為O(1)，從這個角度來講，是要比快排和歸并排序都要優秀的，但是工程中更常見的排序算法依然是快排的，那這是為什么呢？主要從2個角度來考慮：

堆排序數據訪問的方式沒有快速排序友好。CPU的空間局部性原理。快排中，數據是順序訪問的，而堆中是跳著訪問的。
同樣的數據，堆排序的交換次數多余快排。

B樹和B+樹

這里要從mysql講起，使用mysql來查詢數據，我們比較關注的兩個點是等值查詢和范圍查詢，如：

select * from user where id=1234;
select * from user where id > 1234 and id < 2345

我們前面學到的數據結構中：

散列表：等值查詢時間復雜度為O(1)，但可能存在hash沖突的問題，且范圍查詢不支持；
二分查找樹：可能失衡
平衡二叉樹（AVL，紅黑樹）：范圍查詢仍然不方便，且樹的高度為logn；
跳表：插入、查找、刪除數據的時間復雜度都為logn,同時支持區間查詢，但是logn的時間復雜度仍然過高。且B+樹提出于1972年，跳表提出于1989年，所以B+樹才是爸爸。

綜上，我們必須要降低樹的高度，所以肯定是多叉樹。

B樹：

B+樹

我們來對比下B樹和B+樹：

B B+ 存儲結構每個節點存數據葉子節點存數據，非葉子節點存儲索引。所以可以存放更多的數據查找性能不穩定穩定，必須查找到葉子節點范圍查詢不支持支持

所以，mysql的索引選擇了B+樹。那么B+樹是怎么演化來的呢？

如果我們對二分查找樹進行改造，樹中的節點并不存儲數據本身，而是只是作為索引。除此之外，我們把每個葉子節點串在一條鏈表上，鏈表中的數據是從小到大有序的。

如果我們要為上億的數據建立索引，比如，我們給一億個數據構建二叉查找樹索引，那索引中會包含大約 1 億個節點，每個節點假設占用 16 個字節，那就需要大約 1GB 的內存空間。給一張表建立索引，我們需要 1GB 的內存空間。如果我們要給 10 張表建立索引，那對內存的需求是無法滿足的。如何解決這個索引占用太多內存的問題呢?

答案是把索引存放到硬盤中，但是如此一來，需要從硬盤中讀取數據，速度是無法忍受的，因為樹高是需要IO的次數，所以要降低樹高。答案是多叉樹。

那多叉樹的m到底是多少比較好呢？不管是內存中的數據，還是磁盤中的數據，操作系統都是按頁(一頁大小通常是 4KB，這個值可以通過 getconfig PAGE_SIZE 命令查看)來讀取的，一次會讀一頁的數據。如果要讀取的數據量超過一頁的大小，就會觸發多次 IO 操作。所以，我們在選擇 m 大小的時后，要盡量讓每個節點的大小等于一個頁的大小。讀取一個節點，只需要一次磁盤 IO 操作。