MySQL索引原理詳解
索引是什麼
索引是幫助MySQL高效獲取數據的排好序的數據結構
最重要的點是有序的，我們用索引就是為瞭快速的查找數據，如果一堆數據是無序的，程序隻能挨個遍歷每個元素，對比值，才能找到某個元素，最壞的情況要比對N次， N 是這一堆數據的長度。如果數據是有序的，我們就可以使用二分查找算法，他的時間復雜度是 O(long N)，效率比直接挨個查找快的多。
二分查找算法關鍵步驟就是找到區間的中間值，然後確定要查找的值落在左區間還是右區間，一直重復這個步驟直到找到該值。於是就可以將這種查詢方法映射成一種數據結構——樹。我們規定一種樹，有左節點，右節點，和當前節點。並且左節點 < 當前節點 < 右節點 .
如下圖所示:
由於樹具有方便快速查找的特性，我們一般都會使用樹結構去存儲索引，並對簡單的查找二叉樹做瞭很多優化，比如 紅黑樹，平衡二叉樹， B 樹 B+樹
樹的構建，刪除， 查找都有一定的算法，這裡不詳細描述，隻需知道樹有一個通用的特性：樹的高度越低，查找效率越高
所以索引的構建 ， 本質上是控制樹的高度
索引數據結構
二叉樹：
- 紅黑樹
- Hash 表
- B Tree
樹形索引
表中的數據與索引結構映射關系可以理解如下圖:
加入要找到 col2 = 23 的記錄，如果不使用索引，我們需要對整張表掃描，從 34 -> 77 -> 5 -> 91 -> 22 -> 89 -> 23, 需要對比7次才能找到
使用索引時， 查找路徑時是 34 -> 22 -> 23 隻需對比3次就行。在表中數據量極大時，差別更明顯
樹的動畫
推薦一個在線工具，它以動畫的形式描述瞭每種樹的構建與查找方法
為什麼不是簡單的二叉樹？
我們知道MySQL索引采用的是 B+樹，那麼為什麼不是其他的樹呢？
因為在順序插入下，樹的高度會一直增加，等同於鏈表。無法控制樹的高度，如下圖:
如果需要查找6，仍然需要查找6次
為什麼不是紅黑樹？
紅黑樹（平衡二叉樹）： 雖然會自動平衡節點位置，但仍然高度不可控。表比較大時會導致樹的高度很高。增加查找次數
為什麼最終選擇B+樹 而不是B樹
要解決這個疑問，我們需要知道這兩種樹的構造，如下圖：
B Tree:
B + Tree:
水平方向可以存放更多的索引key
B+樹將數據全部放到葉子節點，留下更多的空間放 key, key 越多，寬度越寬，同樣的數據量，寬度越大，高度越小。查找次數就越小。
為什麼需要 擴展樹的寬度而不是樹的深度呢？
如果按照上面的說法，我們拓寬瞭樹的寬度，減少瞭樹的高度，但是比較次數並沒有發生改變，隻不過是減少瞭縱向的比較，增加瞭橫向的比較
這個疑問的前提是所有的數據都在內存中，直接在內存中進行比較大小。 但是事實並非如此，不可能把表中的所有數據都加到內存中，必須先從磁盤中加在一部分數據到內存，然後在內存中比較大小，內存中運算的速度遠遠大於從磁盤加載數據的速度。磁盤加載數據是機械運動，需要電機帶動磁針轉圈掃描磁道。內存運算則是電子運動，不可同日而語。
數據從磁盤加載到內存中，是有最小單位的，這個單位是 頁， 不是 字節或者 位， 頁是固定字節數據，由操作系統決定，這樣可以減少加載磁盤的次數。
由於B Tree 的每一層都已經是有序的，我們把樹中水平方向的數據放在磁盤相鄰的地方，每次從磁盤加載一頁數據時，便可以得到部分或全部的水平方向的結點，不用再次排序。
在水平方向在內存中使用二分查找的效率遠遠大於從磁盤中加載一頁數據， 所以我們希望樹越寬越好,這樣一次性加載的數據就越多，而不是越高越好
對於B+ 樹，我們假設要查找50這個數據，先從根節點即(15 56 77) 這些數據中找到50所處的范圍，因為 (15 56 77) 已經是有序的，可以根據二分查找算法找到 50 處於 15–56之間， 然後加載 15 所指向的下一頁數據 （15 20 49）,再次根據二分查找算法，找到50處於 49之後，再從磁盤加載49所指向的數據頁，找到50
數據量估算
MySQL 自己也有一個邏輯 頁，一般是操作系統中 頁 的整數倍，這個邏輯頁的數據可以通過配置修改，但是不建議，MySQL 是經過大量的測試，為我們定義瞭一個合理的默認值 16Kb
可以通過下面語句查詢：
show global status like 'Innodb_page_size'
假設上圖中表示的是主鍵索引，類型是 bigint, 占 8 個字節。指向下一頁的指針占 6 個字節， 那麼這一頁可以存放 16 * 1024 / (8 + 6) = 1170 個key, 同理第二頁即 （15 20 49 ….） 也可以放 1170 個key , 對於第三頁，也就是葉子節點，包含瞭主鍵和對應整行的數據。就按照一行數據放1KB 吧(已經比較大瞭) 能放 16 行，那麼隻有一頁根節點的話， 這個索引索引樹能放 1170 * 1170 * 16 =21,902,400 行數據。 這棵樹的高度隻有3，就已經能支持上千萬的數據量瞭。也就是隻需加載3次磁盤就可以查找到數據瞭。並且MySQL 存放根節點的頁還有優化，可能會把這個頁常駐內存。
葉子節點包含所有的索引字段
如上圖所示，在主鍵索引中，葉子節點包含瞭表中的所有字段，對於一些全表掃描的查詢來說，直接掃描葉子節點便可以得到數據，不用再從索引樹上挨個查找
葉子節點直接包含雙向指針,范圍查找效率高
對於一些范圍查詢比如 id > 20 and id < 50, 在索引樹上定位到 20 之後直接使用右向指針定位到下一個比20大的數據，依次往下，直到 50，便可以檢出該區間的數據，如果沒有這個指針，（B Tree）則需要再次回到索引樹中去查找 , 極大的提高瞭范圍查找的性能
Hash 索引
hash 索引原理如下：
更快
大多情況下 Hash 索引比B+ Tree 索引更快，Hash 計算的效率非常高，且僅需一次查找就可以定位到數據(無hash沖突的情況)
不支持范圍查詢
圖中有些歧義，Hash 後的值是沒有順序的，也不是整數，所以無法進行高效的范圍查詢查詢
hash 沖突問題
如果在某列上有很多相同的行，比如 name 字段，叫 張三的人非常多。會產生很多次hash沖突，隻能退化成列表搜索瞭
表引擎
我們常說的 MyISAM 引擎 或者 InnoDB 引擎是基於表的，是表的一個屬性， 可不是基於數據庫的， 同一個數據庫中可以有不同引擎的表
MyISAM 和 InnoDB 引擎
不同引擎的表在磁盤中產生的文件也不一樣，數據庫文件位置默認在安裝目錄/data 下
MyISAM 引擎
- frm: 表結構相關, frame（框架） 縮寫`
- MYD: MyISAM Data 表數據
- MYI: MyISAM Index 表索引
索引結構中的葉子節點的 data 存放的是 數據行的位置，及這一行在 MYD 文件的位置， 而不是直接放的真實數據
InnoDB
- frm 表結構信息
- ibd 表數據加索引
表數據組織形式
表結構本身就是按照 B+ Tree 結構存儲， 葉子節點放的是出索引列其他列的數據
聚集與非聚集索引
聚集索引 (InnoDB 主鍵索引)
葉子節點直接包含整行數據
非聚集索引 (MyISAM 索引, InnoDB 非主鍵索引)
葉子節點不包含整行數據,包含的是對應行所在的位置，或者主鍵Id
單從索引結構的來看，聚集索引的查找速度高於非聚集索引
InnoDB 隻有一個聚集索引，默認是主鍵索引， 非主鍵索引的葉子節點存放的是主鍵的值，如下圖：
這樣做的目的有兩個：
- 節約空間，避免將整行的數據存放多份
- 保證數據的一致性，否則每增加一行，對應的每個索引都要維護一份行數據。必須要等到每個索引都更新完，數據才能插入成功
★★★ 為什麼建議InnoDB 表必須有主鍵，並且是整型自增的？
InnoDB 整個表的數據就是用B+ 樹組織的，如果存在主鍵，就用主鍵為索引，葉子節點存儲行數據
如果沒有主鍵，InnoDB 就會找到一個每行數據都不相同的列作為索引來組織整個表的數據
如果沒有找到這種列，就會建一個隱藏的列，自動維護值，用這個隱藏的列來組織數據，所以我們要主動做這種工作減少數據庫的負擔
為什麼是整型
因為在查找數據的過程中，需要多次比較大小，整型的比較運算速度大於字符串， 並且占用空間小
為什麼是自增
這一點涉及到B+ 樹的構建，我們知道索引一個最重要的特性就是排好序 的。如果我們不是順序插入的，那麼樹就要自己額外做排序，調整樹結構，浪費瞭性能
- 避免葉子節點的分裂
- 避免B+ 樹做平衡調整
聯合索引
聯合索引和單索引差不多，隻不過是先按第一個字段排序，再按第二個字段排序，然後再按第三個字段排序。
這種排序規則表明瞭隻有在第一個字段相等的情況下，第二字段才是有序的。第二字段相等的情況下，第三個字段才是有序的。
所以 name = 'Bill' and age = 20 and position = 'dev' 可以用到全部索引， 因為 name 確定瞭，age 是有序的，age 可以走索引， age 確定後 position 可以走索引。這個聯合索引可以全部用到
如果是 name = 'Bill and age > 30 and position = 'dev'' , 首先name 可以走索引，name 確定後 age 是有序的，age 也可以走索引，但是 age > 30 導致 age 查出來的數據有多個（31 32）, 31 和 32 下的 position (dev admin ) 不是有序的，便無法利用二分算法進行查找。所以無法利用 position 這個索引，這也就是左前綴法則的原理和聯合索引失效的原理
到此這篇關於MySQL索引原理詳解的文章就介紹到這瞭,更多相關MySQL索引內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！