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

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

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

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

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

面試官：你說說平時你是怎么解決慢查詢，怎么加速SQL查詢的

表妹：簡單啊，加索引，用啥查就加啥索引就可以了

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

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

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

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

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

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

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

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

? ? ? ? ? ? ? ?

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

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

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

索引種類

主鍵索引

?

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

?

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

?

普通索引

?

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

?

唯一索引

?

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

?

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

?

存在唯一鍵沖突的時候的避免策略

?

insert ignore

?

會忽略數(shù)據(jù)庫中已經(jīng)存在的數(shù)據(jù)(根據(jù)主鍵或者唯一索引判斷)，如果數(shù)據(jù)庫沒有數(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 語句末尾指定了on duplicate key update，并且插入行后會導(dǎo)致在一個UNIQUE索引或PRIMARY KEY中出現(xiàn)重復(fù)值，則在出現(xiàn)重復(fù)值的行執(zhí)行UPDATE；如果不會導(dǎo)致重復(fù)的問題，則插入新行，跟普通的insert into一樣。使用insert into，你必須具有insert和update權(quán)限

?

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

?

全文索引

?

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

?

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

?

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

?

空間索引

?

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

?

組合索引

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

索引的優(yōu)缺點

?

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

?

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

?

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

?

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

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

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

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

B樹

?

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

?

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

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

?

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

?

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

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

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

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

（5）所有葉子節(jié)點都位于同一層，或者說根節(jié)點到每個葉子節(jié)點的路徑長度都相同

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

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

?

B+樹

?

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

?

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

?

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

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

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

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

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

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

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

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

B樹和B+樹的對比

?

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

?

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

?

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

?

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

?

B+樹遍歷效率更高

?

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

?

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

?

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

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

Hash索引

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

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

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

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

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

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

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

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

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

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