年輕人不講武德，刁難Java面試官：B+樹如何實現(xiàn)索引？最后還面過了！簡直就是奇跡！
前言
事情的經(jīng)過是這樣的：
電面試官問我什么是B+樹，我說用的不多，只知道是一種樹數(shù)據(jù)結(jié)構(gòu)。
然后面試官問我怎么實現(xiàn)索引的？我答不出來，就下一題了。
最后問的差不多了，面試官問我，你還有什么想問我的?
我本著每次面試都算是學(xué)習(xí)的心態(tài)就問了句：B+樹怎么實現(xiàn)索引的?
沒想到面試官…支支吾吾半天也答不上來，然后說太久了都忘了。
得虧當(dāng)時是電面，要不然我都不知道用什么樣的表情面對面試官！哈哈哈！
我覺得面試官當(dāng)時肯定心想：年輕人不講武德，偷襲我69歲面試官？
最后知道電面過的時候，我覺得這簡直就是個奇跡！
不過愛學(xué)習(xí)的我當(dāng)然不會就此罷休，接下來就整理總結(jié)了B+數(shù)索引實戰(zhàn)的全過程，同樣的坑絕對不能摔倒兩次！
文章末尾也為大家準(zhǔn)備好了Java學(xué)習(xí)資料，千萬不要錯過哦！
索引的代價
空間上的代價
一個索引都為對應(yīng)一棵B+樹，樹中每一個節(jié)點都是一個數(shù)據(jù)頁，一個頁默認(rèn)會占用16KB的存儲空間，所以一個索引也是會占用磁盤空間的。
時間上的代價
索引是對數(shù)據(jù)的排序，那么當(dāng)對表中的數(shù)據(jù)進(jìn)行增、刪、改操作時，都需要去維護(hù)修改內(nèi)容涉及到的B+樹索引。
所以在進(jìn)行增、刪、改操作時可能需要額外的時間進(jìn)行一些記錄移動，頁面分裂、頁面回收等操作來維護(hù)好排
序。
B+樹索引實戰(zhàn)
全職匹配
select * from t1 where b = 1 and c = 1 and d = 1;
查詢優(yōu)化器會分析這些查詢條件并且按照可以使用的索引中列的順序來決定先使用哪個查詢條件。
匹配左邊的列
select * from t1 where b = 1;select * from t1 where b = 1 and c = 1;
下面這個sql是用不到索引的
select * from t1 where c = 1;
因為B+樹先是按照b列的值排序的，在b列的值相同的情況下才使用c列進(jìn)行排序，也就是說b列的值不同的記錄
中c的值可能是無序的。而現(xiàn)在你跳過b列直接根據(jù)c的值去查找，這是做不到的。
匹配列前綴
如果只給出后綴或者中間的某個字符串，比如：
select * from t1 where b like '%101%';
這種是用不到索引的，因為字符串中間有’101’的字符串并沒有排好序，所以只能全表掃描了。有時候我們有一些匹配某些字符串后綴的需求，比方說某個表有一個url列，該列中存儲了許多url：
www.baidu.com
www.google.com
www.qq.com
假設(shè)已經(jīng)對該url列創(chuàng)建了索引，如果我們想查詢以com為后綴的網(wǎng)址的話可以這樣寫查詢條件：WHERE url LIKE'%com'，但是這樣的話無法使用該url列的索引。為了在查詢時用到這個索引而不至于全表掃描，我們可以把后綴查詢改寫成前綴查詢，不過我們就得把表中的數(shù)據(jù)全部逆序存儲一下，也就是說我們可以這樣保存url列中的數(shù)據(jù)：
moc.udiab.www
moc.elgoog.www
moc.qq.www
這樣再查找以com為后綴的網(wǎng)址時搜索條件便可以這么寫：WHERE url LIKE 'moc%'，這樣就可以用到索引了。
匹配范圍值
select * from t1 where b > 1 and b < 20000;
由于B+樹中的數(shù)據(jù)頁和記錄是先按b列排序的，所以我們上邊的查詢過程其實是這樣的：
找到b值為1的記錄。
找到b值為20000的記錄。
由于所有記錄都是由鏈表連起來的（記錄之間用單鏈表，數(shù)據(jù)頁之間用雙鏈表），所以他們之間的記錄都可以很容易的取出來
找到這些記錄的主鍵值，再到聚簇索引中回表查找完整的記錄。
不過在使用聯(lián)合進(jìn)行范圍查找的時候需要注意，如果對多個列同時進(jìn)行范圍查找的話，只有對索引最左邊的那個列進(jìn)行范圍查找的時候才能用到B+樹索引，比如：
select * from t1 where b > 1 and c > 1;
上邊這個查詢可以分成兩個部分：
通過條件b > 1來對b進(jìn)行范圍，查找的結(jié)果可能有多條b值不同的記錄，
對這些b值不同的記錄繼續(xù)通過c > 1繼續(xù)過濾。
這樣子對于聯(lián)合索引來說，只能用到b列的部分，而用不到c列的部分，因為只有b值相同的情況下才能用c列的值進(jìn)行排序，而這個查詢中通過b進(jìn)行范圍查找的記錄中可能并不是按照c列進(jìn)行排序的，所以在搜索條件中繼續(xù)以c列進(jìn)行查找時是用不到這個B+樹索引的。
精確匹配某一列并范圍匹配另外一列
對于同一個聯(lián)合索引來說，雖然對多個列都進(jìn)行范圍查找時只能用到最左邊那個索引列，但是如果左邊的列是精確查找，則右邊的列可以進(jìn)行范圍查找，比方說這樣：
select * from t1 where b = 1 and c > 1;
排序
select * from t1 order by b, c, d;
這個查詢的結(jié)果集需要先按照b值排序，如果記錄的b值相同，則需要按照c來排序，如果c的值相同，則需要按照d排序。因為這個B+樹索引本身就是按照上述規(guī)則排好序的，所以直接從索引中提取數(shù)據(jù)，然后進(jìn)行回表操作取出該索引中不包含的列就好了。
分組
select b, c, d, count(*) from t1 group by b, c, d;
這個查詢語句相當(dāng)于做了3次分組操作：
先把記錄按照b值進(jìn)行分組，所有b值相同的記錄劃分為一組。
將每個b值相同的分組里的記錄再按照c的值進(jìn)行分組，將title值相同的記錄放到一個分組里。
再將上一步中產(chǎn)生的分組按照d的值分成更小的分組。
如果沒有索引的話，這個分組過程全部需要在內(nèi)存里實現(xiàn)，而如果有索引的話，正好這個分組順序又和B+樹中的索引列的順序是一致的，所以可以直接使用B+樹索引進(jìn)行分組。
使用聯(lián)合索引進(jìn)行排序或分組的注意事項
對于聯(lián)合索引有個問題需要注意，ORDER BY的子句后邊的列的順序也必須按照索引列的順序給出，如果給出order by c, b, d?的順序，那也是用不了B+樹索引的。
同理，?order by b?order by b, c?這種匹配索引左邊的列的形式可以使用部分的B+樹索引。當(dāng)聯(lián)合索引左邊列的值為常量，也可以使用后邊的列進(jìn)行排序，比如這樣：
select * from t1 where b = 1 order by c, d;
這個查詢能使用聯(lián)合索引進(jìn)行排序是因為b列的值相同的記錄是按照c, d排序的。
不可以使用索引進(jìn)行排序或分組的幾種情況
ASC、DESC混用
對于使用聯(lián)合索引進(jìn)行排序的場景，我們要求各個排序列的排序順序是一致的，也就是要么各個列都是ASC規(guī)則排序，要么都是DESC規(guī)則排序。
ORDER BY子句后的列如果不加ASC或者DESC默認(rèn)是按照ASC排序規(guī)則排序的，也就是升序排序的。
select * from t1 order by b ASC, c DESC;
這個查詢是用不到索引的。
如何建立索引
考慮索引選擇性
索引的選擇性（Selectivity），是指不重復(fù)的索引值（也叫基數(shù)，Cardinality）與表記錄數(shù)的比值：
選擇性=基數(shù)/記錄數(shù)
選擇性的取值范圍為(0, 1]，選擇性越高的索引價值越大。如果選擇性等于1，就代表這個列的不重復(fù)值和表記錄數(shù)是一樣的，那么對這個列建立索引是非常合適的，如果選擇性非常小，那么就代表這個列的重復(fù)值是很多的，不適合建立索引。
考慮前綴索引
用列的前綴代替整個列作為索引key，當(dāng)前綴長度合適時，可以做到既使得前綴索引的選擇性接近全列索引，同時因為索引key變短而減少了索引文件的大小和維護(hù)開銷。
使用mysql官網(wǎng)提供的示例數(shù)據(jù)庫：https://dev.mysql.com/doc/employee/en/employees-installation.html
github地址：https://github.com/datacharmer/test_db.git
employees表只有一個索引，那么如果我們想按名字搜索一個人，就只能全表掃描了：
EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND
last_name='Anido';
那么可以對或建立索引，看下兩個索引的選擇性：
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees; -
- 0.0042
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM
employees.employees; -- 0.9313
顯然選擇性太低，選擇性很好，但是first_name和last_name加起來長度為30，有沒有兼顧長度和選擇性的辦法？
可以考慮用first_name和last_name的前幾個字符建立索引，例如，看看其選擇性：
SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity
FROM employees.employees; -- 0.7879
選擇性還不錯，但離0.9313還是有點距離，那么把last_name前綴加到4：
SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity
FROM employees.employees; -- 0.9007
這時選擇性已經(jīng)很理想了，而這個索引的長度只有18，比短了接近一半，建立前綴索引的方式為：
ALTER TABLE employees.employees ADD INDEX `first_name_last_name4` (first_name,
last_name(4));
前綴索引兼顧索引大小和查詢速度，但是其缺點是不能用于ORDER BY和GROUP BY操作，也不能用于覆蓋索引。
總結(jié)
索引列的類型盡量小
利用索引字符串值的前綴
主鍵自增
定位并刪除表中的重復(fù)和冗余索引
盡量使用覆蓋索引進(jìn)行查詢，避免回表帶來的性能損耗。
我是Java高級開發(fā)之路，專注分享程序員的干貨知識與趣事，
最后為大家分享我整理的最全的Java面試資料
聽說一鍵三連的粉絲都面試成功了？也祝愿所有的讀者都能夠收獲自己心儀的offer！
