索引是什么

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結構

最重要的點是有序的，我們用索引就是為了快速的查找數(shù)據(jù)，如果一堆數(shù)據(jù)是無序的，程序只能挨個遍歷每個元素，對比值，才能找到某個元素，最壞的情況要比對N次， N 是這一堆數(shù)據(jù)的長度。如果數(shù)據(jù)是有序的，我們就可以使用二分查找算法，他的時間復雜度是 O(long N)，效率比直接挨個查找快的多。

二分查找算法關鍵步驟就是找到區(qū)間的中間值，然后確定要查找的值落在左區(qū)間還是右區(qū)間，一直重復這個步驟直到找到該值。于是就可以將這種查詢方法映射成一種數(shù)據(jù)結構——樹。我們規(guī)定一種樹，有左節(jié)點，右節(jié)點，和當前節(jié)點。并且左節(jié)點 < 當前節(jié)點 < 右節(jié)點 .

如下圖所示: 

由于樹具有方便快速查找的特性，我們一般都會使用樹結構去存儲索引，并對簡單的查找二叉樹做了很多優(yōu)化，比如 紅黑樹，平衡二叉樹， B 樹 B+樹

樹的構建，刪除， 查找都有一定的算法，這里不詳細描述，只需知道樹有一個通用的特性：樹的高度越低，查找效率越高

所以索引的構建 ， 本質上是控制樹的高度

索引數(shù)據(jù)結構

二叉樹：

• 紅黑樹
• Hash 表
• B Tree

樹形索引

表中的數(shù)據(jù)與索引結構映射關系可以理解如下圖:

加入要找到 col2 = 23 的記錄，如果不使用索引，我們需要對整張表掃描，從 34 -> 77 -> 5 -> 91 -> 22 -> 89 -> 23, 需要對比7次才能找到

使用索引時， 查找路徑時是 34 -> 22 -> 23 只需對比3次就行。在表中數(shù)據(jù)量極大時，差別更明顯

樹的動畫

推薦一個在線工具，它以動畫的形式描述了每種樹的構建與查找方法

為什么不是簡單的二叉樹？

我們知道MySQL索引采用的是 B+樹，那么為什么不是其他的樹呢？

因為在順序插入下，樹的高度會一直增加，等同于鏈表。無法控制樹的高度，如下圖: 

如果需要查找6，仍然需要查找6次

為什么不是紅黑樹？

紅黑樹（平衡二叉樹）： 雖然會自動平衡節(jié)點位置，但仍然高度不可控。表比較大時會導致樹的高度很高。增加查找次數(shù)

為什么最終選擇B+樹 而不是B樹

要解決這個疑問，我們需要知道這兩種樹的構造，如下圖：

B Tree:

B + Tree:

水平方向可以存放更多的索引key

B+樹將數(shù)據(jù)全部放到葉子節(jié)點，留下更多的空間放 key, key 越多，寬度越寬，同樣的數(shù)據(jù)量，寬度越大，高度越小。查找次數(shù)就越小。

為什么需要 擴展樹的寬度而不是樹的深度呢？

如果按照上面的說法，我們拓寬了樹的寬度，減少了樹的高度，但是比較次數(shù)并沒有發(fā)生改變，只不過是減少了縱向的比較，增加了橫向的比較

這個疑問的前提是所有的數(shù)據(jù)都在內存中，直接在內存中進行比較大小。 但是事實并非如此，不可能把表中的所有數(shù)據(jù)都加到內存中，必須先從磁盤中加在一部分數(shù)據(jù)到內存，然后在內存中比較大小，內存中運算的速度遠遠大于從磁盤加載數(shù)據(jù)的速度。磁盤加載數(shù)據(jù)是機械運動，需要電機帶動磁針轉圈掃描磁道。內存運算則是電子運動，不可同日而語。

數(shù)據(jù)從磁盤加載到內存中，是有最小單位的，這個單位是 頁， 不是 字節(jié)或者 位， 頁是固定字節(jié)數(shù)據(jù)，由操作系統(tǒng)決定，這樣可以減少加載磁盤的次數(shù)。

由于B Tree 的每一層都已經是有序的，我們把樹中水平方向的數(shù)據(jù)放在磁盤相鄰的地方，每次從磁盤加載一頁數(shù)據(jù)時，便可以得到部分或全部的水平方向的結點，不用再次排序。

在水平方向在內存中使用二分查找的效率遠遠大于從磁盤中加載一頁數(shù)據(jù)， 所以我們希望樹越寬越好,這樣一次性加載的數(shù)據(jù)就越多，而不是越高越好

對于B+ 樹，我們假設要查找50這個數(shù)據(jù)，先從根節(jié)點即(15 56 77) 這些數(shù)據(jù)中找到50所處的范圍，因為 (15 56 77) 已經是有序的，可以根據(jù)二分查找算法找到 50 處于 15--56之間， 然后加載 15 所指向的下一頁數(shù)據(jù) （15 20 49）,再次根據(jù)二分查找算法，找到50處于 49之后，再從磁盤加載49所指向的數(shù)據(jù)頁，找到50

數(shù)據(jù)量估算

MySQL 自己也有一個邏輯 頁，一般是操作系統(tǒng)中 頁 的整數(shù)倍，這個邏輯頁的數(shù)據(jù)可以通過配置修改，但是不建議，MySQL 是經過大量的測試，為我們定義了一個合理的默認值 16Kb

可以通過下面語句查詢：

show global status like 'Innodb_page_size'

假設上圖中表示的是主鍵索引，類型是 bigint, 占 8 個字節(jié)。指向下一頁的指針占 6 個字節(jié)， 那么這一頁可以存放 16 * 1024 / (8 + 6) = 1170 個key, 同理第二頁即 （15 20 49 ....） 也可以放 1170 個key , 對于第三頁，也就是葉子節(jié)點，包含了主鍵和對應整行的數(shù)據(jù)。就按照一行數(shù)據(jù)放1KB 吧(已經比較大了) 能放 16 行，那么只有一頁根節(jié)點的話， 這個索引索引樹能放 1170 * 1170 * 16 =21,902,400 行數(shù)據(jù)。 這棵樹的高度只有3，就已經能支持上千萬的數(shù)據(jù)量了。也就是只需加載3次磁盤就可以查找到數(shù)據(jù)了。并且MySQL 存放根節(jié)點的頁還有優(yōu)化，可能會把這個頁常駐內存。

葉子節(jié)點包含所有的索引字段

如上圖所示，在主鍵索引中，葉子節(jié)點包含了表中的所有字段，對于一些全表掃描的查詢來說，直接掃描葉子節(jié)點便可以得到數(shù)據(jù)，不用再從索引樹上挨個查找

葉子節(jié)點直接包含雙向指針,范圍查找效率高

對于一些范圍查詢比如 id > 20 and id < 50, 在索引樹上定位到 20 之后直接使用右向指針定位到下一個比20大的數(shù)據(jù)，依次往下，直到 50，便可以檢出該區(qū)間的數(shù)據(jù)，如果沒有這個指針，（B Tree）則需要再次回到索引樹中去查找 , 極大的提高了范圍查找的性能

Hash 索引

hash 索引原理如下： 

更快

大多情況下 Hash 索引比B+ Tree 索引更快，Hash 計算的效率非常高，且僅需一次查找就可以定位到數(shù)據(jù)(無hash沖突的情況)

不支持范圍查詢

圖中有些歧義，Hash 后的值是沒有順序的，也不是整數(shù)，所以無法進行高效的范圍查詢查詢

hash 沖突問題

如果在某列上有很多相同的行，比如 name 字段，叫 張三的人非常多。會產生很多次hash沖突，只能退化成列表搜索了

表引擎

我們常說的 MyISAM 引擎 或者 InnoDB 引擎是基于表的，是表的一個屬性， 可不是基于數(shù)據(jù)庫的， 同一個數(shù)據(jù)庫中可以有不同引擎的表

MyISAM 和 InnoDB 引擎

不同引擎的表在磁盤中產生的文件也不一樣，數(shù)據(jù)庫文件位置默認在安裝目錄/data 下

MyISAM 引擎

• frm: 表結構相關, frame（框架） 縮寫`
• MYD: MyISAM Data 表數(shù)據(jù)
• MYI: MyISAM Index 表索引

索引結構中的葉子節(jié)點的 data 存放的是 數(shù)據(jù)行的位置，及這一行在 MYD 文件的位置， 而不是直接放的真實數(shù)據(jù)

InnoDB

• frm 表結構信息
• ibd 表數(shù)據(jù)加索引

表數(shù)據(jù)組織形式

表結構本身就是按照 B+ Tree 結構存儲， 葉子節(jié)點放的是出索引列其他列的數(shù)據(jù)

聚集與非聚集索引

聚集索引 (InnoDB 主鍵索引)

葉子節(jié)點直接包含整行數(shù)據(jù)

非聚集索引 (MyISAM 索引, InnoDB 非主鍵索引)

葉子節(jié)點不包含整行數(shù)據(jù),包含的是對應行所在的位置，或者主鍵Id

單從索引結構的來看，聚集索引的查找速度高于非聚集索引

InnoDB 只有一個聚集索引，默認是主鍵索引， 非主鍵索引的葉子節(jié)點存放的是主鍵的值，如下圖：

這樣做的目的有兩個：

• 節(jié)約空間，避免將整行的數(shù)據(jù)存放多份
• 保證數(shù)據(jù)的一致性，否則每增加一行，對應的每個索引都要維護一份行數(shù)據(jù)。必須要等到每個索引都更新完，數(shù)據(jù)才能插入成功

★★★ 為什么建議InnoDB 表必須有主鍵，并且是整型自增的？

InnoDB 整個表的數(shù)據(jù)就是用B+ 樹組織的，如果存在主鍵，就用主鍵為索引，葉子節(jié)點存儲行數(shù)據(jù)

如果沒有主鍵，InnoDB 就會找到一個每行數(shù)據(jù)都不相同的列作為索引來組織整個表的數(shù)據(jù)

如果沒有找到這種列，就會建一個隱藏的列，自動維護值，用這個隱藏的列來組織數(shù)據(jù)，所以我們要主動做這種工作減少數(shù)據(jù)庫的負擔

為什么是整型

因為在查找數(shù)據(jù)的過程中，需要多次比較大小，整型的比較運算速度大于字符串， 并且占用空間小

為什么是自增

這一點涉及到B+ 樹的構建，我們知道索引一個最重要的特性就是排好序 的。如果我們不是順序插入的，那么樹就要自己額外做排序，調整樹結構，浪費了性能

• 避免葉子節(jié)點的分裂
• 避免B+ 樹做平衡調整

聯(lián)合索引

聯(lián)合索引和單索引差不多，只不過是先按第一個字段排序，再按第二個字段排序，然后再按第三個字段排序。

這種排序規(guī)則表明了只有在第一個字段相等的情況下，第二字段才是有序的。第二字段相等的情況下，第三個字段才是有序的。

所以 name = 'Bill' and age = 20 and position = 'dev' 可以用到全部索引， 因為 name 確定了，age 是有序的，age 可以走索引， age 確定后 position 可以走索引。這個聯(lián)合索引可以全部用到

如果是 name = 'Bill and age > 30 and position = 'dev'' , 首先name 可以走索引，name 確定后 age 是有序的，age 也可以走索引，但是 age > 30 導致 age 查出來的數(shù)據(jù)有多個（31 32）, 31 和 32 下的 position (dev admin ) 不是有序的，便無法利用二分算法進行查找。所以無法利用 position 這個索引，這也就是左前綴法則的原理和聯(lián)合索引失效的原理

到此這篇關于MySQL索引原理詳解的文章就介紹到這了,更多相關MySQL索引內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論