mysql的索引呢刻蟹？你又知道多少逗旁？
在Java面試中必問mysql，問mysql的時(shí)候索引也是必問舆瘪，可見索引有多么重要片效。簡單的說索引是一種為了提高數(shù)據(jù)檢索效率的一種數(shù)據(jù)結(jié)構(gòu)。
索引的常?模型
索引的出現(xiàn)是為了實(shí)現(xiàn)數(shù)據(jù)檢索的高效介陶，只所以引入索引的概念是為因?yàn)槟軐?shí)現(xiàn)數(shù)據(jù)高效索引的數(shù)據(jù)結(jié)構(gòu)很多堤舒，我們先看一下常見的三種數(shù)據(jù)結(jié)構(gòu)哈希表、有序數(shù)組和搜索樹哺呜。
-
哈希表是一種key-value鍵值對(duì)舌缤，輸入key就可以找到value的值。實(shí)現(xiàn)一個(gè)哈希表很簡單某残，把值放在數(shù)組里国撵，用一個(gè)哈希函數(shù)把key換算成一個(gè)確定的位置，然后把value放在數(shù)組的這個(gè)位置玻墅。不可避免地介牙，多個(gè)key值經(jīng)過哈希函數(shù)的換算，會(huì)出現(xiàn)同一個(gè)值的情況澳厢。處理這種情況的一種方法是环础，拉出一個(gè)鏈表。假設(shè)你現(xiàn)在在維護(hù)一個(gè)訂單信息和訂單號(hào)sn的表剩拢，需要根據(jù)訂單號(hào)sn查找訂單信息线得。此時(shí)對(duì)應(yīng)的哈希索引如下圖：截屏2020-07-28 下午11.20.32
訂單m和訂單n算出來的都是m，但是沒關(guān)系徐伐，后面跟的是一個(gè)鏈表贯钩，如果要查詢order_m首先計(jì)算order_sn算出為m時(shí)間復(fù)雜度為O(1)再遍歷后面的鏈表時(shí)間復(fù)雜度為O(n),這種情況對(duì)于取區(qū)間的值就比較慢了，必須一個(gè)一個(gè)的遍歷。所以哈希表只適合等值查詢的場景角雷。
-
有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀祸穷，但是有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎，因?yàn)榫S持有序的成本非常高勺三，每次插入和刪除都需要維持有序雷滚，下標(biāo)需要移動(dòng)。如果僅僅看查詢效率吗坚，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了揭措。在需要更新數(shù)據(jù)的時(shí)候就麻煩了，你往中間插入一個(gè)記錄就必 須得挪動(dòng)后面所有的記錄刻蚯，成本太高绊含。
截屏2020-07-28 下午11.38.13 -
跳表 skiplist，我們知道鏈表在每次查找的時(shí)候都需要遍歷一次表炊汹，我們能不能改造一下鏈表提高檢索的效率躬充，可以使用索引的思想對(duì)鏈表進(jìn)行改造，將部分關(guān)鍵提取出來當(dāng)做關(guān)鍵節(jié)點(diǎn)讨便，如果檢索效率還是太低充甚，再將關(guān)鍵節(jié)點(diǎn)的數(shù)據(jù)取出來當(dāng)關(guān)鍵節(jié)點(diǎn)的關(guān)鍵節(jié)點(diǎn)。
image-20200729230340082 -
二叉搜索樹霸褒，如果我們有個(gè)用戶表用二叉搜索樹實(shí)現(xiàn)的話如下圖:image.png
二叉搜索樹的特點(diǎn)是:每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)伴找，父節(jié)點(diǎn)又小于右兒子。這樣如果你要查ID_card_n2的話废菱，按照?qǐng)D中的搜索順序就是按照UserA -> UserC -> UserF -> User2這個(gè)路徑得到技矮。這個(gè)時(shí)間復(fù)雜度是O(log(N))。
用一張動(dòng)圖來表示搜索過程假設(shè)在這個(gè)樹中搜索20流程如下:
image.png當(dāng)然為了維持O(log(N))的查詢復(fù)雜度殊轴，你就需要保持這棵樹是平衡二叉樹衰倦。為了做這個(gè)保證，更新的時(shí)間復(fù)雜度也是O(log(N))旁理。所謂維持平衡就是要避免出現(xiàn)類似于鏈表的樹樊零，要讓數(shù)據(jù)分布在樹的兩側(cè)。樹可以有二叉孽文，也可以有多叉驻襟。多叉樹就是每個(gè)節(jié)點(diǎn)有多個(gè)兒子，兒子之間的大小保證從左到右遞增芋哭。二叉樹是搜索效率最高的沉衣，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲(chǔ)卻并不使用二叉樹。其原因是楷掉，索引不止存在內(nèi)存中厢蒜，還要寫到磁盤上。你可以想象一下一棵100萬節(jié)點(diǎn)的平衡二叉樹烹植，樹高20斑鸦。一次查詢可能需要訪問20個(gè)數(shù)據(jù)塊。為什么樹高是1就要io一次草雕？因?yàn)槊恳淮蝘o只能取出一個(gè)節(jié)點(diǎn)的數(shù)據(jù)對(duì)于二叉樹也就是2個(gè)巷屿，只取兩個(gè)因?yàn)橐鶕?jù)取出來的數(shù)據(jù)的指針去獲取后面的數(shù)據(jù)，除非后面節(jié)點(diǎn)的數(shù)據(jù)剛好和硬盤中取出的數(shù)據(jù)相鄰墩虹。為了減少io成本就應(yīng)該把樹高降低嘱巾，所以數(shù)據(jù)庫使用了N插樹。在一次io中查出來一個(gè)節(jié)點(diǎn)的數(shù)據(jù)包含N個(gè)指針诫钓，從而降低io次數(shù)旬昭。
InnoDB 的索引模型
InnoDB使用了B+樹索引模型，B+樹是在搜索樹的基礎(chǔ)上改進(jìn)的菌湃。為了方便理解我們就把模型簡化為二叉樹问拘，樹中的節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)本身，而是只是作為索引惧所。除此之外骤坐，我們把每個(gè)葉子節(jié)點(diǎn)串在一條鏈表上，鏈表中的數(shù)據(jù)是從小到大有序的下愈。經(jīng)過改造之后的二叉樹纽绍，就像圖中這樣，看起來有點(diǎn)想跳表势似。
改造之后拌夏，如果我們要求某個(gè)區(qū)間的數(shù)據(jù)。我們只需要拿區(qū)間的起始值履因，在樹中進(jìn)行查找辖佣，當(dāng)查找到某個(gè)葉子節(jié)點(diǎn)之后，我們?cè)夙樦湵硗蟊闅v搓逾，直到鏈表中 的結(jié)點(diǎn)數(shù)據(jù)值大于區(qū)間的終止值為止卷谈。所有遍歷到的數(shù)據(jù)，就是符合區(qū)間值的所有數(shù)據(jù)霞篡。但是如果在千萬上億級(jí)別的數(shù)據(jù)中構(gòu)建索引世蔗，如果索引都放入內(nèi)存中盡管檢索非常好但是也是非常耗費(fèi)內(nèi)存的一件事，所以不能不索引全部放內(nèi)存中朗兵，放硬盤就涉及到了io性能的問題污淋，前面我們提到了降低樹高，將二叉變?yōu)镸叉余掖，這個(gè)M的數(shù)值放多少合適寸爆？不管是內(nèi)存中的數(shù)據(jù)，還是磁盤中的數(shù)據(jù)，操作系統(tǒng)都是按頁(一頁大小通常是4KB赁豆，這個(gè)值可以通過getconfig PAGE_SIZE命令查看)來讀取的仅醇，一次會(huì)讀一頁的數(shù)據(jù)。如果要讀取的數(shù)據(jù)量超過一頁的大小魔种，就會(huì)觸發(fā)多次IO操作析二。所以，我們?cè)谶x擇m大小的時(shí)候节预，要盡量讓每個(gè)節(jié)點(diǎn)的大小等于一個(gè)頁的大小叶摄。讀取一個(gè)節(jié)點(diǎn)，只需要一次磁盤IO操作安拟。對(duì)于一個(gè)B+樹來說蛤吓，m值是根據(jù)頁的大小事先計(jì)算好的，也就是說糠赦，每個(gè)節(jié)點(diǎn)最多只能有m個(gè)子節(jié)點(diǎn)柱衔。在往數(shù)據(jù)庫中寫入數(shù)據(jù)的過程中，這樣就有可能使索引中某些節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)超過m愉棱，這個(gè)節(jié)點(diǎn)的大小超過了一個(gè)頁的大小唆铐，讀取這樣一個(gè)節(jié)點(diǎn)，就會(huì)導(dǎo)致多次磁盤IO操作奔滑。當(dāng)出現(xiàn)超過m的情況我們就進(jìn)行列表操作艾岂，裂變之后父節(jié)點(diǎn)也會(huì)超過m，同樣的操作我們將父節(jié)點(diǎn)也進(jìn)行一遍朋其。這種級(jí)聯(lián)反應(yīng)會(huì)從下往上王浴，一直影響到根節(jié)點(diǎn)。我們用一個(gè)動(dòng)圖(圖中的m為3)來表示:
B+樹的特點(diǎn)：
每個(gè)節(jié)點(diǎn)中子節(jié)點(diǎn)的個(gè)數(shù)不能超過m梅猿，也不能小于m/2;
根節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)可以不超過m/2氓辣，這是一個(gè)例外;
m叉樹只存儲(chǔ)索引，并不真正存儲(chǔ)數(shù)據(jù)袱蚓，這個(gè)有點(diǎn)兒類似跳表; 通過鏈表將葉子節(jié)點(diǎn)串聯(lián)在一起钞啸，這樣可以方便按區(qū)間查找;
一般情況，根節(jié)點(diǎn)會(huì)被存儲(chǔ)在內(nèi)存中喇潘，其他節(jié)點(diǎn)存儲(chǔ)在磁盤中体斩。
“N叉樹”的N值在MySQL中是可以被人工調(diào)整的么?
5.6以后可以通過page大小來間接控制。
最左前綴原則
B+樹這種索引結(jié)構(gòu)颖低，可以利用索引的“最左前綴”絮吵，來定位記錄。假設(shè)我們有張表里面用name忱屑、age建立了聯(lián)合索引蹬敲，索引示意圖為
當(dāng)你的邏輯需求是查到所有名字是“張三”的人時(shí)暇昂，可以快速定位到ID4，然后向后遍歷得到所有需要的結(jié)果伴嗡。 如果你要查的是所有名字第一個(gè)字是“張”的人急波，你的SQL語句的條件是"where name like ‘張%’"。這時(shí)闹究，你也能夠用上這個(gè)索引，查找到第一個(gè)符合條件的記錄是ID3食店，然后向后遍歷渣淤，直到不滿足條件為止。 可以看到吉嫩，不只是索引的全部定義价认，只要滿足最左前綴，就可以利用索引來加速檢索自娩。這個(gè)最左前綴可以是聯(lián)合索引的最左N個(gè)字段用踩，也可以是字符串索引的最左M個(gè)字符，在建立聯(lián)合索引的時(shí)候忙迁，如何安排索引內(nèi)的字段順序脐彩。如果通過調(diào)整順序，可以少維護(hù)一個(gè)索引姊扔，那么這個(gè)順序往往就是需要優(yōu)先考慮采用 的惠奸。
索引下推
以市?表的聯(lián)合索引(name, age)為例，如果現(xiàn)在有一個(gè)需求:檢索出表中“名字第一個(gè)字是張恰梢，而且年齡是10歲 的所有男孩”佛南。那么，SQL語句是這么寫的:
select * from tuser where name like '張%' and age=10 and ismale=1;
在MySQL 5.6之前嵌言，只能從ID3開始一個(gè)個(gè)回表嗅回。到主鍵索引上找出數(shù)據(jù)行，再對(duì)比字段值摧茴。而MySQL 5.6 引入的索引下推優(yōu)化(index condition pushdown)绵载， 可以在索引遍歷過程中，對(duì)索引中包含的字段先做判斷苛白， 直接過濾掉不滿足條件的記錄尘分，減少回表次數(shù)。沒有索引下推的情況為：
5.6以后有索引下推的情況
問題：
CREATE TABLE `test` ( `a` int(11) NOT NULL, `b` int(11) NOT NULL, `c` int(11) NOT NULL, `d` int(11) NOT NULL, PRIMARY KEY (`a`,`b`), KEY `c` (`c`),
KEY `ca` (`c`,`a`),
KEY `cb` (`c`,`b`) ) ENGINE=InnoDB;
既然主鍵包含了a丸氛、b這兩個(gè)字段培愁，那意味著單獨(dú)在字段c上創(chuàng)建一個(gè)索引，就已經(jīng)包含了三個(gè)字段了呀缓窜，為什么要?jiǎng)?chuàng)建“ca”“cb”這兩個(gè)索引?
如果c列上重復(fù)率很低的情況下,兩個(gè)索引都可以不用建定续。因?yàn)槿绻^濾只剩下幾條數(shù)據(jù),排序也不影響,如果C列重復(fù)度比較高,就需要建立(c,b)的聯(lián)合索引了,來消除排序了谍咆。因?yàn)樵跀?shù)據(jù)量大的情況下,排序是一個(gè)非常耗時(shí)的操作,很有可能還需要磁盤臨時(shí)表來做排序。而且如果沒有(c,b)聯(lián)合索引,limit 1僅僅表示返回給客戶端一條數(shù)據(jù),沒有起到限制掃描行,數(shù)的作用ca列上的索引,由于滿足最左前綴,不用加私股。因?yàn)閏是固定值,那么a列就是有序的.那么這里limit 1就很好限制了只用精準(zhǔn)掃描一條數(shù)據(jù).所以有時(shí)候如果在where條件建立索引的效率差的情況下,在order by limit這一列建索引也是很好的方案,排好序,在回表,只要過濾出滿足條件的limit行,就能及時(shí)停止掃描
總結(jié):
- 覆蓋索引:如果查詢條件使用的是普通索引(或是聯(lián)合索引的最左原則字段)摹察，查詢結(jié)果是聯(lián)合索引的字段或是主鍵，不 用回表操作倡鲸，直接返回結(jié)果供嚎，減少IO磁盤讀寫讀取正行數(shù)據(jù)
- 最左前綴:聯(lián)合索引的最左 N 個(gè)字段，也可以是字符串索引的最左 M 個(gè)字符
- 聯(lián)合索引:根據(jù)創(chuàng)建聯(lián)合索引的順序峭状，以最左原則進(jìn)行where檢索克滴，比如(age，name)以age=1 或 age= 1 and name=‘張 三’可以使用索引优床，單以name=‘張三’ 不會(huì)使用索引劝赔，考慮到存儲(chǔ)空間的問題，還請(qǐng)根據(jù)業(yè)務(wù)需求胆敞，將查找頻繁的數(shù)據(jù)進(jìn)行靠左 創(chuàng)建索引着帽。
- 索引下推:like 'hello%’and age >10 檢索，MySQL5.6版本之前移层，會(huì)對(duì)匹配的數(shù)據(jù)進(jìn)行回表查詢仍翰。5.6版本后，會(huì)先過濾掉a ge<10的數(shù)據(jù)观话，再進(jìn)行回表查詢歉备，減少回表率，提升檢索速度
