如何理解并實(shí)現(xiàn)索引的原理和優(yōu)化

這篇文章主要講解了“如何理解并實(shí)現(xiàn)索引的原理和優(yōu)化”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“如何理解并實(shí)現(xiàn)索引的原理和優(yōu)化”吧！

Part1為什么Kafka不需要我們關(guān)心索引，而Mysql卻需要？

Kafka 和 MySQL 雖然最終數(shù)據(jù)都是落磁盤，但是兩者在用途和數(shù)據(jù)查詢方式上有著很大的差異，所以決定了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不同，進(jìn)而決定了索引的復(fù)雜程度。

我們先看下kafka的存儲(chǔ)結(jié)構(gòu)：

由于 kafka 的定位是進(jìn)行穩(wěn)定的高性能數(shù)據(jù)讀寫。所以對(duì)磁盤來(lái)說(shuō)，是采用順序讀寫的方式，落在了一些 .log 文件中，并以基準(zhǔn)偏移量補(bǔ)0命名。

為了實(shí)現(xiàn)高速查找 kafka 創(chuàng)建了稀疏索引文件(隔一段數(shù)據(jù)創(chuàng)建一條，而非全量)，即index文件。其中維護(hù)消息的 offset 和 .log文件的物理位置。通過(guò)二分查找快速定位log文件并順序掃描找到目標(biāo)。

所以，kafka的索引組織方式是相對(duì)簡(jiǎn)單、方案相對(duì)固定，但MySQL卻不行。Mysql是關(guān)系型數(shù)據(jù)庫(kù)，是為了支持復(fù)雜的業(yè)務(wù)數(shù)據(jù)查詢而創(chuàng)建的，查詢方式、數(shù)據(jù)獲取需求多種多樣，要求MySQL具備更加復(fù)雜的索引機(jī)制來(lái)加速?gòu)?fù)雜業(yè)務(wù)查詢場(chǎng)景。

Part2MySQL數(shù)據(jù)怎么被組織[1][2]

以InnoDB存儲(chǔ)引擎來(lái)看mysql數(shù)據(jù)存儲(chǔ)：

參考了三本資料，基本把最重要的部分都概括了

數(shù)據(jù)被分了多個(gè)邏輯層：行->頁(yè)->區(qū)塊->段->表空間。

我們知道，InnoDB存儲(chǔ)引擎表是Index organized的（數(shù)據(jù)即索引，索引即數(shù)據(jù)），他們都維護(hù)在一個(gè)B+樹上，數(shù)據(jù)段就是葉子節(jié)點(diǎn)，索引段就是非葉子節(jié)點(diǎn)；

而我們劃分的段、區(qū)塊 其實(shí)都是為了利用操作系統(tǒng)的資源（比如每次從磁盤加載到內(nèi)存的數(shù)據(jù)大小按區(qū)塊來(lái)約定等等`）來(lái)達(dá)到更高效讀寫的目的，邏輯劃分的。

其中頁(yè)是MySQL和磁盤交互的最小單位，怎么從頁(yè)找到行，怎么聚合到塊、到段再到空間呢。

1數(shù)據(jù)記錄最小單位-- 行

從上面總圖中摘出一條記錄的結(jié)構(gòu)如下圖：

我們可以看到，記錄頭中除了行號(hào)，還有下一條記錄的標(biāo)識(shí)next_record，所以，我們可以通過(guò)next_record將記錄連接起來(lái)，以單向鏈表的形式，所以這就決定了，當(dāng)我們?cè)谟涗涙溨袑ふ夷秤涗洉r(shí)，只能順序遍歷，這也決定了一條數(shù)據(jù)鏈不會(huì)太長(zhǎng)。

但一個(gè)頁(yè)默認(rèn)是16K，加上行溢出等處理，一頁(yè)最多存放7992行記錄，這么多的記錄，必須順序遍歷么？當(dāng)然不需要，讓我看看頁(yè)是怎么組織記錄行的。

2與磁盤最小交互單位-- 頁(yè)

作為與磁盤交互的最小單位，是用來(lái)存放實(shí)際數(shù)據(jù)的(頁(yè)類型是b-tree Node存真實(shí)數(shù)據(jù),還有其他類型如索引目錄頁(yè)等用來(lái)加速查詢)從上面的大圖中可以大致看到一個(gè)頁(yè)的整體結(jié)構(gòu)：

讓我們來(lái)看幾個(gè)關(guān)鍵的字段參數(shù)：

Page Directory 決定著記錄項(xiàng)在頁(yè)內(nèi)的查詢效率

為了更快速的查詢，頁(yè)目錄存儲(chǔ)的本頁(yè)的數(shù)據(jù)目錄(槽)，包含最大最小記錄和 分組數(shù)據(jù)鏈的最大記錄的偏移量。方便使用二分法快速查找數(shù)據(jù)，不需要再?gòu)淖钚≈甸_始遍歷，如下圖：

圖片來(lái)自《從根兒上理解 MySQL》

File Header決定頁(yè)和頁(yè)之間怎樣關(guān)聯(lián)

記錄本頁(yè)的一些通用信息，主要包含< 本頁(yè)頁(yè)號(hào)、上一頁(yè)、下一頁(yè)、頁(yè)類型、所屬表空間等等>。

通過(guò)頁(yè)號(hào)來(lái)找到本頁(yè)、通過(guò)上下頁(yè)進(jìn)行雙向鏈表串聯(lián)、通過(guò)類型判斷是索引頁(yè)還是數(shù)據(jù)頁(yè)。。。

圖片來(lái)自《從根兒上理解 MySQL》

此字段決定了頁(yè)和頁(yè)之間可以很方便的通過(guò)上述屬性進(jìn)行關(guān)聯(lián)。

Page Header決定頁(yè)的層級(jí)

存儲(chǔ)的本頁(yè)的數(shù)據(jù)信息，主要包含**<** 本頁(yè)記錄數(shù)量、在B+樹中的層級(jí)、歸屬的索引ID、插入方向、最大事務(wù)ID等等 >。

有了頁(yè)面的數(shù)據(jù)組織概念，那么，怎么利用這些結(jié)構(gòu)來(lái)實(shí)現(xiàn)的數(shù)據(jù)快速查詢呢？

Part3索引的演進(jìn)思路

從上面的數(shù)據(jù)組織的知識(shí)里可以看到，行記錄之間串聯(lián)成單向鏈表，在每頁(yè)中都按分組方式分布在此頁(yè)的最小記錄和最大記錄之間。

頁(yè)面之間通過(guò)上一頁(yè)、下一頁(yè)的指針，串聯(lián)成雙向鏈表，在磁盤中進(jìn)行存儲(chǔ)，如下圖：

那么，要查詢一條記錄，可以怎么做？

3原始：順序方式

如上圖所示的數(shù)據(jù)串聯(lián)方式，自然的提供了一種查詢方式：即按主鍵順序遍歷每頁(yè)和頁(yè)中的記錄行。

但是，這樣的查詢方式，除了在頁(yè)內(nèi)有二分優(yōu)化，再無(wú)效率可言。怎么辦？

尋求改進(jìn)：既然頁(yè)內(nèi)的行記錄可以分組入槽，那數(shù)據(jù)頁(yè)之間為什么不行呢?

4改進(jìn)：目錄方式

我們將頁(yè)向上聚蔟，構(gòu)建一個(gè)頁(yè)號(hào)目錄，先在目錄中查找，再到對(duì)應(yīng)頁(yè)中查找，就比順序查找要快很多了。

尋求改進(jìn)：這樣的方式所需大量連續(xù)空間 + 目錄會(huì)隨數(shù)據(jù)變動(dòng)而頻繁變動(dòng)，怎么辦？

5演進(jìn)：主鍵B+樹方式

其實(shí)，在敘述行記錄結(jié)構(gòu)的時(shí)候，我們就看到，數(shù)據(jù)行的結(jié)構(gòu)中，除了實(shí)際業(yè)務(wù)數(shù)據(jù)外，還有很多額外空間。

如record_type用來(lái)表示該記錄的類型是數(shù)據(jù)還是索引。正是這些額外的空間的設(shè)計(jì)，給InnoDB以更加適合的方式組織索引提供了支持：

圖片來(lái)自《從根兒上理解 MySQL》

這就是一棵B+樹，頁(yè)節(jié)點(diǎn)有層級(jí)區(qū)分，頁(yè)中的行記錄有類型區(qū)分。

業(yè)務(wù)數(shù)據(jù)都包含在葉子節(jié)點(diǎn)中，目錄數(shù)據(jù)都包含在其他非葉節(jié)點(diǎn)中。

這樣組織方式的優(yōu)勢(shì)，是允許足夠少的層級(jí)容納足夠多的數(shù)據(jù)項(xiàng)(可以簡(jiǎn)單的假設(shè)每一頁(yè)的數(shù)據(jù)項(xiàng)大小來(lái)預(yù)估)。

而這個(gè)索引方式就是我們常說(shuō)的聚蔟索引。即使用主鍵值進(jìn)行記錄和頁(yè)的排序，且葉子節(jié)點(diǎn)含有全部用戶數(shù)據(jù)。

尋求改進(jìn)：如果我想用其他列來(lái)查詢，怎么辦？

6擴(kuò)展：二級(jí)索引、聯(lián)合索引

二級(jí)索引

比如用戶需要根據(jù)某一列（a列）的值來(lái)查詢，那就再重新創(chuàng)建一個(gè)B+樹。此索引樹和聚蔟索引樹的差別在于，索引節(jié)點(diǎn)是以a列的值為目錄，且葉子節(jié)點(diǎn)只包含a列的值和主鍵兩個(gè)值。

如果用戶需要查詢除c列以外的更多信息，則需要拿主鍵ID再去聚蔟索引查一次，也叫回表。

聯(lián)合索引

二級(jí)索引是除主鍵外的單列索引，而聯(lián)合索引則是多個(gè)列共同排序。假設(shè)用戶需要用a 、b 兩個(gè)列進(jìn)行有序查詢，那內(nèi)在含義是，在a列值相同的情況下，再判斷b的值。

同二級(jí)索引一樣，InnoDB也需要再創(chuàng)建一棵B+樹，且目錄項(xiàng)的排序按先a，后b進(jìn)行排序串聯(lián)，葉子節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)只包含 a 、b、主鍵三個(gè)值。

Part4生產(chǎn)實(shí)踐之觸類旁通

7美團(tuán)定時(shí)任務(wù)索引優(yōu)化[3]

系統(tǒng)需要定時(shí)的撈取特定時(shí)間段內(nèi)特定狀態(tài)、特定類型、特定操作者的任務(wù)進(jìn)行定時(shí)處理。

select * from task   where     status=x     and operator_id=xxxx      and operate_time>xxxxxxxx01     and operate_time<xxxxxxxx99     and type=x;

開發(fā)發(fā)現(xiàn)此sql運(yùn)行的越來(lái)越慢，希望給每個(gè)字段加二級(jí)索引，被優(yōu)化師叫停，而是考慮的該表所有查詢方式后，創(chuàng)建了一個(gè)聯(lián)合索引：

(status,operator_id,type,operate_time)

為什么不建多個(gè)的二級(jí)索引？為什么范圍查詢的字段要放在最后？

分析：

（1）從前面的原理部分我們知道，索引是要占內(nèi)存的，不是越多越好，能起作用就行。

（2）用于范圍匹配的字段的索引位置要嚴(yán)謹(jǐn)。因?yàn)閯?chuàng)建索引的時(shí)候，根據(jù)索引字段的順序來(lái)進(jìn)行排序，如果把time字段放在type字段前面建索引，在查詢時(shí)，因?yàn)閠ime是一個(gè)范圍值，那么多個(gè)time值延續(xù)到type字段，整體是無(wú)序的，無(wú)法用到type索引。

8螞蟻分布式主事務(wù)表的索引運(yùn)用

螞蟻的分布式事務(wù)中的主事務(wù)表起到了維護(hù)整體事務(wù)狀態(tài)的作用，其中包含了整體事務(wù)狀態(tài)、操作時(shí)間等字段。而在業(yè)務(wù)支付發(fā)生異常，且實(shí)時(shí)回滾失敗時(shí)，需要事務(wù)恢復(fù)系統(tǒng)從遠(yuǎn)程撈取前1分鐘的異常數(shù)據(jù)，并撈取對(duì)應(yīng)的分支記錄表發(fā)起異步回滾。

考慮查詢效率，查詢sql會(huì)限定業(yè)務(wù)發(fā)生時(shí)間在[前10分鐘，前1分鐘]，是有范圍查詢，所以，針對(duì)其他字段，業(yè)務(wù)時(shí)間的索引順序需要置于聯(lián)合索引的最后。此操作的原理和上一部分美團(tuán)定時(shí)任務(wù)的原理是一樣的。

9阿里開發(fā)手冊(cè)中幾條典型的規(guī)范[4]

【強(qiáng)制】 在 varchar 字段上建立索引時(shí)，必須指定索引長(zhǎng)度，沒(méi)必要對(duì)全字段建立索引，根據(jù)實(shí)際文本區(qū)分度決定索引長(zhǎng)度。

原理關(guān)聯(lián)：字段越長(zhǎng)，索引占內(nèi)存越多，只要其長(zhǎng)度可以保證區(qū)分度即可

【強(qiáng)制】 字符搜索嚴(yán)禁左模糊或者全模糊，如果需要請(qǐng)走搜索引擎來(lái)解決。

原理關(guān)聯(lián)：左模糊的字段不是有序的，無(wú)法用到索引

【推薦】 如果有 order by 的場(chǎng)景，請(qǐng)注意利用索引的有序性。order by 最后的字段是組合索引的一部分，并且放在索引組合順序的最后，避免出現(xiàn) file_sort 的情況，影響查詢性能。

原理關(guān)聯(lián)：如果條件中有范圍查詢，則后續(xù)字段是無(wú)序的，order by時(shí)無(wú)法用到索引

【推薦】 建組合索引的時(shí)候，區(qū)分度最高的在最左邊。

原理關(guān)聯(lián)：區(qū)分度越高，查詢路徑越短，效率越高

感謝各位的閱讀，以上就是“如何理解并實(shí)現(xiàn)索引的原理和優(yōu)化”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)如何理解并實(shí)現(xiàn)索引的原理和優(yōu)化這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！