MySQL索引數據結構

下面列舉了常見的數據結構

• 二叉樹
• 紅黑樹
• Hash表
• B-Tree（B樹）

Select * from t where t.col=5

我們在執行一條查詢的Sql語句時候，在數據量比較大又不加索引的情況下，逐行查詢并進行比對，每次需要從磁盤上查找，每行數據可能在磁盤不同的位置，數據比較靠后的話，一千萬數據可能要比對幾百萬，很耗費資源。

Mysql衡量查詢效率的就是磁盤IO次數，那么Mysql中應該采用什么樣的數據結構存儲數據呢，以及為什么要使用那個數據結構呢。

二叉樹

大多數人都知道，如果加上索引之后。把數據放在二叉樹里面，查詢會快很多，但是還有一種特殊的情況：

把一個遞增列的索引放入二叉樹中，列id作為等于5查詢目標，就會從col為1開始搜索，**這樣要搜索幾次？**二叉樹插入的數據如果大于本身，會放在父節點的右下角，小的會放在父節點的左下角，因此形成了這樣像鏈表一樣的結構，其實本質還是二叉樹。

需要從根節點遍歷，經過5次的查找，每個節點都存儲在磁盤上，每查一個節點需要跟磁盤做一次IO交互，效率相比之前沒加索引也沒有太大提升,這顯然不是Mysql的索引結構。

紅黑樹

HasMap的數據結構就是紅黑樹，原來是數組加鏈表，現在優化到了數組加紅黑樹。

紅黑樹本質還是二叉樹，還有一個名字又叫平衡二叉樹。當一邊子節點比另一邊高太多的時候，會自動旋轉平衡。當數據量比較大的時候比如1000萬，紅黑樹存儲的高度就可能達到幾十。如果數據量越大樹的高度就會越高。每查一個節點要進行一次磁盤IO交互。樹的高的越高查找效率越低，很顯然紅黑樹也不是Mysql的數據結構，早期版本Mysql有用到紅黑樹，現在版本沒有用到紅黑樹。那么能不能對紅黑樹做點改造。

B-Tree

樹的高的越高查找效率越低，那么將樹高縮小，比如限制在5層，把一層存放更多元素。把一個節點的數據在磁盤同一個區域全部查出來放到內存，只做一次IO查找，就可以查到很多索引信息。B樹又叫平衡多叉樹。

索引值和具體data都在每個節點里，而節點的位置不固定，最好的情況查找值就在第一層。

B樹的特點就是每層節點數目非常多，層數很少，目的就是為了減少磁盤IO次數，B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題，由于節點內部每個 key 都帶著 data 域，每次查找到具體節點還要和data進行順序比對，如果查找某個范圍內數據，又需要重新遍歷。正是為了解決這個問題，B+樹應運而生

B樹遍歷全部數據：

B+Tree

B+樹節點只存儲 key 的副本，真實的 key 和 data 域都在葉子節點存儲，數據全部存儲在葉子節，并且每一個節點之間用指針串聯起來，形成鏈表，方便遍歷，可以跨區間訪問，這優點尤其突出在范圍查詢，不需要在一次從根節點到子節點遍歷。

B+樹遍歷全部數據：

數據量大的情況下哪個更快，我想你應該知道了吧！