面試時，交流有關mysql索引問題時，發現有些人能夠濤濤不絕的說出B+樹和B樹，平衡二叉樹的差別，卻說不出B+樹和hash索引的差別。這種一看就知道是死記硬背，沒有了解索引的本質。本文旨在剖析這背後的原理，歡迎留言探讨
摘要
問題
如果對以下問題感到困惑或一知半解，請繼續看下去，相信本文一定會對你有幫助
- mysql 索引如何實作
- mysql 索引結構B+樹與hash有何差別。分别适用于什麼場景
- 資料庫的索引還能有其他實作嗎
- redis跳表是如何實作的
- 跳表和B+樹，LSM樹有和差別呢
解析
首先為什麼要把mysql索引和redis跳表放在一起讨論呢，因為他們解決的都是同一種問題，用于解決資料集合的查找問題，即根據指定的key，快速查到它所在的位置（或者對應的value）
當你站在這個角度去思考問題時，還會不知道B+樹索引和hash索引的差別嗎
資料集合的查找問題
現在我們将問題領域邊界劃厘清楚了，就是為了解決資料集合的查找問題。這一塊需要考慮哪些問題呢
- 需要支援哪些查找方式，單key/多key/範圍查找，
- 插入/删除效率
- 查找效率（即時間複雜度）
- 存儲大小（空間複雜度）
我們看下幾種常用的查找結構
hash
hash是key,value形式，通過一個散列函數，能夠根據key快速找到value
B+樹
B+樹是在平衡二叉樹基礎上演變過來，為什麼我們在算法課上沒學到B+樹和跳表這種結構呢。因為他們都是從工程實踐中得到，在理論的基礎上進行了妥協。
B+樹首先是有序結構，為了不至于樹的高度太高，影響查找效率，在葉子節點上存儲的不是單個資料，而是一頁資料，提高了查找效率，而為了更好的支援範圍查詢，B+樹在葉子節點備援了非葉子節點資料，為了支援翻頁，葉子節點之間通過指針連接配接。
跳表
跳表是在連結清單的基礎上進行擴充的，為的是實作redis的sorted set資料結構。 level0: 是存儲原始資料的，是一個有序連結清單，每個節點都在鍊上 level0+: 通過指針串聯起節點，是原始資料的一個子集，level等級越高，串聯的資料越少，這樣可以顯著提高查找效率，
總結
| 資料結構 | 實作原理 | key查詢方式 | 查找效率 | 存儲大小 | 插入、删除效率 |
|---|---|---|---|---|---|
| Hash | 哈希表 | 支援單key | 接近O(1) | 小，除了資料沒有額外的存儲 | O(1) |
| 平衡二叉樹擴充而來 | 單key,範圍，分頁 | O(Log(n) | 除了資料，還多了左右指針，以及葉子節點指針 | O(Log(n)，需要調整樹的結構，算法比較複雜 | |
| 有序連結清單擴充而來 | 單key，分頁 | 除了資料，還多了指針，但是每個節點的指針小于<2,是以比B+樹占用空間小 | O(Log(n)，隻用處理連結清單，算法比較簡單 |
對LSM結構感興趣的可以看下cassandra vs mongo (1)存儲引擎
有用點個贊，謝謝
參考
https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7545940.html