表妹去面試被問到索引，結(jié)果梅開二度

hello大家好 我是大家的學(xué)習(xí)成長(zhǎng)小伙伴Captain

表妹：親愛的面試官，感謝您上次能夠理解我家中的雞蛋，而且還不計(jì)前嫌，再一次給我面試的機(jī)會(huì)，這次我一定好好抓住

面試官：嗯行，挺好，上次我們聊到了數(shù)據(jù)mysql，聊了下索引，感覺你也不是很熟悉的樣子，那我們換個(gè)角度吧

表妹：啊啊啊??！好的，親愛的面試官(本來(lái)都好好準(zhǔn)備了引擎了，結(jié)果不問了，放馬過來(lái)吧

面試官：你說(shuō)說(shuō)平時(shí)你是怎么解決慢查詢，怎么加速SQL查詢的

表妹：簡(jiǎn)單啊，加索引，用啥查就加啥索引就可以了

面試官：還有嗎，就這些嗎

表妹：就這些啊(天真的眼神看著面試官

面試官：那你說(shuō)說(shuō)索引都有哪些啊，底層都是怎么存儲(chǔ)的，怎么加速查詢的

表妹：我比較熟悉的索引就主鍵索引、普通索引、唯一索引和Hash索引，底層存儲(chǔ)結(jié)構(gòu)就是兩種B+樹和Hash（Innodb引擎），加速查詢主要是由于B+樹的特殊結(jié)構(gòu)，可以降低樹的層次減少IO次數(shù)，就可以查詢出數(shù)據(jù)

而Hash存儲(chǔ)就是和HashMap一樣的，這種的查詢優(yōu)點(diǎn)就是善于單值查詢，缺點(diǎn)就是不擅長(zhǎng)區(qū)間查詢，而B+樹便可以解決這個(gè)問題

面試官：不錯(cuò)，你能給我分析一下B+樹為什么可以解決區(qū)間查詢嗎

表妹：（壞了，這個(gè)昨天光吃雞蛋了，忘了問了）那個(gè)，面試官，我突然想起來(lái)，家里還有幾塊紫薯在煮著，我得趕緊回去，要不紫薯變黑薯了

面試官：行吧，你先回去吧，下次再繼續(xù)面試，這次記得把該關(guān)的都關(guān)完了

? ? ? ? ? ? ? ?

于是乎，表妹回來(lái)了，以質(zhì)問的語(yǔ)氣問我：喂，你這家伙，昨天怎么給我講索引的時(shí)候，沒給我說(shuō)索引的底層的B+樹的原理啊，害的我今天出丑

這不能怪我啊，你問我的時(shí)候，我本來(lái)想繼續(xù)給你講下去的，可是你卻一直在那里吃雞蛋，吃著雞蛋還看著魷魚游戲，光喊一二三木頭人了，你都沒尋思聽我講話了誒

算了算了，我就不責(zé)怪你了，你今天必須把索引給我講明白，不講明白今天沒玩，妹妹看似很生氣的說(shuō)到

索引種類

主鍵索引

?

主鍵索引，不允許null，這個(gè)是底層構(gòu)建B+樹的依據(jù)，可以提高查詢效率，并提供唯一性約束，一張表中只能有一個(gè)主鍵，被標(biāo)志為自動(dòng)增長(zhǎng)的字段一定是主鍵，但是主鍵并不一定自動(dòng)增長(zhǎng)，一般把主鍵定義在無(wú)意義的字段上，主鍵的數(shù)據(jù)類型也最好是數(shù)值

?

B+樹的構(gòu)建就是根據(jù)主鍵索引來(lái)構(gòu)建，如果我們未指定主鍵，MySQL會(huì)自動(dòng)創(chuàng)建一個(gè)列來(lái)作為主鍵索引

?

普通索引

?

最普通的索引，沒有任何限制，該唯一索引指向的是主鍵索引，通過唯一索引找到主鍵索引，然后去主鍵索引構(gòu)建的B+樹中回表查詢具體數(shù)據(jù)，如果只需要主鍵字段，則不需要回表即可滿足條件

?

唯一索引

?

特性就是唯一，可以為null，可以把唯一性約束放在一個(gè)或者多個(gè)列上，這些列或列的組合必須有唯一的。但是，唯一性約束所在的列并不是表的主鍵列。

?

唯一性約束強(qiáng)制在指定的列上創(chuàng)建一個(gè)唯一性索引。在默認(rèn)情況下，創(chuàng)建唯一性的非聚簇索引，但是，也可以指定所創(chuàng)建的索引是聚簇索引。

?

存在唯一鍵沖突的時(shí)候的避免策略

?

insert ignore

?

會(huì)忽略數(shù)據(jù)庫(kù)中已經(jīng)存在的數(shù)據(jù)(根據(jù)主鍵或者唯一索引判斷)，如果數(shù)據(jù)庫(kù)沒有數(shù)據(jù)，就插入新的數(shù)據(jù)，如果有數(shù)據(jù)的話就跳過這條數(shù)據(jù).

?

replace into

?

首先嘗試插入數(shù)據(jù)到表中。如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)(根據(jù)主鍵或者唯一索引判斷)則先刪除此行數(shù)據(jù)，然后插入新的數(shù)據(jù)，否則，直接插入新數(shù)據(jù)。使用replace into，你必須具有delete和insert權(quán)限

?

insert on duplicate key update

?

如果在insert into 語(yǔ)句末尾指定了on duplicate key update，并且插入行后會(huì)導(dǎo)致在一個(gè)UNIQUE索引或PRIMARY KEY中出現(xiàn)重復(fù)值，則在出現(xiàn)重復(fù)值的行執(zhí)行UPDATE；如果不會(huì)導(dǎo)致重復(fù)的問題，則插入新行，跟普通的insert into一樣。使用insert into，你必須具有insert和update權(quán)限

?

如果有新記錄被插入，則受影響行的值顯示1；如果原有的記錄被更新，則受影響行的值顯示2；如果記錄被更新前后值是一樣的，則受影響行數(shù)的值顯示0

?

全文索引

?

fulltext索引跟其它索引大不相同，它更像是一個(gè)搜索引擎，而不是簡(jiǎn)單的where語(yǔ)句的參數(shù)匹配。fulltext索引配合match against操作使用，而不是一般的where語(yǔ)句加like

?

MySQL可以通過建立全文索引，利用查詢關(guān)鍵字和查詢列內(nèi)容之間的相關(guān)度進(jìn)行檢索，可以利用全文索引來(lái)提高匹配的速度。比如實(shí)現(xiàn)全匹配模糊查詢。

?

mysql的全文索引性能非常不穩(wěn)定，不建議生產(chǎn)環(huán)境使用。需要使用全文檢索的地方，建議使用ES

?

空間索引

?

MyISAM 存儲(chǔ)引擎支持空間數(shù)據(jù)索引R樹，可以用于地理數(shù)據(jù)存儲(chǔ)?？臻g數(shù)據(jù)索引會(huì)從所有維度來(lái)索引數(shù)據(jù)，可以有效地使用任意維度來(lái)進(jìn)行組合查詢。

?

組合索引

多個(gè)字段上創(chuàng)建的索引，只有在查詢條件中使用了創(chuàng)建索引時(shí)的第一個(gè)字段，索引才會(huì)被使用。使用組合索引時(shí)遵循最左前綴集合

索引的優(yōu)缺點(diǎn)

?

大大加速數(shù)據(jù)的檢索速度

?

減少磁盤IO，最根本也是提高了速度

?

創(chuàng)建和維護(hù)索引需要耗費(fèi)時(shí)間，表中的數(shù)據(jù)進(jìn)行增加、修改和刪除的時(shí)候，索引也需要?jiǎng)討B(tài)維護(hù)

?

索引需要占據(jù)額外的存儲(chǔ)空間，所以這并不意味著索引越多越好，有些小表可能進(jìn)行全表掃描速度更快，因?yàn)槭褂盟饕枰M(jìn)行回表查詢，就是先通過索引找到主鍵索引，再通過主鍵索引去構(gòu)建的B+樹中去查找整條數(shù)據(jù)

索引底層結(jié)構(gòu)

我們就分析最常用的兩種索引結(jié)構(gòu)B+樹索引和Hash索引，而myisam和innodb引擎中的B+樹又是有點(diǎn)區(qū)別的，這個(gè)我們下面會(huì)介紹

在了解B+樹之前，先看下B樹

B樹

?

B樹，多路查找樹，體態(tài)矮胖，可以更少的進(jìn)行磁盤IO，想象一下，樹的每一層代表一次磁盤IO

?

描述一棵B樹時(shí)需要指定它的階數(shù)，階數(shù)表示了一個(gè)節(jié)點(diǎn)最多有多少的孩子節(jié)點(diǎn)，一般使用字母m表示階數(shù)。

當(dāng)m取2時(shí)，就是我們常見的二叉搜索樹。

?

一棵m階的B數(shù)定義如下：

?

（1）每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字

（2）根節(jié)點(diǎn)最少可以只有一個(gè)關(guān)鍵字

（3）非根節(jié)點(diǎn)至少有Math.ceil(m/2)-1個(gè)關(guān)鍵字

（4）每個(gè)節(jié)點(diǎn)的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它

（5）所有葉子節(jié)點(diǎn)都位于同一層，或者說(shuō)根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑長(zhǎng)度都相同

B樹，最大的優(yōu)點(diǎn)就是比平常的二叉樹更矮胖，而這樣就可以利用更矮胖的結(jié)構(gòu)存儲(chǔ)更多的數(shù)據(jù)，這樣也就會(huì)讓IO次數(shù)減少，B樹的特點(diǎn)在于葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都會(huì)存儲(chǔ)數(shù)據(jù)，而存儲(chǔ)的是不同的數(shù)據(jù)，這也就意味著整棵樹會(huì)組成全量的數(shù)據(jù)

也就是可能還沒有查詢到最底層就可能已經(jīng)拿到想要的數(shù)據(jù)了，不僅存儲(chǔ)著數(shù)據(jù)，還起著索引的結(jié)構(gòu)

?

B+樹

?

B+樹是對(duì)B樹的變形，最大的區(qū)別是非葉子節(jié)點(diǎn)不保存數(shù)據(jù)，而只用于存儲(chǔ)索引，所有的數(shù)據(jù)都保存到葉子節(jié)點(diǎn)中

?

B樹是所有節(jié)點(diǎn)（包含葉子節(jié)點(diǎn)）組成了所有的數(shù)據(jù)，而B+樹是所有數(shù)據(jù)均存儲(chǔ)到葉子節(jié)點(diǎn)上

?

同時(shí)B+樹的所有葉子節(jié)點(diǎn)都有相鄰葉子節(jié)點(diǎn)的指針，也就是所有葉子節(jié)點(diǎn)組成了一個(gè)鏈表

看到這兩句話，不知道大家有沒有一種豁然開朗的感覺嘞

第一句，所有數(shù)據(jù)都存儲(chǔ)到葉子節(jié)點(diǎn)，而非葉子節(jié)點(diǎn)都不會(huì)存儲(chǔ)相應(yīng)的全部數(shù)據(jù)，也就是mysql一張表的一條數(shù)據(jù)，非葉子節(jié)點(diǎn)都只會(huì)存儲(chǔ)其中的一個(gè)索引字段，而不是該對(duì)象的所有字段

這意味著什么呢，這也就意味著每個(gè)相同存儲(chǔ)大小的節(jié)點(diǎn)，可以存儲(chǔ)更多的索引數(shù)據(jù)了，比如一個(gè)節(jié)點(diǎn)1KB，按照B樹只能存儲(chǔ)100條數(shù)據(jù)，而按照B樹可以存儲(chǔ)1000條數(shù)據(jù)，造成的直接后果就是這個(gè)樹變得更矮更胖了！

明白了不，更矮更胖也就意味著可以通過更少的IO次數(shù)來(lái)獲得想要的數(shù)據(jù)

第二句，B+樹的所有葉子節(jié)點(diǎn)都有相鄰葉子節(jié)點(diǎn)的指針，也就是所有葉子節(jié)點(diǎn)組成了一個(gè)鏈表，這樣做的優(yōu)點(diǎn)就是支持范圍查詢，再回想一下B樹的結(jié)構(gòu)，B樹也不是不支持范圍查詢，而是會(huì)效率很低，它需要來(lái)回的IO，才能把周圍的數(shù)據(jù)都找出來(lái)，這樣是很糟糕的設(shè)計(jì)

而B+樹的結(jié)構(gòu)就可以直接通過底層的指針便可以找到周邊的數(shù)據(jù)了，就是一個(gè)排好序的鏈表，只需要找到其中的部分的有序數(shù)據(jù)，只需要找到開頭和結(jié)尾便可以確定所有的數(shù)據(jù)了

關(guān)于數(shù)據(jù)結(jié)構(gòu)，這里我給大家推薦一個(gè)網(wǎng)站，可以學(xué)習(xí)下各種數(shù)據(jù)結(jié)構(gòu)，觀看數(shù)據(jù)組成原理：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

B樹和B+樹的對(duì)比

?

B+樹的磁盤IO更低，查詢效率更高

?

B+樹的非葉子節(jié)點(diǎn)并不會(huì)存儲(chǔ)整條數(shù)據(jù)，而是存儲(chǔ)數(shù)據(jù)的索引，這句話是針對(duì)于MySQL表來(lái)說(shuō)，因此非葉子節(jié)點(diǎn)可以用同樣的存儲(chǔ)空間，存儲(chǔ)更多的索引數(shù)據(jù)，也就使得B+樹更加的矮胖，可以一次性讀入內(nèi)存中的關(guān)鍵字也就越多，磁盤的IO次數(shù)也就降低了，查詢效率也就更高

?

查詢效率更加穩(wěn)定

?

非葉子節(jié)點(diǎn)并不是最終指向文件內(nèi)容的節(jié)點(diǎn)，也就意味著如果需要獲取更多數(shù)據(jù)，都需要通過非葉子節(jié)點(diǎn)索引找到葉子節(jié)點(diǎn)，也就是任何關(guān)鍵字的查找都需要走一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，所以查詢效率也更加穩(wěn)定

?

B+樹遍歷效率更高

?

由于B+樹特有的結(jié)構(gòu)，只需要遍歷所有葉子節(jié)點(diǎn)的數(shù)據(jù)便可以實(shí)現(xiàn)整棵樹的遍歷

?

B+樹更好的支持范圍查詢

?

范圍查詢?cè)诂F(xiàn)在系統(tǒng)中是必不可少的，B+樹的葉子節(jié)點(diǎn)都有相應(yīng)的指針指向前后節(jié)點(diǎn)，組成鏈表，所以更好的支持范圍查詢。而B樹效率則會(huì)很低

上面說(shuō)了這么多種樹，為的就是給大家理解mysql底層索引和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)跟上Captain的步伐，繼續(xù)沖

Hash索引

上面這是大家最熟悉的HashMap的結(jié)構(gòu)，就是通過數(shù)組+鏈表的形式來(lái)存儲(chǔ)數(shù)據(jù)，存儲(chǔ)數(shù)據(jù)的方式就是通過對(duì)每一個(gè)數(shù)據(jù)進(jìn)行Hash運(yùn)算，通過Hash運(yùn)算就可以得到一個(gè)位置的數(shù)據(jù)，我們當(dāng)然也需要根據(jù)數(shù)組的大小來(lái)鎖定這個(gè)Hash取值的范圍

比如我們數(shù)組大小是16，我們就可以通過Hash運(yùn)算得到一個(gè)這個(gè)范圍的數(shù)據(jù)，然后把這個(gè)數(shù)據(jù)放到相應(yīng)的數(shù)組的位置，如果該位置為空，就直接把數(shù)據(jù)放到這里。而不為空，就涉及到hash沖突的處理了，這里就不多講了，就是以數(shù)組元素作為鏈表的頭節(jié)點(diǎn)往后延伸鏈表

哈希索引，存儲(chǔ)結(jié)構(gòu)就是這種，而這種的最大優(yōu)點(diǎn)就是查詢速度非?？欤樵儚?fù)雜度O(1)，查詢方式就是通過計(jì)算查詢索引的hash值，直接找到數(shù)組位置即可，然后按照數(shù)組位置進(jìn)行一個(gè)一個(gè)的對(duì)比，直到找到相應(yīng)的索引就行

所以啊，最快的就是直接數(shù)組第一個(gè)元素就是，直接就找出來(lái)了，否則的話，就一個(gè)一個(gè)對(duì)比下，直到找到即可

自適應(yīng)哈希索引

在mysql中還有一個(gè)自適應(yīng)哈希索引，這個(gè)東西是mysql自己內(nèi)部?jī)?yōu)化的，我們無(wú)法操作這個(gè)

在使用B+樹的時(shí)候，每個(gè)數(shù)據(jù)都需要經(jīng)過多次的IO進(jìn)行查詢，如果某些數(shù)據(jù)需要經(jīng)常性的訪問到，那這些數(shù)據(jù)就會(huì)被放到innodb的buffer pool中

哎，放到buffer pool中，放到buffer pool中我們下次直接取就可以了，關(guān)自適應(yīng)哈希索引什么事情啊

我們知道數(shù)據(jù)的讀取都是以頁(yè)page為單位的，所以buffer pool中緩存數(shù)據(jù)的時(shí)候也是存儲(chǔ)的數(shù)據(jù)所在的頁(yè)，并不是只緩存相應(yīng)的數(shù)據(jù)，那這部分緩存的數(shù)據(jù)也是緩存的頁(yè)，那每次查詢的時(shí)候還是得從緩存中通過B+樹中查詢，所以這樣也是可以優(yōu)化的

經(jīng)常使用的數(shù)據(jù)就直接把相應(yīng)的數(shù)據(jù)的位置放到自適應(yīng)哈希索引中即可了，下一次再查詢的時(shí)候就不需要再去緩存中通過B+數(shù)的結(jié)構(gòu)把數(shù)據(jù)給挖出來(lái)