前言
在今天的網際網路企業中，mysql是必須掌握的技能，可能維護mysql的技能都已經交給dba或者直接采用相關雲服務，但是了解其中的原理還是很重要的。例如mysql中的存儲引擎、事務管理、binlog日志、主從同步等等，這篇文章主要記錄下對mysql的b+樹的學習總結，如果對此概念已經比較了解，就可以不用在閱讀了。
目錄
- 前言
- 索引的資料結構
-
-
- hash
- b+樹
-
- b+樹原理
-
- 什麼是二叉樹？
- 什麼是b樹？
- b+樹
- mysql表設定自增長id的作用
-
- 總結
- 參考
索引的資料結構
mysql的InnoDB常用的索引資料結構有2種，hash和b+樹。
hash
hash就是建立hash表，根據hash算法，建立索引鍵和資料的映射關系，hash可能會出現沖突，解決hash沖突有幾種方式：
- 開放定址法： 一旦出現沖突就向後查找空位，直到找到空位為止
- 再hash法： 采用多個hash函數，hash出現沖突，繼續下一次hash
- 連結清單法： 出現沖突時，通過連結清單實作共同進入該位
-
公共溢出區： 出現沖突時，都進入公共溢出區
InnoDB中采用的hash結構是第3種。
優點
- hash算法時間複雜度低，對于等值查找效率很高（但是要求查找值重複度低，如果重複度高，進傳入連結表查詢還是需要周遊）
缺點
- 範圍查找不适用
- 無法用來做資料排序，由于hash後的資料排序可能跟原有資料排序不一緻
- 組合索引，部分索引無法實作查詢，組合索引采用多鍵計算hash，但是如果隻用前面幾個索引查詢，就無法使用
我們發現hash索引的局限性太強，很多場景無法适用，這也是我們實際使用中幾乎沒人使用該索引資料結構的原因。
b+樹
我們在設計mysql資料庫的表時，都會預設加個業務無關的自增長主鍵id，至于為啥這樣可能很多人不了解，等會我們來解釋。
b+樹原理
什麼是二叉樹？
二叉搜尋樹有個特性，就是left-child小于都小于自己，right-child都大于自己，那麼我們看下面這個樹，右側的樹雖然也滿足，但是其查找性能已經不是2分法而是線性，這種情況我們稱之為失去了”平衡“。
什麼是b樹？
b樹解決了二叉樹不能平衡的問題，在b樹中所有的葉子節點在同一層，有以下幾個特性：
- 定義任意非葉子結點最多隻有M個兒子；且M>2
- 根結點的兒子數為[2, M]；
- 除根結點以外的非葉子結點的兒子數為[M/2, M]；
- 每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；
- 非葉子結點的關鍵字個數=指向兒子的指針個數-1；
- 非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
- 非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
- 所有葉子結點位于同一層；
b樹如何實作平衡
由于M/2的限制，在插入結點時，如果結點已滿，需要将結點分裂為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟結點合并；
邏輯結構
特點
資料分布在所有節點中，在查找的時候一旦比對到，就可以拿到資料。其查找的時間複雜度為： O(logN)
b+樹
b+樹是b樹的變型，相比于b樹其有以下幾個不同：
- 非葉子結點的子樹指針與關鍵字個數相同
- 為所有葉子結點增加一個鍊指針
- 所有關鍵字都在葉子結點出現
相比于b樹其優點
- 非葉子節點的資訊更加少，減少io開銷
- 所有資料都在葉子節點，查找性能穩定
- 葉子節點之間有連結清單指針關聯，更加利于周遊
鑒于以上的優勢，b+樹更适合做檔案索引，這也是InnoDB采用的原因。
mysql表設定自增長id的作用
回到我們提出的問題，InnoDB的主鍵索引采用b+樹，其非葉子節點中存儲的是主鍵id，其葉子節點存儲的是具體的行資料，這是聚簇索引，也就是主鍵索引。
非主鍵索引中差別在于，其葉子節點存儲的不是實際的資料，而是主鍵的值。
那麼如果不按照主鍵查找呢？
按照其他索引查找資料，其他索引的葉子節點并沒有資料，其隻有資料的主鍵，在查找到資料主鍵的時候，再去通過主鍵索引查找資料的資料傳回。
為啥主鍵索引是自增長id呢？
在聚簇索引寫入的時候，葉子節點時是通過通過連結清單關聯的、且有序，順序的主鍵會使磁盤寫入變成順序的，效率更高。 批量讀取資料的時候效率也更高。
試想一下，如果id是非自增長的，那麼每次無論是非葉子節點中插入資料會變成随機的而不是順序的，效率自然變低。
總結
今天先說到這裡，有錯誤的地方望指出，後續有空繼續輸出mysql其他方面的學習總結。
參考
b樹資料結構解釋