索引的由來
- 大資料時代誰掌握了資料就是掌握了流量，就是掌握的号召力。面對浩瀚的資料如何存儲并非難事， 難點在于如何在大資料面前查詢依舊快如閃電！
- 這時候索引就産生了，索引的産生主要還是借鑒于圖書管理者書簽的功能。在大資料面前 es 産生了，而我們今天要說的索引卻不是它 而是目前中小項目中廣泛使用的 mysql 資料庫中的索引。
- 本文主題着重介紹索引是什麼？索引如何存儲？為什麼這麼設計索引？常見的索引有哪些？最後我們在通過案列來分析如何命中索引以及索引失效的部分場景。
什麼是索引
索引是建立在表上的，對資料庫表中一列或多列的值進行排序的一種結構，可以提高查詢的速度。
- 索引是一種資料結構,以協助快速查詢,更新資料庫中的資料 。 mysql 的索引主要由 B+Tree 進行存儲。在存儲主題上又分為聚簇索引和非聚簇索引。
聚簇索引
- 聚簇索引從字面上了解就是聚集在一起。是以凡事索引和資料存放在一起的我們就叫做聚簇索引。在mysql 中 INNODB 的主鍵索引就是采用的聚簇索引，因為在葉子節點負責存放資料，而非葉子節點負責存放索引。而除了主鍵索引外其他索引則是非聚簇索引，因為其他索引的葉子節點存儲的是主鍵索引的位址指向。
非聚簇索引
- 在 MyISAM 引擎中就是非聚簇索引，我們通過它的檔案結構也能夠看出索引和資料是分開存放的。 非聚簇索引也會帶來一些問題。諸如回表
- 在 INNODB 中非主鍵索引就是非聚簇索引，同時這種非主鍵索引也會帶來一個問題就是二次索引也稱回表。因為我們通過非主鍵索引是無法定位到最終資料的。大部分情況下我們是需要在根據主鍵索引進行第二次查找的。加入你有一個索引idx_nameselect name from t where name=13 發生一次索引，不會回表查詢select * from t where name=13 發生兩次索引，會發生回表
- 上面第一個sql 不會發生回表是因為我門的sql 發生了索引覆寫，意思是idx_name 這顆樹已經覆寫了我們查詢的範圍。
索引存儲結構
- 先說結論 mysql 中索引是通過 B+ Tree 進行存儲的。但是在 mysql 中一開始是采取的 二叉樹存儲的。關于樹形存儲結構都是二叉樹。那麼我們是mysql 中不采用二叉樹、紅黑樹呢？下面我們來分析下采用二叉樹、紅叉樹分别會帶來哪些問題。
二叉樹
- 二叉樹是根據順序在根據大小判斷其存儲的左右節點的。這就導緻如果我們是按遞增ID作為索引的話，最終就導緻二叉樹變成一顆偏向一邊的樹，換個角度看其實就是連結清單。
- 而針對一張表我們往往就是ID作為索引的居多。而ID采用自增政策的居多，是以如果索引采用的是二叉樹的，毋庸置疑銷量基本無提升，這也是為什麼官方放棄 二叉樹 作為索引存儲的資料結構。
- 而二叉樹一共有如下幾種極端情況
平衡二叉樹
- 在開始紅黑樹之前，我們需要先了解下有種臨界狀态叫平衡二叉樹。
- 平衡二叉樹又叫做Self-balancing binary search tree 。 平衡二叉樹是二叉樹的一種特例
- 在二叉樹中有一個定義平衡度(平衡因子)的概念。他的公式是左右高度的絕對值。
- 當這個平衡度<=1的時候我們就稱之為平衡二叉樹
- 在平衡二叉樹中他的高度是最穩定的，換句話說平衡二叉樹和其他二叉樹相比能夠在相同的節點情況下保證樹的高度最低；這也是為什麼mysql中索引的結構是一種平衡二叉樹的更新版
紅黑樹
紅黑樹實際上是一顆平衡二叉樹；是以在建構的過程中他會發生自平衡
- 因為二叉樹在極端的情況會變成一個連結清單，針對連結清單的問題紅黑樹的自平衡特性就完美的規避了二叉樹的缺點。那麼為什麼最終索引也不是選擇紅黑樹呢？
- 仔細觀察能夠發現紅黑樹是一顆标準的二叉樹。他所能容納的最大節點數和他的高度正好成二的次方這個關系。也就是說假設紅黑樹的高度是h ，那麼他能容納最多的節點為 2^h。
- 這樣看來在資料量過大時，通過紅黑樹去建構貌似這顆二叉樹高度就過去龐大了。高度也高給我們查詢就帶來更多次互動。要知道每個節點都是存儲在硬碟中的，那麼每一次的通路都會帶來一次IO消耗。是以為了能夠提高查詢效率 mysql 最終還是沒有選擇紅黑樹。
①、每個節點要麼紅色要麼黑色
②、根節點是黑色的
③、葉子節點是黑色的
④、紅色節點的子節點一定是黑色的
⑤、從一個節點出發，到達任意一個葉子結點(NULL)路徑上一定具有相同的黑色節點（保證了平衡度<=2）
BTree
BTree的設計主要是針對磁盤擷取其他存儲的一種平衡樹(不一定是二叉這裡往往指的是多叉)
- B樹非常适合讀取和寫入相對較大的資料塊（如CD光牒）的存儲系統。它通常用于資料庫和檔案系統。
- 總結下BTree 具有如下特點：
①、至少是2階，即至少有兩個子節點 ②、對于m階BTree來說，非根節點所包含的關鍵詞個數j需要滿足 (m/2)-1<=j<=m-1 ③、除葉子結點外，節點内關鍵詞個數+1總是等于指針個數 ④、所有葉子結點都在同一層 ⑤、每個關鍵字儲存實際磁盤資料
B+Tree
B+Tree 是BTree的一種變體。BTree節點裡出了索引還會存儲指針資料，而B+Tree僅存儲索引值，這樣同樣空間節點能夠存儲更多的索引
- B+Tree 因為壓縮了資料存儲空間，這樣就能夠在相同高度的BTree上存儲更多的索引，這樣更加提高索引定位銷率。
Hash表
①、hash索引無法進行範圍查詢，因為上述的hash結構是沒有順序的，hash索引隻能實作等于、In等查詢 ②、hash值是針對中繼資料的一種散列運算。hash值得大小并不能反應中繼資料的大小。中繼資料a 、b對應的hash值有可能是3333、2222,而實際上上a<b . 是以我們無法通過hash值進行排序，進而hash索引無法進行排序 ③、對于組合索引來說，在B+Tree中我們有最左比對原則，但是在hash索引中是不支援的。因為組合索引整個映射成hash值，我們通過聯合索引中部分值進行hash運算得帶的值與hash索引中是沒有關系的 ④、hash索引在查詢時是需要周遊整個hash表的。這點我們Java中的HashMap一樣 ⑤、hash索引在資料量少的情況下比BTree快。但是當hash沖突比較多的時候定位就會比B+Tree慢很多了。
總結
- 現在看來資料庫運作的很牛逼，而且索引也很快，但這并不是一口吃成胖子的，了解了索引的底層資料結構後我們也能夠了解 mysql 也是一步一步嘗試過來的， 索引也是不斷的優化而成的。說不定以後還會有其他結構産生，隻能說每種資料結構都是最好的，前提是在特定的場景下。
- 本專欄最後一篇我們将介紹下 mysql 的索引如何命中，以及那些場景導緻索引失效。然後再着重介紹下高頻面試題--回表&&索引下推
來源：https://juejin.cn/post/7168268214713974798