1、面試真題MySQ索引的原理和數(shù)據(jù)結構能介紹一下嗎？b+樹和b-樹有什么區(qū)別？MySQL聚簇索引和非聚簇索引的區(qū)別是什么？他們分別是如何存儲的？使用MySQL索引都有哪些原則？MySQL復合索引如何使用？2、面試官心理分析

數(shù)據(jù)庫是30k以內(nèi)的工程師面試必問的問題，而且如果問數(shù)據(jù)庫，一定是問mysql，N年前可能java工程師出去面試，oracle這塊的技能是殺手锏，現(xiàn)在已經(jīng)沒人說，會oracle是加分項了，現(xiàn)在都是熟悉大數(shù)據(jù)hadoop、hbase等技術是加分項。

3、面試題剖析（1）索引的數(shù)據(jù)結構是什么

其實就是讓你聊聊mysql的索引底層是什么數(shù)據(jù)結構實現(xiàn)的，弄不好現(xiàn)場還會讓你畫一畫索引的數(shù)據(jù)結構，然后會問問你mysql索引的常見使用原則，弄不好還會拿個SQL來問你，就這SQL建個索引一般咋建？

(資料圖片僅供參考)

至于索引是啥？這個問題太基礎了，大家都知道，mysql的索引說白了就是用一個數(shù)據(jù)結構組織某一列的數(shù)據(jù)，然后如果你要根據(jù)那一列的數(shù)據(jù)查詢的時候，就可以不用全表掃描，只要根據(jù)那個特定的數(shù)據(jù)結構去找到那一列的值，然后找到對應的行的物理地址即可。

那么回答面試官的一個問題，mysql的索引是怎么實現(xiàn)的？

答案是，不是二叉樹，也不是一顆亂七八糟的樹，而是一顆b+樹。這個很多人都會這么回答，然后面試官一定會追問，那么你能聊聊b+樹嗎？

但是說b+樹之前，咱們還是先來聊聊b-樹是啥，從數(shù)據(jù)結構的角度來看，b-樹要滿足下面的條件：

（1）d為大于1的一個正整數(shù)，稱為B-Tree的度。

（2）h為一個正整數(shù)，稱為B-Tree的高度。

（3）每個非葉子節(jié)點由n-1個key和n個指針組成，其中d<=n<=2d。

（4）每個葉子節(jié)點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節(jié)點的指針均為null 。

（5）所有葉節(jié)點具有相同的深度，等于樹高h。

（6）key和指針互相間隔，節(jié)點兩端是指針。

（7）一個節(jié)點中的key從左到右非遞減排列。

（8）所有節(jié)點組成樹結構。

（9）每個指針要么為null，要么指向另外一個節(jié)點。

（10）如果某個指針在節(jié)點node最左邊且不為null，則其指向節(jié)點的所有key小于v(key1)，其中v(key1)為node的第一個key的值。

（11）如果某個指針在節(jié)點node最右邊且不為null，則其指向節(jié)點的所有key大于v(keym)，其中v(keym)為node的最后一個key的值。

（12）如果某個指針在節(jié)點node的左右相鄰key分別是keyi和keyi+1且不為null，則其指向節(jié)點的所有key小于v(keyi+1)且大于v(keyi)。

上面那段規(guī)則，我也是從網(wǎng)上找的，說實話，沒幾個java程序員能耐心去看明白或者是背下來，大概知道是個樹就好了。就拿個網(wǎng)上的圖給大家示范一下吧：

比如說我們現(xiàn)在有一張表：

(id intname varcharage int)

我們現(xiàn)在對id建個索引：15、56、77、20、49

select * from table where id = 49select * from table where id = 15

反正大概就長上面那個樣子，查找的時候，就是從根節(jié)點開始二分查找。大概就知道這個是事兒就好了，深講里面的數(shù)學問題和算法問題，時間根本不夠，面試官也沒指望你去講里面的數(shù)學和算法問題，因為我估計他自己也不一定能記住。

好了，b-樹就說到這里，直接看下一個，b+樹。b+樹是b-樹的變種，啥叫變種？就是說一些原則上不太一樣了，稍微有點變化，同樣的一套數(shù)據(jù)，放b-樹和b+樹看著排列不太一樣的。而mysql里面一般就是b+樹來實現(xiàn)索引，所以b+樹很重要。

b+樹跟b-樹不太一樣的地方在于：

每個節(jié)點的指針上限為2d而不是2d+1。內(nèi)節(jié)點不存儲data，只存儲key；葉子節(jié)點不存儲指針。

這圖我就不自己畫了，網(wǎng)上弄個圖給大家瞅一眼：

select * from table where id = 15select * from table where id>=18 and id<=49

但是一般數(shù)據(jù)庫的索引都對b+樹進行了優(yōu)化，加了順序訪問的指針，如網(wǎng)上弄的一個圖，這樣在查找范圍的時候，就很方便，比如查找18~49之間的數(shù)據(jù)：

其實到這里，你就差不多了，你自己仔細看看上面兩個圖，b-樹和b+樹都現(xiàn)場畫一下，然后給說說區(qū)別，和通過b+樹查找的原理即可。

接著來聊點稍微高級點的，因為上面說的只不過都是最基礎和通用的b-樹和b+樹罷了，但是mysql里不同的存儲引擎對索引的實現(xiàn)是不同的。

（2）myism存儲引擎的索引實現(xiàn)

先來看看myisam存儲引擎的索引實現(xiàn)。就拿上面那個圖，咱們來現(xiàn)場手畫一下這個myisam存儲的索引實現(xiàn)，在myisam存儲引擎的索引中，每個葉子節(jié)點的data存放的是數(shù)據(jù)行的物理地址，比如0x07之類的東西，然后我們可以畫一個數(shù)據(jù)表出來，一行一行的，每行對應一個物理地址。

索引文件

id=15，data：0x07，0a89，數(shù)據(jù)行的物理地址。

數(shù)據(jù)文件單獨放一個文件。

select * from table where id = 15 -> 0x07物理地址 -> 15，張三，22。

myisam最大的特點是數(shù)據(jù)文件和索引文件是分開的，大家看到了么，先是索引文件里搜索，然后到數(shù)據(jù)文件里定位一個行的。

（3）innodb存儲引擎的索引

好了，再來看看innodb存儲引擎的索引實現(xiàn)，跟myisam最大的區(qū)別在于說，innodb的數(shù)據(jù)文件本身就是個索引文件，就是主鍵key，然后葉子節(jié)點的data就是那個數(shù)據(jù)的所在行。我們還是用上面那個索引起來現(xiàn)場手畫一下這個索引好了，給大家來感受一下。

innodb存儲引擎，要求必須有主鍵，會根據(jù)主鍵建立一個默認索引，叫做聚簇索引，innodb的數(shù)據(jù)文件本身同時也是個索引文件，索引存儲結構大致如下：

15，data：0x07，完整的一行數(shù)據(jù)，（15,張三,22）。

22，data：完整的一行數(shù)據(jù)，（22,李四,30）。

就是因為這個原因，innodb表是要求必須有主鍵的，但是myisam表不要求必須有主鍵。另外一個是，innodb存儲引擎下，如果對某個非主鍵的字段創(chuàng)建個索引，那么最后那個葉子節(jié)點的值就是主鍵的值，因為可以用主鍵的值到聚簇索引里根據(jù)主鍵值再次查找到數(shù)據(jù)，即所謂的回表，例如：

select * from table where name = ‘張三’。

先到name的索引里去找，找到張三對應的葉子節(jié)點，葉子節(jié)點的data就是那一行的主鍵，id=15，然后再根據(jù)id=15，到數(shù)據(jù)文件里面的聚簇索引（根據(jù)主鍵組織的索引）根據(jù)id=15去定位出來id=15這一行的完整的數(shù)據(jù)

所以這里就明白了一個道理，為啥innodb下不要用UUID生成的超長字符串作為主鍵？因為這么玩兒會導致所有的索引的data都是那個主鍵值，最終導致索引會變得過大，浪費很多磁盤空間。

還有一個道理，一般innodb表里，建議統(tǒng)一用auto_increment自增值作為主鍵值，因為這樣可以保持聚簇索引直接加記錄就可以，如果用那種不是單調(diào)遞增的主鍵值，可能會導致b+樹分裂后重新組織，會浪費時間。

（4）索引的使用規(guī)則

一般來說跳槽時候，索引這塊必問，b+樹索引的結構，一般是怎么存放的，出個題，針對這個SQL，索引應該怎么來建立

select * from table where a=1 and b=2 and c=3，你知道不知道，你要怎么建立索引，才可以確保這個SQL使用索引來查詢

好了，各位同學，聊到這里，你應該知道具體的myisam和innodb索引的區(qū)別了，同時也知道什么是聚簇索引了，現(xiàn)場手畫畫，應該都ok了。然后我們再來說幾個最最基本的使用索引的基本規(guī)則。

其實最基本的，作為一個java碼農(nóng)，你得知道最左前綴匹配原則，這個東西是跟聯(lián)合索引（復合索引）相關聯(lián)的，就是說，你很多時候不是對一個一個的字段分別搞一個一個的索引，而是針對幾個索引建立一個聯(lián)合索引的。

給大家舉個例子，你如果要對一個商品表按照店鋪、商品、創(chuàng)建時間三個維度來查詢，那么就可以創(chuàng)建一個聯(lián)合索引：shop_id、product_id、gmt_create

一般來說，你有一個表（product）：shop_id、product_id、gmt_create，你的SQL語句要根據(jù)這3個字段來查詢，所以你一般來說不是就建立3個索引，一般來說會針對平時要查詢的幾個字段，建立一個聯(lián)合索引

后面在java系統(tǒng)里寫的SQL，都必須符合最左前綴匹配原則，確保你所有的sql都可以使用上這個聯(lián)合索引，通過索引來查詢

create index (shop_id,product_id,gmt_create)

（1）全列匹配

這個就是說，你的一個sql里，正好where條件里就用了這3個字段，那么就一定可以用到這個聯(lián)合索引的：

select * from product where shop_id=1 and product_id=1 and gmt_create=’2018-01-01 10:00:00’

（2）最左前綴匹配

這個就是說，如果你的sql里，正好就用到了聯(lián)合索引最左邊的一個或者幾個列表，那么也可以用上這個索引，在索引里查找的時候就用最左邊的幾個列就行了：

select * from product where shop_id=1 and product_id=1，這個是沒問題的，可以用上這個索引的。

（3）最左前綴匹配了，但是中間某個值沒匹配

這個是說，如果你的sql里，就用了聯(lián)合索引的第一個列和第三個列，那么會按照第一個列值在索引里找，找完以后對結果集掃描一遍根據(jù)第三個列來過濾，第三個列是不走索引去搜索的，就是有一個額外的過濾的工作，但是還能用到索引，所以也還好，例如：

select * from product where shop_id=1 and gmt_create=’2018-01-01 10:00:00’

就是先根據(jù)shop_id=1在索引里找，找到比如100行記錄，然后對這100行記錄再次掃描一遍，過濾出來gmt_create=’2018-01-01 10:00:00’的行。

這個我們在線上系統(tǒng)經(jīng)常遇到這種情況，就是根據(jù)聯(lián)合索引的前一兩個列按索引查，然后后面跟一堆復雜的條件，還有函數(shù)啥的，但是只要對索引查找結果過濾就好了，根據(jù)線上實踐，單表幾百萬數(shù)據(jù)量的時候，性能也還不錯的，簡單SQL也就幾ms，復雜SQL也就幾百ms。可以接受的。

（4）沒有最左前綴匹配

那就不行了，那就在搞笑了，一定不會用索引，所以這個錯誤千萬別犯。

select * from product where product_id=1，這個肯定不行。

（5）前綴匹配

這個就是說，如果你不是等值的，比如=，>=，<=的操作，而是like操作，那么必須要是like ‘XX%’這種才可以用上索引，比如說：

select * from product where shop_id=1 and product_id=1 and gmt_create like ‘2018%’

（6）范圍列匹配

如果你是范圍查詢，比如>=，<=，between操作，你只能是符合最左前綴的規(guī)則才可以范圍，范圍之后的列就不用索引了。

select * from product where shop_id>=1 and product_id=1

這里就在聯(lián)合索引中根據(jù)shop_id來查詢了。

（7）包含函數(shù)

如果你對某個列用了函數(shù)，比如substring之類的東西，那么那一列不用索引。

select * from product where shop_id=1 and 函數(shù)(product_id) = 2

上面就根據(jù)shop_id在聯(lián)合索引中查詢

（5）索引的缺點以及使用注意

索引是有缺點的，比如常見的就是會增加磁盤消耗，因為要占用磁盤文件，同時高并發(fā)的時候頻繁插入和修改索引，會導致性能損耗的。

我們給的建議，盡量創(chuàng)建少的索引，比如說一個表一兩個索引，兩三個索引，十來個，20個索引，高并發(fā)場景下還可以。

字段，status，100行，status就2個值，0和1。

你覺得你建立索引還有意義嗎？幾乎跟全表掃描都差不多了。

select * from table where status=1，相當于是把100行里的50行都掃一遍。

你有個id字段，每個id都不太一樣，建立個索引，這個時候其實用索引效果就很好，你比如為了定位到某個id的行，其實通過索引二分查找，可以大大減少要掃描的數(shù)據(jù)量，性能是非常好的。

在創(chuàng)建索引的時候，要注意一個選擇性的問題，select count(discount(col)) / count(*)，就可以看看選擇性，就是這個列的唯一值在總行數(shù)的占比，如果過低，就代表這個字段的值其實都差不多，或者很多行的這個值都類似的，那創(chuàng)建索引幾乎沒什么意義，你搜一個值定位到一大坨行，還得重新掃描。

就是要一個字段的值幾乎都不太一樣，此時用索引的效果才是最好的。

還有一種特殊的索引叫做前綴索引，就是說，某個字段是字符串，很長，如果你要建立索引，最好就對這個字符串的前綴來創(chuàng)建，比如前10個字符這樣子，要用前多少位的字符串創(chuàng)建前綴索引，就對不同長度的前綴看看選擇性就好了，一般前綴長度越長選擇性的值越高。

好了，各位同學，索引這塊能聊到這個程度，或者掌握到這個程度，其實普通的互聯(lián)網(wǎng)系統(tǒng)中，80%的活兒都可以干了，因為在互聯(lián)網(wǎng)系統(tǒng)中，一般就是盡量降低SQL的復雜度，讓SQL非常簡單就可以了，然后搭配上非常簡單的一個主鍵索引（聚簇索引）+ 少數(shù)幾個聯(lián)合索引，就可以覆蓋一個表的所有SQL查詢需求了。更加復雜的業(yè)務邏輯，讓java代碼里來實現(xiàn)就ok了。

大家要明白，SQL達到95%都是單表增刪改查，如果你有一些join等邏輯，就放在java代碼里來做。SQL越簡單，后續(xù)遷移分庫分表、讀寫分離的時候，成本越低，幾乎都不用怎么改造SQL。

我這里給大家說下，互聯(lián)網(wǎng)公司而言，用MySQL當最牛的在線即時的存儲，存數(shù)據(jù)，簡單的取出來；不要用MySQL來計算，不要寫join、子查詢、函數(shù)放MySQL里來計算，高并發(fā)場景下；計算放java內(nèi)存里，通過寫java代碼來做；可以合理利用mysql的事務支持。

關鍵詞： 聚簇索引 數(shù)據(jù)結構 數(shù)據(jù)文件 物理地址