前言
寫資料庫，我第一時間就想到了MySQL、Oracle、索引、存儲過程、查詢優化等等。
不知道大家是不是跟我想得一樣，我最想寫的是索引，為啥呢？
以下這個面試場景，不知道大家熟悉不熟悉：
面試官：資料庫有幾千萬的資料，查詢又很慢我們怎麼辦？
面試者：加索引。
面試官：那索引有哪些資料類型？索引是怎麼樣的一種結構？哪些字段又适合索引呢？B+的優點？聚合索引和非聚合索引的差別？為什麼說索引會降低插入、删除、修改等維護任務的速度？……..
面試者：面試官怎麼出我們公司門來着。
是的大家可能都知道慢了加索引，那為啥加，在什麼字段上加，以及索引的資料結構特點，優點啥的都比較模糊或者甚至不知道。
那我們也不多BB了，直接開始這次的面試吧。
正文
我看你履歷上寫到了熟悉MySQL資料庫以及索引的相關知識，我們就從索引開始，索引有哪些資料結構？
Hash、B+
大家去設計索引的時候，會發現索引類型是可以選擇的。
為什麼哈希表、完全平衡二叉樹、B樹、B+樹都可以優化查詢，為何Mysql獨獨喜歡B+樹？
我先聊一下Hash：
大家可以先看一下下面的動圖
注意字段值所對應的數組下标是雜湊演算法随機算出來的，是以可能出現哈希沖突。
那麼對于這樣一個索引結構，現在來執行下面的sql語句：
select * from sanguo where name='雞蛋'
可以直接對‘雞蛋’按雜湊演算法算出來一個數組下标，然後可以直接從資料中取出資料并拿到所對應那一行資料的位址，進而查詢那一行資料， 那麼如果現在執行下面的sql語句：
select * from sanguo where name>'雞蛋'
則無能為力，因為哈希表的特點就是可以快速的精确查詢，但是不支援範圍查詢。
如果做成了索引，那速度也是很慢的，要全部掃描。
問個題外話，那Hash表在哪些場景比較适合？
等值查詢的場景，就隻有KV（Key，Value）的情況，例如Redis、Memcached等這些NoSQL的中間件。
你說的是無序的Hash表，那有沒有有序的資料結構？
有序數組，它就比較優秀了呀，它在等值查詢的和範圍查詢的時候都很Nice。
那它完全沒有缺點麼？
不是的，有序的适合靜态資料，因為如果我們新增、删除、修改資料的時候就會改變他的結構。
比如你新增一個，那在你新增的位置後面所有的節點都會後移，成本很高。
那照你這麼說他根本就不優秀啊，特點也沒地方放。
此言差矣，可以用來做靜态存儲引擎啊，用來儲存靜态資料，例如你2019年的支付寶賬單，2019年的淘寶購物記錄等等都是很合适的，都是不會變動的曆史資料。
有點東西啊小夥子，那二叉樹呢？
二叉樹的新增和結構如圖：
二叉樹的結構我就不在這裡多BB了，不了解的朋友可以去看看資料結構章節。
二叉樹是有序的，是以是支援範圍查詢的。
但是他的時間複雜度是O(log(N))，為了維持這個時間複雜度，更新的時間複雜度也得是O(log(N))，那就得保持這棵樹是完全平衡二叉樹了。
怎麼聽你一說，平衡二叉樹用來做索引還不錯呢？
此言差矣，索引也不隻是在記憶體裡面存儲的，還是要落盤持久化的，可以看到圖中才這麼一點資料，如果資料多了，樹高會很高，查詢的成本就會随着樹高的增加而增加。
為了節約成本很多公司的磁盤還是采用的機械硬碟，這樣一次千萬級别的查詢差不多就要10秒了，這誰頂得住啊？
如果用B樹呢？
同理來看看B樹的結構：
可以發現同樣的元素，B樹的表示要比完全平衡二叉樹要“矮”，原因在于B樹中的一個節點可以存儲多個元素。
B樹其實就已經是一個不錯的資料結構，用來做索引效果還是不錯的。
那為啥沒用B樹，而用了B+樹？
一樣先看一下B加的結構：
我們可以發現同樣的元素，B+樹的表示要比B樹要“胖”，原因在于B+樹中的非葉子節點會備援一份在葉子節點中，并且葉子節點之間用指針相連。
那麼B+樹到底有什麼優勢呢？
其實很簡單，我們看一下上面的資料結構，最開始的Hash不支援範圍查詢，二叉樹樹高很高，隻有B樹跟B+有的一比。
B樹一個節點可以存儲多個元素，相對于完全平衡二叉樹整體的樹高降低了，磁盤IO效率提高了。
而B+樹是B樹的更新版，隻是把非葉子節點備援一下，這麼做的好處是為了提高範圍查找的效率。
提高了的原因也無非是會有指針指向下一個節點的葉子節點。
小結：到這裡可以總結出來，Mysql選用B+樹這種資料結構作為索引，可以提高查詢索引時的磁盤IO效率，并且可以提高範圍查詢的效率，并且B+樹裡的元素也是有序的。
那麼，一個B+樹的節點中到底存多少個元素最合适你有了解過麼？
額這個這個？卧*有點懵逼呀。
過了一會還是沒想出，隻能老實交代：這個不是很了解咳咳。
你可以換個角度來思考B+樹中一個節點到底多大合适？
B+樹中一個節點為一頁或頁的倍數最為合适。
為啥？
因為如果一個節點的大小小于1頁，那麼讀取這個節點的時候其實也會讀出1頁，造成資源的浪費。
如果一個節點的大小大于1頁，比如1.2頁，那麼讀取這個節點的時候會讀出2頁，也會造成資源的浪費。
是以為了不造成浪費，是以最後把一個節點的大小控制在1頁、2頁、3頁、4頁等倍數頁大小最為合适。
你提到了頁的概念，能跟我簡單說一下麼？
首先Mysql的基本存儲結構是頁(記錄都存在頁裡邊)：
- 各個資料頁可以組成一個雙向連結清單
- 而每個資料頁中的記錄又可以組成一個單向連結清單
- - 每個資料頁都會為存儲在它裡邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然後再周遊該槽對應分組中的記錄即可快速找到指定的記錄
- 以其他列(非主鍵)作為搜尋條件：隻能從最小記錄開始依次周遊單連結清單中的每條記錄。
是以說，如果我們寫 select * from user where username='丙丙'這樣沒有進行任何優化的sql語句，預設會這樣做：
- 定位到記錄所在的頁
- - 需要周遊雙向連結清單，找到所在的頁
- 從所在的頁内中查找相應的記錄
- - 由于不是根據主鍵查詢，隻能周遊所在頁的單連結清單了
很明顯，在資料量很大的情況下這樣查找會很慢！看起來跟回表有點點像。
哦？回表你聊一下。
卧槽，該死，我嘴幹嘛。
回表大概就是我們有個主鍵為ID的索引，和一個普通name字段的索引，我們在普通字段上搜尋：
sql select * from table where name = '丙丙'
執行的流程是先查詢到name索引上的“丙丙”，然後找到他的id是2，最後去主鍵索引，找到id為2對應的值。
回到主鍵索引樹搜尋的過程，就是回表。不過也有方法避免回表，那就是覆寫索引。
哦？那你再跟我聊一下覆寫索引呗？
！！！我這個嘴。。。
這個其實比較好了解，剛才我們是 select * ，查詢所有的，我們如果隻查詢ID那，其實在Name字段的索引上就已經有了，那就不需要回表了。
覆寫索引可以減少樹的搜尋次數，提升性能，他也是我們在實際開發過程中經常用來優化查詢效率的手段。
很多聯合索引的建立，就是為了支援覆寫索引，特定的業務能極大的提升效率。
索引的最左比對原則知道麼？
最左比對原則：
- 索引可以簡單如一個列 (a)，也可以複雜如多個列 (a,b,c,d)，即聯合索引。
- 如果是聯合索引，那麼key也由多個列組成，同時，索引隻能用于查找key是否存在（相等），遇到範圍查詢 (>、<、between、like左比對)等就不能進一步比對了，後續退化為線性查找。
- 是以，列的排列順序決定了可命中索引的列數。
例子：
- 如有索引 (a,b,c,d)，查詢條件 a=1 and b=2 and c>3 and d=4，則會在每個節點依次命中a、b、c，無法命中d。(c已經是範圍查詢了，d肯定是排不了序了)
總結
索引在資料庫中是一個非常重要的知識點！
上面談的其實就是索引最基本的東西，N叉樹，跳表、LSM我都沒講，同時要建立出好的索引要顧及到很多的方面：
- 最左字首比對原則。這是非常重要、非常重要、非常重要（重要的事情說三遍）的原則，MySQL會一直向右比對直到遇到範圍查詢 （>,<,BETWEEN,LIKE）就停止比對。
- 盡量選擇區分度高的列作為索引，區分度的公式是 COUNT(DISTINCT col)/COUNT(*)。表示字段不重複的比率，比率越大我們掃描的記錄數就越少。
- 索引列不能參與計算，盡量保持列“幹淨”。比如， FROM_UNIXTIME(create_time)='2016-06-06' 就不能使用索引，原因很簡單，B+樹中存儲的都是資料表中的字段值，但是進行檢索時，需要把所有元素都應用函數才能比較，顯然這樣的代價太大。是以語句要寫成 ：create_time=UNIX_TIMESTAMP('2016-06-06')。
- 盡可能的擴充索引，不要建立立索引。比如表中已經有了a的索引，現在要加（a,b）的索引，那麼隻需要修改原來的索引即可。
- 單個多列組合索引和多個單列索引的檢索查詢效果不同，因為在執行SQL時，MySQL隻能使用一個索引，會從多個單列索引中選擇一個限制最為嚴格的索引(經指正，在MySQL5.0以後的版本中，有“合并索引”的政策，翻看了《高性能MySQL 第三版》，書作者認為：還是應該建立起比較好的索引，而不應該依賴于“合并索引”這麼一個政策)。
- “合并索引”政策簡單來講，就是使用多個單列索引，然後将這些結果用“union或者and”來合并起來