前言
當(dāng)提到MySQL數(shù)據(jù)庫(kù)的時(shí)候图呢,我們的腦海會(huì)經(jīng)常想起幾個(gè)關(guān)鍵字:索引条篷、事務(wù)、數(shù)據(jù)庫(kù)鎖等蛤织,索引是MySQL的靈魂赴叹,是平時(shí)進(jìn)行查詢的利器,也是面試中的重中之重指蚜。
可能我們了解MySQL的底層是b+樹稚瘾,會(huì)加快查詢,也會(huì)在表中建立索引姚炕,但是這是遠(yuǎn)遠(yuǎn)不夠的摊欠,下面我們來(lái)列舉幾個(gè)面試中常見的索引問題:
- 索引為什么要用b+樹這種數(shù)據(jù)結(jié)構(gòu)?
- 聚集索引和非聚集索引的區(qū)別
- 索引什么時(shí)候會(huì)失效柱宦,最左原則是什么些椒?
當(dāng)遇到這些問題的時(shí)候,可能會(huì)發(fā)現(xiàn)自己對(duì)索引還是一知半解掸刊,今天我們一起學(xué)習(xí)MySQL的索引免糕。
一、一條查詢語(yǔ)句是如何執(zhí)行的
首先來(lái)看在MySQL數(shù)據(jù)庫(kù)中忧侧,一條查詢語(yǔ)句是如何執(zhí)行的石窑,索引出現(xiàn)在哪個(gè)環(huán)節(jié),起到了什么作用蚓炬。
1.1 應(yīng)用程序發(fā)現(xiàn)SQL到服務(wù)器
當(dāng)執(zhí)行SQL語(yǔ)句時(shí)松逊,應(yīng)用程序會(huì)連接到相關(guān)的數(shù)據(jù)庫(kù)服務(wù)器,然后服務(wù)器對(duì)SQL進(jìn)行處理肯夏。
1.2 查詢緩存
接著數(shù)據(jù)庫(kù)服務(wù)器會(huì)先去查詢是否有該SQL語(yǔ)句的緩存经宏,key是查詢的語(yǔ)句犀暑,value是查詢的結(jié)果。如果存在緩存烁兰,即你查詢的結(jié)果直接命中耐亏,就會(huì)直接從緩存中拿出value返回給客戶端。
注:這個(gè)查詢過程中沪斟,查詢不會(huì)被解析广辰,不會(huì)生成查詢計(jì)劃,不會(huì)被執(zhí)行
1.3 查詢優(yōu)化處理主之,執(zhí)行查詢計(jì)劃
如果沒有存在緩存择吊,則執(zhí)行此步驟
- 解析SQL:生成解析樹咬展,驗(yàn)證關(guān)鍵字如select敞嗡、where柑晒、left jion等是否正確
- 預(yù)處理:進(jìn)一步檢查解析樹是否合法芙代,如檢查數(shù)據(jù)表和列是否存在糕再,驗(yàn)證用戶權(quán)限等钉迷。
- 優(yōu)化SQL: 決定使用哪個(gè)索引庐完,或者在多個(gè)表關(guān)聯(lián)的時(shí)候決定表的連接順序裆蒸,緊接著琼讽,將SQL語(yǔ)句轉(zhuǎn)化成執(zhí)行計(jì)劃
1.4將查詢結(jié)果返回給客戶端
最后必峰,數(shù)據(jù)庫(kù)服務(wù)器將查詢結(jié)果返回給客戶端。(如果查詢可以緩存钻蹬,MySQL也會(huì)將結(jié)果存放到緩存中)
這就是一條查詢語(yǔ)句的執(zhí)行流程吼蚁,可以看到索引出現(xiàn)在優(yōu)化SQL的流程步驟中,接下來(lái)了解索引到底是什么
二 索引概述
先簡(jiǎn)單了解以下索引的相關(guān)概念
2.1 索引是什么
索引是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)
2.2 索引分類
1)從存儲(chǔ)結(jié)構(gòu)上來(lái)劃分
- Btree索引(B+tree问欠,B-tree)
- 哈希索引
- full-index 全文索引
- Rtree
2)從應(yīng)用程序上來(lái)劃分 - 普通索引:即一個(gè)索引只包含單個(gè)列肝匆,一個(gè)表可以有多個(gè)單列索引
- 唯一索引:索引列的值必須唯一,但允許有空值
- 復(fù)合索引:一個(gè)索引包含多個(gè)列
3)從表記錄的排列順序和索引的排列順序是否一致來(lái)劃分 - 聚集索引:表記錄的排列順序和索引的排列順序一致
- 非聚集索引:表記錄的排列順序和索引的排列順序不一致
2.3 聚集索引和非聚集索引
1)簡(jiǎn)單概述
- 聚集索引:以主鍵創(chuàng)建的索引
- 非聚集索引:以非主鍵創(chuàng)建的索引(也叫二級(jí)索引)
2)詳細(xì)概括 -
聚集索引
聚集索引表記錄的排列順序和索引的排列順序一致顺献,所以查詢效率快旗国,因?yàn)橹灰业降谝粋€(gè)索引值記錄,其余連續(xù)性的記錄在物理表中也會(huì)連續(xù)存放注整,一起就可以查詢到能曾。
缺點(diǎn):新增比較慢,因?yàn)闉榱吮WC表中記錄的物理順序和索引順序一致肿轨,在記錄插入的時(shí)候寿冕,會(huì)對(duì)數(shù)據(jù)頁(yè)進(jìn)行重新排序 -
非聚集索引
索引的邏輯順序與磁盤上行的物理存儲(chǔ)順序不同,非聚集索引在葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵和索引列椒袍,當(dāng)我們使用非聚集索引查詢數(shù)據(jù)時(shí)驼唱,需要拿到葉子節(jié)點(diǎn)上的主鍵再去表中查找想要的數(shù)據(jù)。這個(gè)過程就是我們所說(shuō)的回表槐沼。
3)聚集索引和非聚集索引的區(qū)別 - 聚集索引再葉子節(jié)點(diǎn)中曙蒸,存儲(chǔ)的是表中的數(shù)據(jù)
- 非聚集索引在葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵和索引列
舉個(gè)例子
比如漢語(yǔ)字典捌治,想要查「阿」字岗钩,只需要翻到字典前幾頁(yè)纽窟,a開頭的位置,接著「啊」「愛」都會(huì)出來(lái)兼吓。也就是說(shuō)臂港,字典的正文部分本身就是一個(gè)目錄,不需要再去查其他目錄來(lái)找到需要找的內(nèi)容视搏。我們把這種正文內(nèi)容本身就是一種按照一定規(guī)則排列的目錄稱為==聚集索引==审孽。
如果遇到不認(rèn)識(shí)的字,只能根據(jù)“偏旁部首”進(jìn)行查找浑娜,然后根據(jù)這個(gè)字后的頁(yè)碼直接翻到某頁(yè)來(lái)找到要找的字佑力。但結(jié)合部首目錄和檢字表而查到的字的排序并不是真正的正文的排序方法。
image.png
比如要查“玉”字筋遭,我們可以看到在查部首之后的檢字表中“玉”的頁(yè)碼是587頁(yè)打颤,然后是玨,是251頁(yè)漓滔。很顯然编饺,在字典中這兩個(gè)字并沒有挨著,現(xiàn)在看到的連續(xù)的“玉响驴、玨透且、瑩”三字實(shí)際上就是他們在非聚集索引中的排序,是字典正文中的字在非聚集索引中的映射豁鲤。我們可以通過這種方式來(lái)找到所需要的字秽誊,但它需要兩個(gè)過程,先找到目錄中的結(jié)果琳骡,然后再翻到結(jié)果所對(duì)應(yīng)的頁(yè)碼锅论。我們把這種目錄純粹是目錄,正文純粹是正文的排序方式稱為==非聚集索引==日熬。
2.4MySQL如何添加索引
1)添加PRIMARY KEY(主鍵索引)
ALTER TABLE 'tableName' ADD PRIMARY KEY ('column')
2)添加UNIQUE(唯一索引)
ALTER TABLE 'tableName' ADD UNIQUE('column')
3)添加INDEX(普通索引)
ALTER TABLE 'tableName' ADD INDEX indexName ('column')
4)添加FULLTEXT (全文索引)
ALTER TABLE 'tableName' ADD FULLTEXT('column')
5)添加多列索引
ALTER TABLE `tableName` ADD INDEX indexName (`column1`,`column2`,`column3`)
索引底層數(shù)據(jù)結(jié)構(gòu)
了解了索引的基本概念后棍厌,可能最好奇的就是索引的底層是怎么實(shí)現(xiàn)的呢?為什么索引可以如此高效地進(jìn)行數(shù)據(jù)的查找呢竖席?如何設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)可以滿足我們的要求耘纱?下文通過一般程序員的思維來(lái)想一下如果是我們來(lái)設(shè)計(jì)索引,要如何設(shè)計(jì)來(lái)達(dá)到索引的效果毕荐。
3.1哈希索引
可能直接想到的就是用哈希表來(lái)實(shí)現(xiàn)快速查找束析,就像我們平時(shí)用的hashmap一樣,value=get(key)O(1)時(shí)間復(fù)雜度一步到位憎亚,確實(shí)员寇,哈希索引是一種方式
1)定義
哈希索引就是采用一定的哈希算法弄慰,只需一次哈希算法即可立刻定位到相應(yīng)的位置,速度非车妫快陆爽。本質(zhì)上就是將鍵值換成新的哈希值,根據(jù)這個(gè)哈希值來(lái)定位
2)局限性
- 哈希索引沒法利用索引完成排序
- 不能進(jìn)行多字段查詢
- 在有大量重復(fù)鍵值的情況下扳缕,哈希索引的效率是極低的(出現(xiàn)哈希碰撞問題)
- 不支持范圍查詢慌闭。
在MySQL常用的InnoDB引擎中,還是使用B+Tree索引比較多躯舔。InnoDB是自適應(yīng)哈希索引的(哈希索引的創(chuàng)建由InnoDB存儲(chǔ)引擎自動(dòng)優(yōu)化創(chuàng)建驴剔,我們干預(yù)不了)
3.2 如何設(shè)計(jì)索引的數(shù)據(jù)結(jié)構(gòu)呢
假設(shè)要查詢某個(gè)區(qū)間的數(shù)據(jù),我們只需要拿到區(qū)間的起始值粥庄,然后在書中查找丧失。如數(shù)據(jù)為:
1)查詢[7,30]區(qū)間的數(shù)據(jù)
當(dāng)找到起始節(jié)點(diǎn)10后,再順著鏈表進(jìn)行遍歷惜互,知道鏈表中的節(jié)點(diǎn)數(shù)據(jù)大于區(qū)間的終止值為止布讹。所有遍歷到的數(shù)據(jù),就是符合區(qū)間值的所有數(shù)據(jù)
** 2)還可以怎么優(yōu)化**
利用二叉查找樹载佳,區(qū)間查詢的功能已經(jīng)實(shí)現(xiàn)了炒事,但是,為了節(jié)省內(nèi)存蔫慧,我們只能把樹存儲(chǔ)在硬盤中挠乳。
那么,每個(gè)節(jié)點(diǎn)的讀取或者訪問姑躲,都對(duì)應(yīng)一次硬盤IO操作睡扬,每次查詢數(shù)據(jù)時(shí)磁盤IO操作的次數(shù),也叫做IO漸進(jìn)復(fù)雜度黍析,也就是樹的高度
所以卖怜,我們要減少IO磁盤操作的次數(shù),也就是要降低樹的高度
結(jié)構(gòu)優(yōu)化過程如下圖所示:
這里將二叉樹變成了M叉樹阐枣,降低了樹的高度马靠,那么這個(gè)M應(yīng)該選擇多少才合適呢?
問題:對(duì)于相同個(gè)數(shù)的數(shù)據(jù)構(gòu)建m叉樹索引蔼两,m叉樹的m越大甩鳄,那樹的高度就越小,那么m叉樹中的m是不是越大越好呢额划?到底多大才合適呢妙啃?
不管是內(nèi)存中的數(shù)據(jù)還是磁盤中的數(shù)據(jù),操作系統(tǒng)都是按頁(yè)(一頁(yè)的大小通常是4kb俊戳,這個(gè)值可以通過getconfig(PAGE_SIZE)命令查看)來(lái)讀取的揖赴,一次只會(huì)讀取一頁(yè)的數(shù)據(jù)馆匿。
如果要讀取的數(shù)據(jù)量超過了一頁(yè)的大小,就會(huì)觸發(fā)多次IO操作燥滑。所以在選擇m大小的時(shí)候渐北,要盡量讓每個(gè)節(jié)點(diǎn)的大小等于一個(gè)頁(yè)的大小。一般實(shí)際應(yīng)用中突倍,出度d(樹的分叉數(shù))是非常大的數(shù)字腔稀,通常超過100盆昙;樹的高度(h)非常小羽历,通常不超過3。
3.3 B樹
順著解決問題的思路知道了我們想要的數(shù)據(jù)結(jié)構(gòu)是什么淡喜。目前索引常用的數(shù)據(jù)結(jié)構(gòu)是b+樹秕磷,先介紹一下什么是b樹(也就是B-tree)
1)B樹的特點(diǎn):
- 關(guān)鍵字分布在整棵樹的所有節(jié)點(diǎn)
- 任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中
-
搜索可能在非葉子節(jié)點(diǎn)結(jié)束
如下圖所示:
image.png
3.4 B+樹
了解B樹,再來(lái)看一下B+樹炼团,也是MySQL索引大部分使用的數(shù)據(jù)結(jié)構(gòu)
1)B+樹的特點(diǎn):
- 非葉子節(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同澎嚣。
- 非葉子節(jié)點(diǎn)的子樹指針P[i]指向關(guān)鍵字屬于 [k[i],K[i+1])的子樹(注意:區(qū)間是前閉后開)。
- 為所有的葉子節(jié)點(diǎn)增加一個(gè)鏈指針
- 所有關(guān)鍵字都出現(xiàn)在葉子節(jié)點(diǎn)
這些基本特點(diǎn)是為了滿足以下的特性瘟芝。
2)B+樹的特性 - 所有的關(guān)鍵字都出現(xiàn)在葉子節(jié)點(diǎn)的鏈表中易桃,并且鏈表的關(guān)鍵字是有序的
- 搜索只在葉子節(jié)點(diǎn)中命中
- 非葉子節(jié)點(diǎn)相當(dāng)于葉子節(jié)點(diǎn)的索引層,葉子節(jié)點(diǎn)是存儲(chǔ)關(guān)鍵字?jǐn)?shù)據(jù)的數(shù)據(jù)層
3)相對(duì)B樹锌俱,B+樹做索引的優(yōu)勢(shì) - B+樹的讀寫磁盤代價(jià)更低晤郑。B+樹沒有具體指向關(guān)鍵字具體信息的指針,所以內(nèi)部節(jié)點(diǎn)相對(duì)B樹更小贸宏,如果把所有關(guān)鍵字存放在同一塊盤中造寝,那么盤中所容納的關(guān)鍵字?jǐn)?shù)量越多,一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多吭练,相應(yīng)的诫龙,IO讀寫次數(shù)就降低了
- 樹的查詢效率更加穩(wěn)定。B+樹所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)鲫咽,所有關(guān)鍵字查詢的路徑長(zhǎng)度相同签赃,每次數(shù)據(jù)的查詢效率想當(dāng)。而B樹可能在非葉子節(jié)點(diǎn)就停止查找了分尸,所以查詢的效率不夠穩(wěn)定
- B+樹只需要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷
Mongo DB的索引為什么選擇的是B樹锦聊,而MySQL是B+樹?
因?yàn)镸ongo DB不是傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)寓落,而是以類似于Json格式的Bson格式作為存儲(chǔ)的NoSQL非關(guān)系型數(shù)據(jù)庫(kù)括丁,目的就是高性能、高可用伶选、易拓展史飞。擺脫了關(guān)系模型尖昏。所以范圍查找和遍歷查找的需求就沒那么強(qiáng)烈。
3.6 MyISAM存儲(chǔ)引擎和InnoDB的索引有什么區(qū)別
1)MyISAM存儲(chǔ)引擎
- 主鍵索引
MyISAM的索引文件(.MYI)和數(shù)據(jù)文件(.MYD)文件是分離的构资,索引文件僅保存記錄所在頁(yè)的指針(物理位置)抽诉,通過這些指針來(lái)讀取頁(yè),進(jìn)而讀取被索引的行吐绵。樹中的葉子節(jié)點(diǎn)保存的是對(duì)應(yīng)行的物理位置迹淌。通過該值,存儲(chǔ)引擎能順利地進(jìn)行回表查詢己单,得到一行完整記錄唉窃。同時(shí),每個(gè)葉子也保存了指向下一個(gè)葉子的指針纹笼,從而方便葉子節(jié)點(diǎn)的范圍遍歷纹份。
- 輔助索引
在MyISAM中,主鍵索引和輔助索引在結(jié)構(gòu)上沒有任何區(qū)別廷痘,只是主鍵索引要求key是唯一的蔓涧,而輔助索引的key可以重復(fù)。
1)Innodb存儲(chǔ)引擎
Innodb的主鍵索引和輔助索引之前提到過笋额,再回顧一次元暴。
- 主鍵索引
InnoDB主鍵索引中既存儲(chǔ)了主健值,又存儲(chǔ)了行數(shù)據(jù)兄猩。
- 輔助索引
對(duì)于輔助索引茉盏,InnoDB采用的方式是在葉子節(jié)點(diǎn)中保存主鍵值,通過這個(gè)主鍵值來(lái)回表查詢到一條完整記錄厦滤,因此按輔助索引檢索其實(shí)進(jìn)行了二次查詢援岩,效率是沒有主鍵索引高的。
四掏导、MySQL索引失效
在上一節(jié)中了解了索引的多種數(shù)據(jù)結(jié)構(gòu)享怀,以及B樹和B+樹的對(duì)比等,大家應(yīng)該對(duì)索引的底層實(shí)現(xiàn)有了初步的了解趟咆。這一節(jié)從應(yīng)用層的角度出發(fā)添瓷,看一下如何建索引更能滿足我們的需求,以及MySQL索引什么時(shí)候會(huì)失效的問題值纱。先來(lái)思考一個(gè)小問題鳞贷。問題:當(dāng)查詢條件為2個(gè)及2個(gè)以上時(shí),是創(chuàng)建多個(gè)單列索引還是創(chuàng)建一個(gè)聯(lián)合索引好呢虐唠?它們之間的區(qū)別是什么搀愧?哪個(gè)效率高呢?先來(lái)建立一些單列索引進(jìn)行測(cè)試:
這里建立了一張表,里面建立了三個(gè)單列索引userId,mobile,billMonth咱筛。 然后進(jìn)行多列查詢搓幌。
explain select * from `t_mobilesms_11` where userid = '1' and mobile = '13504679876' and billMonth = '1998-03'
我們發(fā)現(xiàn)查詢時(shí)只用到了userid這一個(gè)單列索引,這是為什么呢迅箩?因?yàn)檫@取決于MySQL優(yōu)化器的優(yōu)化策略溉愁。當(dāng)多條件聯(lián)合查詢時(shí),優(yōu)化器會(huì)評(píng)估哪個(gè)條件的索引效率高饲趋,它會(huì)選擇最佳的索引去使用拐揭。也就是說(shuō),此處三個(gè)索引列都可能被用到奕塑,只不過優(yōu)化器判斷只需要使用userid這一個(gè)索引就能完成本次查詢堂污,故最終explain展示的key為userid。
4.1 總結(jié)
多個(gè)單列索引在多條件查詢時(shí)優(yōu)化器會(huì)選擇最優(yōu)索引策略爵川,可能只用一個(gè)索引敷鸦,也可能將多個(gè)索引都用上。但是多個(gè)單列索引底層會(huì)建立多個(gè)B+索引樹寝贡,比較占用空間,也會(huì)浪費(fèi)搜索效率 所以多條件聯(lián)合查詢時(shí)最好建聯(lián)合索引值依。那聯(lián)合索引就可以三個(gè)條件都用到了嗎圃泡?會(huì)出現(xiàn)索引失效的問題嗎?
4.2 聯(lián)合索引失效問題
該部分參考并引用文章:一張圖搞懂MySQL的索引失效(https://segmentfault.com/a/1190000021464570)創(chuàng)建user表愿险,然后建立 name, age, pos, phone 四個(gè)字段的聯(lián)合索引 全值匹配(索引最佳)颇蜡。
索引生效,這是最佳的查詢辆亏。 那么時(shí)候會(huì)失效呢风秤?
1)違反最左匹配原則
最左匹配原則:最左優(yōu)先,以最左邊的為起點(diǎn)任何連續(xù)的索引都能匹配上扮叨,如不連續(xù)缤弦,則匹配不上。如:建立索引為(a,b)的聯(lián)合索引彻磁,那么只查 where b = 2 則不生效碍沐。換句話說(shuō):如果建立的索引是(a,b,c),也只有(a),(a,b),(a,b,c)三種查詢可以生效衷蜓。這里跳過了最左的name字段進(jìn)行查詢累提,發(fā)現(xiàn)索引失效了。 遇到范圍查詢(>磁浇、<斋陪、between、like)就會(huì)停止匹配。比如:a= 1 and b = 2 and c>3 and d =4 如果建立(a,b,c,d)順序的索引无虚,d是用不到索引的鞍匾,因?yàn)閏字段是一個(gè)范圍查詢,它之后的字段會(huì)停止匹配骑科。
2)在索引列上做任何操作
如計(jì)算橡淑、函數(shù)、(手動(dòng)或自動(dòng))類型轉(zhuǎn)換等操作咆爽,會(huì)導(dǎo)致索引失效而進(jìn)行全表掃描梁棠。
explain select * from user where left(name,3) = 'zhangsan' and age =20
這里對(duì)name字段進(jìn)行了left函數(shù)操作,導(dǎo)致索引失效斗埂。
3)使用不等于(!= 符糊、<>)
explain select * from user where age != 20;
explain select * from user where age <> 20;
4)like中以通配符開頭('%abc')
索引失效
explain select * from user where name like ‘%zhangsan’;
索引生效
explain select * from user where name like ‘zhangsan%’;
5)字符串不加單引號(hào)索引失效
explain select * from user where name = 2000;
6)or連接索引失效
explain select * from user where name = ‘2000’ or age = 20 or pos =‘cxy’;
7)order by
正常(索引參與了排序),沒有違反最左匹配原則呛凶。
explain select * from user where name = 'zhangsan' and age = 20 order by age,pos;
違反最左前綴法則男娄,導(dǎo)致額外的文件排序(會(huì)降低性能)。
explain select name,age from user where name = 'zhangsan' order by pos;
8)group by
正常(索引參與了排序)漾稀。
explain select name,age from user where name = 'zhangsan' group by age;
違反最左前綴法則模闲,導(dǎo)致產(chǎn)生臨時(shí)表(會(huì)降低性能)。
explain select name,age from user where name = 'zhangsan' group by pos,age;
五崭捍、總結(jié)
了解一條查詢語(yǔ)句是如何執(zhí)行的尸折,發(fā)現(xiàn)建立索引是一種可以高效查找的數(shù)據(jù)結(jié)構(gòu)。
了解了索引的各種分類情況殷蛇,聚集索引和非聚集索引的區(qū)別实夹,如何創(chuàng)建各種索引。
通過需求一步步分析出為什么MySQL要選b+tree作為索引的數(shù)據(jù)結(jié)構(gòu)粒梦,對(duì)比了btree和b+tree的區(qū)別亮航、 MyISAM和innodb中索引的區(qū)別。
了解了索引會(huì)失效的多種情況匀们,比較重要的最左匹配原則缴淋,相應(yīng)地我們可以在建索引的時(shí)候做一些優(yōu)化。
本文章參考了深入理解MysSQL索引