索引是什么

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

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

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

如下圖所示: 

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

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

所以索引的構(gòu)建 ， 本質(zhì)上是控制樹的高度

索引數(shù)據(jù)結(jié)構(gòu)

二叉樹：

• 紅黑樹
• Hash 表
• B Tree

樹形索引

表中的數(shù)據(jù)與索引結(jié)構(gòu)映射關(guān)系可以理解如下圖:

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

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

樹的動畫

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

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

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

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

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

為什么不是紅黑樹？

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

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

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

B Tree:

B + Tree:

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

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

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

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

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

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

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

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

對于B+ 樹，我們假設(shè)要查找50這個數(shù)據(jù)，先從根節(jié)點即(15 56 77) 這些數(shù)據(jù)中找到50所處的范圍，因為 (15 56 77) 已經(jīng)是有序的，可以根據(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 是經(jīng)過大量的測試，為我們定義了一個合理的默認值 16Kb

可以通過下面語句查詢：

show global status like 'Innodb_page_size'

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

葉子節(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 字段，叫 張三的人非常多。會產(chǎn)生很多次hash沖突，只能退化成列表搜索了

表引擎

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

MyISAM 和 InnoDB 引擎

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

MyISAM 引擎

• frm: 表結(jié)構(gòu)相關(guān), frame（框架） 縮寫`
• MYD: MyISAM Data 表數(shù)據(jù)
• MYI: MyISAM Index 表索引

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

InnoDB

• frm 表結(jié)構(gòu)信息
• ibd 表數(shù)據(jù)加索引

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

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

聚集與非聚集索引

聚集索引 (InnoDB 主鍵索引)

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

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

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

單從索引結(jié)構(gòu)的來看，聚集索引的查找速度高于非聚集索引

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

這樣做的目的有兩個：

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

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

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

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

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

為什么是整型

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

為什么是自增

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

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

聯(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 導(dǎo)致 age 查出來的數(shù)據(jù)有多個（31 32）, 31 和 32 下的 position (dev admin ) 不是有序的，便無法利用二分算法進行查找。所以無法利用 position 這個索引，這也就是左前綴法則的原理和聯(lián)合索引失效的原理

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

最新評論