Mysql索引學習筆記 - tw511教學網

https://www.jianshu.com/p/ace3cd6526c4
推薦up主https://space.bilibili.com/377905911

系列文章目錄和關於我

一丶什麼是索引

索引是儲存引擎快速找到記錄的一種資料結構。資料庫中的資料可以理解成字典中的單詞，而索引就是目錄，顯而易見這是一種空間換時間的做法，目錄佔用了空間，但是加快了我們找到單詞的速度，正如索引需要空間儲存，但是利用索引我們可以快速的找到想要的資料。

InnoDB儲存引擎存在幾種常見的索引：

B+樹索引
全文索引
雜湊索引

本文主要討論B+樹索引

二丶索引的資料結構

可以加快查詢速度的資料結構很多，為什麼mysql使用B+樹來實現暱，換句話說雜湊表，有序陣列，跳錶，平衡二元搜尋樹，B-樹等都可以優化搜尋效率，為什麼偏偏使用B+樹

1.雜湊表

雜湊表，可以聯想Java中的HashMap，在HashMap原始碼學習中，我們瞭解到Hash表的資料結構。如下圖

雜湊表通過hash演演算法將key對映到陣列對應的下表進行儲存，不可避免的會產生hash衝突（多個不同的key雜湊到相同的陣列下標中），解決hash衝突常用拉鍊法，顧名思義，就是把相同hash值的節點組成連結串列。在根據key查詢value的過程中，只需要再次使用相同的hash演演算法那麼就能拿到對應的陣列下表，然後遍歷連結串列找到目標值即可,查詢的效率是o(1)。

明明存在連結串列需要遍歷為什麼說時間複雜度o(1)
首先hash演演算法計算是常數時間，
hash表會在需要的時候進行擴容，
維持連結串列長度儘量在一個常數範圍，從而保證遍歷常數個連結串列節點

mysql中存在自適應雜湊索引，由innodb儲存引擎自己控制，利用查詢O(1)的性質優化等值查詢。我們可以看出，hash表並不適合範圍查詢，對於Id<10這種範圍查詢只能遍歷hash表中每一個資料，相當於要進行一次全表掃描。我還有一個想法：從擴容的角度看，每次擴大陣列大小後都需要移動一些陣列到新的陣列空間中，這部分的複製移動的開銷也許是hash表不合適的原因（redis為了解決這個問題，使用漸進式hash的方式，在擴容的時候生成更大的陣列，但是不是一次移動所以資料，而是把新資料的插入都是方法新陣列，老陣列使用到的資料才會移動到新陣列）

2.有序陣列

有序陣列就是資料中元素有序，正因為有序，索引其在返回查詢上非常優秀，正因為要維持有序，在更改資料的時候，也許需要移動大量陣列（比如插入一個較小的值，大於此值的資料都需要後移動），所以有序資料只適用於靜態資料（比如2020年人口資訊，這種不會改變的資料）

3.跳錶

為了解決有序陣列需要移動元素的問題，我們可以使用連結串列來維護陣列，從而使更改陣列效率為o(1)，但是連結串列的查詢非常慢，但是連結串列整體式有序的，那麼我們可以使用二分法優化查詢效率，如上我們建立多級的節點，在查詢的時候我們首先通過多級的所有依次找到最下層。對於範圍查詢，由於底層資料是有序的，查詢id<7的陣列，首先我們找到id=7然後向左遍歷集合（可以把跳錶最下面一層優化為雙向連結串列，從而讓範圍查詢速度也很快）

哪為什麼不使用跳錶來做索引暱？其實我覺得完全可以使用跳錶，可能是由於跳錶在插入資料維護索引比較隨機，比如上面的跳錶插入資料6

理論上為了達到二分的效果，每一層的結點數需要是下一層結點數的二分之一。也就是說現在有一個新的資料插入了，它有50%的概率需要在第二層加入索引，有25%的概率需要在第三層加個索引，以此類推，直到最頂層。

4.平衡二元搜尋樹

二元搜尋樹，即左子樹小於根，根小於右子樹，這種結構在查詢的時候可以進行二分，根據根節點的值就可以確定期望的資料在左樹還是右樹。

但是二元搜尋樹在插入，刪除節點的時候可能出現樹極度不平衡的情況，出現樹退化成連結串列。

這個時候就需要維持樹的平衡——AVL:在滿足二元搜尋樹的條件下，要求任何節點的兩個子樹高度差不超過1。平衡二元樹的查詢是趨近於O(log(N))，但是需要維護一顆樹為AVL需要進行左旋，右旋的操作，更新的時間複雜度也是 O(log(N))。

為什麼不使用AVL做索引：節點儲存的資料內容太少。因為作業系統和磁碟之間一次資料交換是以頁為單位的，一頁 = 4K，即每次IO作業系統會將4K資料載入進記憶體。但是，在二元樹每個節點的結構只儲存一個關鍵字，一個資料區，兩個子節點的參照，並不能夠填滿4K的內容。倖幸苦苦做了一次的IO操作，卻只載入了一個關鍵字，在樹的高度很高，恰好又搜尋的關鍵字位於葉子節點或者支節點的時候，取一個關鍵字要做很多次的IO。

5.B-樹，B+樹

B-樹就是B樹，英文是B-Tree，所以國內有許多人稱之為B-樹。B樹和B+樹是多路平衡查詢樹，之所以多路，是為了契合磁碟的io操作——作業系統和磁碟之間一次資料交換是以頁為單位的，多路能讓讀取一頁能獲取更多的資料，讓樹的高度更低。

上面兩圖，我們可以看出B樹和B+樹的區別

B+樹葉子節點使用雙向指標串聯起來，這讓B+樹相比於B樹更加適合範圍查詢
B+樹非葉子節點並不存資料，所以每次查詢資料都必須遍歷到葉子節點，時間複雜度穩定為O(logN)，B-樹在運氣好的時候可以在根節點直接拿到資料。但是正是因為非葉子節點不儲存資料，可以讓一次磁碟讀取一頁中包含的索引資料更多，每個節點能索引的範圍更大更精確，讓我們可以更改定位到期望的資料。由於B+樹的葉子節點的資料都是使用連結串列連線起來的，而且他們在磁碟裡是順序儲存的，所以當讀到某個值的時候，磁碟預讀原理就會提前把這些資料都讀進記憶體，使得範圍查詢和排序都很快

B+樹在更改資料的時候，為了保證樹的平衡可能存在節點的分裂和合並，所以我們一般建議使用自增主鍵，在插入的時候，不會頻繁的發生節點的分裂。

三丶聚集索引和非聚集索引

InnoDB儲存引擎是索引組織表——表中的資料按照主鍵順序存放。非聚集索引也稱做輔助索引，無論是聚集還是非聚集，其原理都是一顆B+樹，葉子節點都儲存資料，不同的是聚集索引葉子節點儲存的是一整行的資料，非聚集索引葉子節點儲存的是聚集索引值（主鍵值）。

如果資料表定義了主鍵，那麼這個索引就是聚集索引，如果沒有定義主鍵，mysql會選擇該表的第一個非空唯一的索引構建聚集索引，如果都沒有那麼mysql會生成一個隱藏的列（6位元組的列，並且插入自增）

自增主鍵會把資料自動向後插入，避免了插入過程中聚集索引節點分裂的問題。節點分裂會帶來大範圍的資料物理移動，帶來磁碟IO的效能損耗，並且我們一般建議儘量不要改動主鍵，主鍵的更改也會帶來page分裂，產生碎片。

四丶回表查詢

如上圖，加入我們有一張表存在三個欄位id,age,name我們在id上建立了主鍵索引，這時候id主鍵索引也是聚集索引，在age上建立了普通索引，這時候age索引就是非聚集索引。如果我們執行select * from table where age=1這時候先走age索引（如果資料量較大，資料量少直接全表掃描了）那麼會找到對應的主鍵id，繼續到主鍵id索引中找到目標資料，這個操作叫做回表。

這就是為什麼根據主鍵查詢快於根據其他索引列查詢，因為如果其他索引列沒有包含我們select語句中需要的列（如果是select id from table where age<10,那麼age索引是可以覆蓋到需要的資料的(葉子節點儲存了id)，那麼也不會回表），那麼會走主鍵索引拿到需要的資料，多了一步回表操作。

這裡我們也可以看到為什麼建議使用select * ,這意味著查詢所有列，如果配合上普通索引，那麼大概率這個普通索引不會覆蓋到索引列，導致需要回表查詢。並且select*這種"我全都要"大概率會查詢到我們不需要的列，造成不必要的網路資源消耗，增加不必要的io，增加不必要的記憶體消耗。

五丶聯合索引

聯合索引是指對錶上的多個列建立索引，如上圖表存在四個欄位id,address,name,age，我們在name和age上建立索引，上圖我們粗略的展示了聯合索引的B+樹結構。我們可以觀察到在葉子節點中name是有序的，但是age無序，聯合索引是按照索引定義的順序排序的，這就導致select xxx from table where name='b'是可以根據上面定義的聯合索引查詢資料的，但是``select xxx from table where age=12是無法走上面定義的聯合索引的。這就是常說的最左字首匹配原則`的原理。

聯合索引可以減少回表

如果我們執行select age,id from table where name='a' and age=10,這個時候由於我們定義的聚集索引一級包含了需要的資料就不需要進行回表操作了（這其實也被稱為覆蓋索引，即非聚集索引中可以查詢到全部需要的列，那麼就不需要走聚集索引回表查詢資料）
聯合索引可以優化排序

上圖中的聯合索引，我們可以看到，名稱相同的節點，其年齡是有序的

也就是說select * from table where name='a' order by age這個語句將避免多一次的排序操作（select* from table where id=1 order by age會走主鍵索引拿到所有符合資料進行排序，這裡說的避免一次排序操作指拿到的資料本身就是有序的所有不需要再次排序）
索引下推ICP

全稱Index Condition PushDown,mysql 5.6後支援的一種根據索引進行查詢優化的操作。mysql資料庫會在取出所有資料的同時判斷是否進行where條件的過濾，將where的部分過濾放在儲存引擎層。

mysql5.6之前如果執行select * from table where name like '張%' and age=10這時候會先從name age的聯合索引中拿到name滿足張開頭的資料，然後回表，mysql支援ICP後，效果圖如下

mysql會根據聯合索引中記錄的age對資料進行過濾，這時候age不等於10的資料將不會回表，將回表次數從4優化到了2，這就是索引下推。
如何安排聯合索引的順序

第一原則是，如果通過調整順序，可以少維護一個索引，那麼這個順序往往就是需要優先考慮採用的，比如業務中存在兩個高頻查詢，根據name，以及根據name查詢後根據age排序，這個時候我們應該建立name age的聯合索引，上面我們說過name,age的所有其中name是有序的，age只在name相同的情況下才是有序的，這樣可以減少建立name的普通索引，並且優化排序，甚至利用索引下推減少回表。如果還存在根據age進行的查詢，那麼需要單獨維護一個age的普通索引

六丶索引建立原則

1.為搜尋，排序，分組的列建立索引

一般只為出現在where後面的列，連線子句中的列，出現在order by,或者group by的列進建立索引。不要無腦建立索引，索引是需要儲存在磁碟上的，佔用空間，並且在新增，刪除，修改的時候還需要維護索引，是需要時間的。

比如select xxx from table where name= 'a' order by user_no,這條查詢語句可以選擇在name上建立索引，也可以選擇在user_no 上建立索引，後者可以優化排序。

2.考慮列中不重複的個數建立索引

select xxxx from table where sex=1 這裡不要為sex性別建立索引，性別通常只有男和女，為其建立索引，b+樹只有兩個節點，查詢之後還要對一半的進行回表，不如直接走全表掃描

3.索引列儘可能小

mysql基本資料型別十分豐富，整數型別有tinyint,mediumint,int，bigint，我們因該儘量使用佔用位元組數小的資料型別，這樣可以讓每次讀取磁碟獲取一頁的資料，可以獲得更多的範圍資訊

4.為列字首進行索引

比如說有英文名可能很長，每次都是根據FirstName 進行like查詢，這時候可以選擇為列的前10個字元建立索引(alter table user add index idx_name(name(10)))。但是十個字元之後將無法使用索引。

5.合理的建立覆蓋索引

在聚集索引小節中，我們總結了聚集索引的好處，減少回表，優化排序，索引下推。

6.不要在uuid上建立索引

首先uuid佔用位元組大，導致每一頁範圍資訊少，並且uuid無序，這會導致插入資料的時候節點的分裂。這裡也說明了自增主鍵優秀的點，不會頻繁的節點分裂，並且不要修改主鍵，避免不必要的節點分裂。相比於uuid作為主鍵，不如使用分散式自增主鍵生成的方案

7.存在聯合索引的情況下，不要重複建立索引

存在name,age的聯合索引，那麼不需要再為name單獨建立索引了，但是可以為age建立索引，原理在聯合索引中進行了講解。

七丶索引失效

上圖是mysql的基本架構，其中存在優化器，其作用是不改變sql執行結構的情況下，讓sql更加簡單，並且根據成本分析，制定執行計劃。是否走索引，走什麼索引也是優化器來決定的（sql中可以提示使用什麼索引，強制使用某一個索引）。

常見索引失效的原因有

不滿足最左字首原則

如果存在a,b,c的聯合索引，select * from table where b=2 and a=1這種時候還是可能走聯合索引的，mysql會優化語句,但是select * from table where b=1 and c=2是無法走聯合索引的，因為b，c在b+樹中整體無序
使用了select*

使用select*需要回表，也許mysql優化器評估後覺得走非聚集索引，不如直接全表掃描
索引列上有計算，索引列上使用了函數
型別不匹配

select * from table where name = 123，可以理解成mysql把sql語句新增了型別轉換函數，導致無法走索引
like查詢左邊有%

以xxx開頭是可以走索引的，因為是有序的，但是以xxx結尾和包含xxx是無法走索引的。
or條件導致失效

select xxx from table where age=10 or name='zhangsan',age和 name上存在普通索引，但是mysql優化器覺得不如走全表掃描.這時候我們可以使用union，讓其走索引
order by 使用了聯合索引中不存在的列，或者順序不符合最左字首匹配
group by 使用了聯合索引中不存在的列，或者順序不符合最左字首匹配