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索引內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！