01?概述

????索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)，用于快速找出某個列中有一特定值的行。

????通過上述定義可以理解索引三個基本特性：

??? 1、索引的作用是為了追求高效查找；

????2、索引是一種數(shù)據(jù)結(jié)構(gòu)，且是有序的；

????3、索引用于快速查找某一個特定值的行（非特定值情況，即模糊匹配的情況是無效的）。

????不使用索引，MySQL必須從第一條記錄開始讀完整個表，直到找到相關(guān)的行，表越大，查詢數(shù)據(jù)所花費的時間就越多（全表掃描）。如果表中查詢的列有一個索引，MySQL能夠快速到達一個表搜索數(shù)據(jù)文件，而不必查看所有數(shù)據(jù)，那么將會節(jié)省很大一部分時間。

1.1 隱式索引

隱式索引由數(shù)據(jù)庫服務(wù)器在創(chuàng)建某些對象的時候自動生成。例如，對于主鍵約束和唯一約束，數(shù)據(jù)庫服務(wù)器就會自動創(chuàng)建索引。

????之所以會存在隱式索引，是因為數(shù)據(jù)庫總是優(yōu)先考慮使用索引的這種情況，除非索引失效，但是前提是需要有字段建立索引，如果用戶不手動顯式指定索引字段，那么數(shù)據(jù)庫就自動添加一個。一切都是為了盡可能的將能優(yōu)化的情況都考慮到。

1.2 特點

? ??優(yōu)點：

????1、提高數(shù)據(jù)檢索效率，降低數(shù)據(jù)庫的IO成本；

????2、通過索引對數(shù)據(jù)進行排序，降低數(shù)據(jù)排序的成本，降低了CPU的消耗。

? ??缺點：

????1、實際上索引也是一張表，該表保存了主鍵與索引字段，并指向?qū)嶓w表的記錄，所以索引也是要占空間的（空間換時間）；

????2、雖然索引大大提高了查詢速度，同時會降低更新表的速度，如對表進行INSERT、UPDATE、DELETE操作。

1.3 應(yīng)用場景

? ??需要創(chuàng)建索引：

????1、主鍵自動創(chuàng)建唯一索引

????2、頻繁作為where查詢條件的字段應(yīng)該創(chuàng)建索引

????3、查詢中與其他表關(guān)聯(lián)的字段，外鍵關(guān)系建立索引

????4、查詢中排序的字段（order by），排序的字段若通過索引區(qū)訪問將大大提高排序速度

????5、查詢中統(tǒng)計或者分組字段（group?by）

????注：order?by/group by是先做排序再分組，因此可以建索引

???不需要創(chuàng)建索引：

????1、頻繁更新的字段不適合建立索引，因為每次更新不單單是更新了記錄還會更新索引

????2、WHERE條件里用不到的字段不創(chuàng)建索引

????3、表記錄太少，即小的數(shù)據(jù)表不應(yīng)當(dāng)使用索引

????4、經(jīng)常增刪改的表

????5、如果某個數(shù)據(jù)列包含許多重復(fù)的內(nèi)容，為它建立索引就沒有太大的實際效果

????6、數(shù)據(jù)值分布比較均勻的不適合建索引，比如性別

????7、如果列中包含大數(shù)或者NULL值，不宜創(chuàng)建索引

02?分類

2.1 根據(jù)索引字段

? ??1、單值索引

????單值索引即一個索引只包含單個列，一個表可以有多個單列索引。

? ??2、復(fù)合/聯(lián)合索引

????一個索引包含多個列，例如：INDEX Multidx(id,name.age)。

????創(chuàng)建單列索引還是復(fù)合索引，要看每次查詢中，哪些列在作為過濾條件的WHERE子句中最常出現(xiàn)。

????如果只需要一列，那么就應(yīng)當(dāng)創(chuàng)建單列索引。如果作為過濾條件的WHERE子句用到了兩個或者更多的列，那么復(fù)合索引就是最好的選擇。

2.2 根據(jù)索引字段類型

????1、主鍵索引/聚簇索引

????聚簇索引并不是一種單獨的索引類型，而是一種數(shù)據(jù)存儲方式。聚簇索引總是把數(shù)據(jù)行存儲在葉子頁中（即數(shù)據(jù)和索引都存儲在葉子節(jié)點），因此一個表中只能有一個聚簇索引。

????對于上述聚簇索引結(jié)構(gòu)，主鍵a為索引，則葉子節(jié)點就是最終的數(shù)據(jù)存儲節(jié)點，查找到葉子節(jié)點也就對應(yīng)找到了對應(yīng)的數(shù)據(jù)了。

????并不是所有的存儲引擎都支持聚簇索引。

??? InnoDB只有一個聚集索引：

????默認會拿主鍵id作為聚集索引；

????如果沒有主鍵，會取非空的唯一索引作為聚集索引；

????如果沒有主鍵和非空唯一索引，則InnoDB會自己維護一個唯一row_id作為聚集索引。

????聚簇索引的優(yōu)點如下：

????可以把相關(guān)數(shù)據(jù)保存在一起；

????數(shù)據(jù)訪問更快；

????使用覆蓋索引掃描的查詢可以直接使用頁節(jié)點中的主鍵值。

????當(dāng)然，聚簇索引也有它的缺點：

????聚簇索引最大限度提高了I/O密集型應(yīng)用的性能，但如果所有的數(shù)據(jù)都存放在內(nèi)存中，聚簇索引就沒有優(yōu)勢了；

????插入速度嚴重依賴插入順序，這也是為什么InnoDB一般都會設(shè)置一個自增的int列作為主鍵；

????更新聚簇索引的代價很高，因為會強制InnoDB將每個被更新的行移到新的位置；

????如果不按順序插入新數(shù)據(jù)時，可能會導(dǎo)致“頁分裂”；

????二級索引訪問可能會需要進行回表查詢。

????2、唯一索引

????索引列的值必須唯一，但允許有空值。

??? UNIQUE就是唯一索引，即要求每一行的數(shù)據(jù)必須唯一，但可以為空。

? ? 3、普通索引/二級索引/輔助索引

????InnoDB 中的輔助索引在葉子節(jié)點中并不存儲實際的數(shù)據(jù)，只會包含主索引的值（即索引和數(shù)據(jù)分開存儲）。這就意味著如果使用輔助索引進行數(shù)據(jù)的查找，只能查到主索引，然后根據(jù)這個主索引再次掃描以下主索引的樹，進行一次回表操作。

????對于上述非聚簇索引，假設(shè)字段a、b、c為索引，a為主鍵，則最終查找行記錄的時候，需要通過主鍵a在葉子節(jié)點的位置，獲取具體數(shù)據(jù)的位置信息，然后再去具體地址查找行記錄。即獲取葉子節(jié)點的同時并不能直接獲取最終結(jié)果，需要經(jīng)過二次查找。

????這種索引也可以叫二級索引或者輔助索引。

????注：MyISAM是非聚集索引（對應(yīng)文件MYI和MYD，分別存儲索引和數(shù)據(jù)信息），InnoDB是聚集索引（對應(yīng)文件ibd，數(shù)據(jù)和索引信息）。

????4、全文索引

????全文索引只有在MyISAM索引上才能使用，只能在CHAR、VARCHAR、TEXT類型字段上使用全文索引。

????5、空間索引

????空間索引是對空間數(shù)據(jù)類型的字段建立的索引。

03?原理

3.1?頁

??? Mysql的基本存儲結(jié)構(gòu)是頁（記錄都存在頁里邊），數(shù)據(jù)頁的特點：

????1、各個數(shù)據(jù)頁可以組成一個雙向鏈表；

????2、而每個數(shù)據(jù)頁中的記錄又可以組成一個單向鏈表；

??? 1）每個數(shù)據(jù)頁都會為存儲在它里邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽，然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄；

??? 2）以其他列(非主鍵)作為搜索條件：只能從最小記錄開始依次遍歷單鏈表中的每條記錄。

????所以，select * from user where username='xxxx'，默認會這樣做：

??? 1、定位到記錄所在的頁：需要遍歷雙向鏈表，找到所在的頁；

??? 2、從所在的頁中查找相應(yīng)的記錄。

3.2?二叉樹

????如果用二叉樹建立索引的數(shù)據(jù)結(jié)構(gòu)，那么每個節(jié)點存儲K-V，即索引字段和索引字段所在行的磁盤地址的指針，時間復(fù)雜度為O(logN)。

????但是，實際應(yīng)用中數(shù)據(jù)庫不使用二叉樹作為索引的數(shù)據(jù)結(jié)構(gòu)，主要是因為二叉樹會出現(xiàn)極度不平衡的情況：

3.3?紅黑樹

????為了應(yīng)對極端不平衡的情況，嘗試使用紅黑樹作為索引的數(shù)據(jù)結(jié)構(gòu)。紅黑樹是二叉平衡樹。

????紅黑樹不適合作為索引的特殊場景：存儲數(shù)據(jù)非常大的時候，樹的高度h太大，查找的數(shù)據(jù)如果在葉子節(jié)點，極端的情況下需要查詢高度h次才可以。

????我們需要控制查找次數(shù)，即樹的高度，而紅黑樹每個節(jié)點只存儲一個K，則為了降低高度，可以在一個節(jié)點存儲多個數(shù)據(jù)，從而可以將樹的高度降低，而B+樹能夠控制樹的高度在3~5。

3.4?B Tree

????B類樹的一個很鮮明的特點就是樹的層數(shù)比較少，而每層的節(jié)點都非常多，樹的每個葉子節(jié)點到根節(jié)點的距離都是相同的（這也是為什么叫Balance Tree的原因）。

????另外，樹的每一個節(jié)點都是一個數(shù)據(jù)頁（B+樹是葉子結(jié)點是數(shù)據(jù)頁，其余全部為索引頁），這樣每個節(jié)點只需要一次IO就可以全部讀取。這樣的結(jié)構(gòu)保證了查詢數(shù)據(jù)時能盡量少地進行磁盤IO，同時保證IO的穩(wěn)定性。

? ??特點：

??? 1、葉子節(jié)點具有相同的深度，葉子節(jié)點的指針為空；

??? 2、所有索引元素不重復(fù)；

??? 3、節(jié)點中的數(shù)據(jù)索引從左到右遞增排列。

????注：為了能夠存儲足夠多的數(shù)據(jù)的同時控制樹的高度，一個節(jié)點存儲數(shù)據(jù)的個數(shù)由表數(shù)據(jù)和高度確定。如果數(shù)據(jù)較多，則每個節(jié)點存儲數(shù)據(jù)多一些，這樣高度就降下來了。

????模擬查找關(guān)鍵字29的過程：

??? 1、根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存?！敬疟PI/O操作第1次】

??? 2、比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤塊1的指針P2。

??? 3、根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存。【磁盤I/O操作第2次】

??? 4、比較關(guān)鍵字29在區(qū)間（26,30），找到磁盤塊3的指針P2。

??? 5、根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存?！敬疟PI/O操作第3次】

??? 6、在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。

????分析上面過程，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存。

????但如果我們想進行范圍查找，查詢10~79之間的數(shù)據(jù)，就需要從跟節(jié)點一個一個往下查，范圍跨度越大，則磁盤IO的次數(shù)就越多，性能越差。?

????由于B樹的節(jié)點除了存儲Key還存儲Data，這樣每一層存儲的Key有限，也就是說這樣導(dǎo)致層高不可控，磁盤IO較多。如果除了葉子節(jié)點都存儲Key值，這樣就可以很快找到葉子節(jié)點，進而找到Data，這就引入B+樹。

????應(yīng)用：MongoDB使用B樹。

??? MongoDB是一個通用的、面向文檔的分布式數(shù)據(jù)庫，區(qū)別于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫 MySQL、Oracle 和SQL Server，MongoDB最重要的一個特點就是面向文檔：

??? 1、作為非關(guān)系型的數(shù)據(jù)庫，MongoDB對于遍歷數(shù)據(jù)的需求沒有關(guān)系型數(shù)據(jù)庫那么強，它追求的是讀寫單個記錄的性能；

??? 2、大多數(shù)OLTP的數(shù)據(jù)庫面對的都是讀多寫少的場景，B 樹與 LSM 樹在該場景下有更大的優(yōu)勢。

????上述的兩個場景都是MongoDB需要面對和解決的，所以我們會在這兩個常見場景下對不同的數(shù)據(jù)結(jié)構(gòu)進行比較。

3.5 B+ Tree

??? B+ Tree和 B Tree不同，B+ Tree中，只能將數(shù)據(jù)存儲在葉子結(jié)點中，內(nèi)部節(jié)點將只包含指針，而B Tree可以將數(shù)據(jù)存儲在內(nèi)部的葉節(jié)點中。

????因此B+ Tree的關(guān)鍵優(yōu)勢是中間節(jié)點不包含數(shù)據(jù)，因此B+ Tree的大小遠小于B Tree，并且可以將更多數(shù)據(jù)存儲到存儲器中。另外，B+ Tree的每一個葉子節(jié)點包含了到相鄰的節(jié)點的鏈接，這樣可以快速地進行范圍遍歷。

??? B+樹結(jié)構(gòu)如下：

??? MySQL真正使用的數(shù)據(jù)結(jié)構(gòu)不是B樹，而是B樹的變種B+樹，B+樹是一個平衡二叉樹，從根節(jié)點到每個葉子節(jié)點的高度差值不超過1，而且同層級的節(jié)點間有指針相互鏈接。其特點：

??? 1、非葉子節(jié)點不存儲data，只存儲索引（冗余），可以放更多的索引；

??? 2、葉子節(jié)點包含所有索引字段（非葉子節(jié)點也有一個相同的值，存在冗余，B樹則沒有冗余）；

??? 3、葉子節(jié)點用指針連接，提高區(qū)間訪問的性能（B樹葉子節(jié)點是沒有這個指針的）。

????注：在非葉子節(jié)點不存儲data，因為InnoDB對于頁大小有限制（16KB），所以只存儲索引可以在每一行存儲更多的索引信息（B樹非葉子節(jié)點存儲data信息，浪費內(nèi)存），將data放到葉子節(jié)點。例如，bigint的索引，則15占用8Byte，后面地址信息6Byte，則一個索引占8+6=14Byte，頁大小16KB，則大概可以放16KB/14Byte=1170個節(jié)點。如果葉子節(jié)點data占據(jù)1KB，則頁大小16KB的時候葉子節(jié)點可以存儲16個索引，則最終可以存儲的索引為1170*1170*16（假設(shè)是3層），這是千萬級別的數(shù)據(jù)。

????根節(jié)點一般事先加載到內(nèi)存，所以在根節(jié)點可以快速定位加載的頁，從磁盤加載對應(yīng)的數(shù)據(jù)頁到內(nèi)存，實現(xiàn)快速查找。

????在B+樹葉子節(jié)點保存了所有的索引數(shù)據(jù)（不是所有的表數(shù)據(jù)），所有非葉子結(jié)點都會在葉子節(jié)點保留一份備份，所以B+樹節(jié)點樹比實際存儲的數(shù)據(jù)的個數(shù)要多。

? ??B樹與B+樹：

????1、B樹非葉子節(jié)點存儲data（索引數(shù)據(jù)的地址），B+樹非葉子節(jié)點只存儲索引信息；

????2、B樹不存在數(shù)據(jù)冗余，B+樹存在冗余（普通索引會存儲主鍵，主鍵索引會存儲所有數(shù)據(jù)，這樣就存在數(shù)據(jù)冗余了），葉子節(jié)點存儲所有數(shù)據(jù)。

3.6?Hash

????哈希索引就是采用一定的哈希算法，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節(jié)點到葉子節(jié)點逐級查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非?？臁?/p>

????Hash索引結(jié)構(gòu)的特殊性，其檢索效率非常高，索引的檢查可以一次定位，不像B-Tree索引需要從根節(jié)點到枝節(jié)點，最后才能訪問到葉節(jié)點。這樣多次的IO訪問，所以哈希索引的效率要高于B-Tree索引。

? ??哈希索引局限性：

??? 1、hash函數(shù)計算后的結(jié)果是隨機的，如果是磁盤上放置數(shù)據(jù)，比如主鍵id，那么隨著id的增長，id對應(yīng)的行在磁盤上隨機放置，而隨機查詢非常慢；

??? 2、哈希索引也沒辦法利用索引完成排序；

????3、無法對范圍查詢進行優(yōu)化；

????4、在有大量重復(fù)鍵值情況下，哈希索引的效率也是極低的（哈希碰撞問題）；

????5、無法利用前綴索引，比如在B-Tree中，filed列的值“helloword”并添加索引，查詢xx=helloword時自然可以利用索引，xx=hello也可以利用索引（左前綴索引），因為hash(“helloword”和hash(“hello”)兩者的關(guān)系仍為隨機；

????6、排序無法優(yōu)化；

????7、必須回行，就是說，通過索引拿到的數(shù)據(jù)位置，必須回到表中取數(shù)據(jù)。

3.7?LSM

????LSM Tree技術(shù)出現(xiàn)的一個最主要的原因就是磁盤的隨機寫速度要遠遠低于順序?qū)懙乃俣?，而?shù)據(jù)庫要面臨很多寫密集型的場景，所以很多數(shù)據(jù)庫產(chǎn)品就把LSM Tree的思想引入到了數(shù)據(jù)庫領(lǐng)域。

??? LSM Tree顧名思義，就是The Log-Structured Merge-Tree的縮寫。從這個名稱里面可以看到幾個關(guān)鍵的信息：

????1、log-structred，通過日志的方式來組織的

????2、Merge，可以合并的

????3、Tree，一種樹形結(jié)構(gòu)

????實際上它并不是一棵樹，也不是一種具體的數(shù)據(jù)結(jié)構(gòu)，它實際上是一種數(shù)據(jù)保存和更新的思想。簡單地說，就是將數(shù)據(jù)按照key來進行排序（在數(shù)據(jù)庫中就是表的主鍵），之后形成一顆一顆的樹形結(jié)構(gòu)，或者不是樹形結(jié)構(gòu)，是一張小表也可以，這些數(shù)據(jù)通常被稱為基線數(shù)據(jù)；之后把每次數(shù)據(jù)的改變（也就是log）都記錄下來，也按照主鍵進行排序，之后定期的把log中對數(shù)據(jù)的改變合并（merge）到基線數(shù)據(jù)當(dāng)中。

????注：OceanBase采用LSM。

04?基本操作?

4.1 創(chuàng)建索引

????CREATE INDEX 索引名稱 ON table?(column1,…);?

4.2 刪除索引

????DROP INDEX 索引名稱 ON 表名;

4.3 查看索引

????SHOW INDEX FROM 表名;

05?索引失效

5.1 最左前綴原則/ABC問題

????即便表建立了索引，where查詢語句中存在索引，也不一定走索引，是不是走索引遵循最左前綴原則：

????索引對應(yīng)的數(shù)據(jù)結(jié)構(gòu)B+樹生成的時候就是按照最左的字段排序生成的，如果不指明該字段的取值，那么就無法確定走索引B+樹的左還是右，進而只能全表掃描。

5.2?索引失效的情況

????1、列類型是字符串，查詢條件未加引號

????2、未使用該列作為查詢條件

????3、使用like時通配符在前

????4、在查詢條件中使用OR

????5、索引字段做計算（格式轉(zhuǎn)換，運算）

????6、字符類型索引=數(shù)值類型字段值

????7、不符合最左前綴/聯(lián)合索引ABC問題

07?索引優(yōu)化

7.1 設(shè)計高效索引策略，避免索引失效

? ? 設(shè)計高效索引策略的時候需要考慮以下的情況：

????1、索引長度以及區(qū)分度；

??? 2、聯(lián)合索引需要考慮索引先后順序。

7.2 考慮索引覆蓋

????索引覆蓋是指，如果查詢的列恰好是索引的一部分，那么查詢只需要在索引文件上進行，不需要回行到磁盤再找數(shù)據(jù)（即避免回表操作），這種查詢速度非?？?，稱為“索引覆蓋”。

????覆蓋索引是一個非常有用的工具，可以極大提升性能。試想一下，如果一個查詢只需要掃描索引而無需二次回表查詢，會帶來什么好處：

??? 1、索引行通常遠小于數(shù)據(jù)行的大小，所以如果只需要索引，那么MySQL就會極大地減少數(shù)據(jù)訪問量；

??? 2、因為索引是按照順序存儲的，所以對于I/O密集型的范圍查詢會比隨機從磁盤讀取每一行數(shù)據(jù)的I/O要少的多；

????3、由于InnoDB的聚簇索引，所以覆蓋索引對InnoDB特別有用。

7.3 索引下推

??? Index Condition Pushdown（索引下推），MySQL 5.6引入了索引下推優(yōu)化，是一種在存儲引擎層使用索引過濾數(shù)據(jù)的一種優(yōu)化方式，ICP可以減少存儲引擎訪問基表的次數(shù)以及MySQL服務(wù)器訪問存儲引擎的次數(shù)。

????默認開啟，使用SET optimizer_switch = 'index_condition_pushdown=off';可以將其關(guān)閉。

????官方文檔中給的例子和解釋如下：

????people表中（zipcode，lastname，firstname）構(gòu)成一個索引

????SELECT * FROM people WHERE zipcode='95054' AND lastname LIKE '%etrunia%' AND address LIKE '%Main Street%';

????如果沒有使用索引下推技術(shù)，則MySQL會通過zipcode='95054'從存儲引擎中查詢對應(yīng)的數(shù)據(jù)，返回到MySQL服務(wù)端，然后MySQL服務(wù)端基于lastname LIKE '%etrunia%'和address LIKE '%Main Street%'來判斷數(shù)據(jù)是否符合條件。

????如果使用了索引下推技術(shù)，則MySQL首先會返回符合zipcode='95054'的索引，然后根據(jù)lastname LIKE '%etrunia%'和address LIKE '%Main Street%'來判斷索引是否符合條件。如果符合條件，則根據(jù)該索引來定位對應(yīng)的數(shù)據(jù)，如果不符合，則直接reject掉。有了索引下推優(yōu)化，可以在有l(wèi)ike條件查詢的情況下，減少回表次數(shù)。