年輕人不講武德陋率,刁難Java面試官:B+樹如何實(shí)現(xiàn)索引?最后還面過了秽晚!簡直就是奇跡瓦糟!

前言

事情的經(jīng)過是這樣的:

電面試官問我什么是B+樹,我說用的不多赴蝇,只知道是一種樹數(shù)據(jù)結(jié)構(gòu)菩浙。

然后面試官問我怎么實(shí)現(xiàn)索引的?我答不出來句伶,就下一題了劲蜻。

最后問的差不多了,面試官問我考余,你還有什么想問我的?

我本著每次面試都算是學(xué)習(xí)的心態(tài)就問了句:B+樹怎么實(shí)現(xiàn)索引的?

image.png

沒想到面試官.....支支吾吾半天也答不上來先嬉,然后說太久了都忘了。

得虧當(dāng)時(shí)是電面楚堤,要不然我都不知道用什么樣的表情面對面試官疫蔓!哈哈哈!

我覺得面試官當(dāng)時(shí)肯定心想:年輕人不講武德身冬,偷襲我69歲面試官衅胀?

最后知道電面過的時(shí)候,我覺得這簡直就是個(gè)奇跡吏恭!

不過愛學(xué)習(xí)的我當(dāng)然不會(huì)就此罷休拗小,接下來就整理總結(jié)了B+數(shù)索引實(shí)戰(zhàn)的全過程,同樣的坑絕對不能摔倒兩次樱哼!

文章末尾也為大家準(zhǔn)備好了Java學(xué)習(xí)資料,千萬不要錯(cuò)過哦剿配!

索引的代價(jià)

空間上的代價(jià)

一個(gè)索引都為對應(yīng)一棵B+樹搅幅,樹中每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)據(jù)頁,一個(gè)頁默認(rèn)會(huì)占用16KB的存儲(chǔ)空間呼胚,所以一個(gè)索引也是會(huì)占用磁盤空間的茄唐。

時(shí)間上的代價(jià)

索引是對數(shù)據(jù)的排序,那么當(dāng)對表中的數(shù)據(jù)進(jìn)行增蝇更、刪沪编、改操作時(shí),都需要去維護(hù)修改內(nèi)容涉及到的B+樹索引年扩。
所以在進(jìn)行增蚁廓、刪、改操作時(shí)可能需要額外的時(shí)間進(jìn)行一些記錄移動(dòng)厨幻,頁面分裂相嵌、頁面回收等操作來維護(hù)好排
序腿时。

B+樹索引實(shí)戰(zhàn)

全職匹配

java
select * from t1 where b = 1 and c = 1 and d = 1;

查詢優(yōu)化器會(huì)分析這些查詢條件并且按照可以使用的索引中列的順序來決定先使用哪個(gè)查詢條件。

匹配左邊的列

select * from t1 where b = 1;
select * from t1 where b = 1 and c = 1;

下面這個(gè)sql是用不到索引的

select * from t1 where c = 1;   

因?yàn)锽+樹先是按照b列的值排序的饭宾,在b列的值相同的情況下才使用c列進(jìn)行排序批糟,也就是說b列的值不同的記錄
中c的值可能是無序的。而現(xiàn)在你跳過b列直接根據(jù)c的值去查找看铆,這是做不到的徽鼎。

匹配列前綴

如果只給出后綴或者中間的某個(gè)字符串,比如:

select * from t1 where b like '%101%';

這種是用不到索引的弹惦,因?yàn)樽址虚g有'101'的字符串并沒有排好序否淤,所以只能全表掃描了。有時(shí)候我們有一些匹配某些字符串后綴的需求肤频,比方說某個(gè)表有一個(gè)url列叹括,該列中存儲(chǔ)了許多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í)用到這個(gè)索引而不至于全表掃描,我們可以把后綴查詢改寫成前綴查詢报咳,不過我們就得把表中的數(shù)據(jù)全部逆序存儲(chǔ)一下侠讯,也就是說我們可以這樣保存url列中的數(shù)據(jù):

moc.udiab.www
moc.elgoog.www
moc.qq.www

這樣再查找以com為后綴的網(wǎng)址時(shí)搜索條件便可以這么寫:WHERE url LIKE 'moc%',這樣就可以用到索引了暑刃。

匹配范圍值

select * from t1 where b > 1 and b < 20000;

由于B+樹中的數(shù)據(jù)頁和記錄是先按b列排序的厢漩,所以我們上邊的查詢過程其實(shí)是這樣的:

  • 找到b值為1的記錄。
  • 找到b值為20000的記錄岩臣。
  • 由于所有記錄都是由鏈表連起來的(記錄之間用單鏈表溜嗜,數(shù)據(jù)頁之間用雙鏈表),所以他們之間的記錄都可以很容易的取出來
  • 找到這些記錄的主鍵值架谎,再到聚簇索引中回表查找完整的記錄炸宵。

不過在使用聯(lián)合進(jìn)行范圍查找的時(shí)候需要注意,如果對多個(gè)列同時(shí)進(jìn)行范圍查找的話谷扣,只有對索引最左邊的那個(gè)列進(jìn)行范圍查找的時(shí)候才能用到B+樹索引土全,比如:

select * from t1 where b > 1 and c > 1;

上邊這個(gè)查詢可以分成兩個(gè)部分:

  1. 通過條件b > 1來對b進(jìn)行范圍,查找的結(jié)果可能有多條b值不同的記錄会涎,
  2. 對這些b值不同的記錄繼續(xù)通過c > 1繼續(xù)過濾裹匙。

這樣子對于聯(lián)合索引來說,只能用到b列的部分末秃,而用不到c列的部分概页,因?yàn)橹挥衎值相同的情況下才能用c列的值進(jìn)行排序,而這個(gè)查詢中通過b進(jìn)行范圍查找的記錄中可能并不是按照c列進(jìn)行排序的蛔溃,所以在搜索條件中繼續(xù)以c列進(jìn)行查找時(shí)是用不到這個(gè)B+樹索引的绰沥。

精確匹配某一列并范圍匹配另外一列

對于同一個(gè)聯(lián)合索引來說篱蝇,雖然對多個(gè)列都進(jìn)行范圍查找時(shí)只能用到最左邊那個(gè)索引列,但是如果左邊的列是精確查找徽曲,則右邊的列可以進(jìn)行范圍查找零截,比方說這樣:

select * from t1 where b = 1 and c > 1;

排序

select * from t1 order by b, c, d;

這個(gè)查詢的結(jié)果集需要先按照b值排序,如果記錄的b值相同秃臣,則需要按照c來排序涧衙,如果c的值相同,則需要按照d排序奥此。因?yàn)檫@個(gè)B+樹索引本身就是按照上述規(guī)則排好序的弧哎,所以直接從索引中提取數(shù)據(jù),然后進(jìn)行回表操作取出該索引中不包含的列就好了稚虎。

分組

select b, c, d, count(*) from t1 group by b, c, d;

這個(gè)查詢語句相當(dāng)于做了3次分組操作:

  1. 先把記錄按照b值進(jìn)行分組撤嫩,所有b值相同的記錄劃分為一組。
  2. 將每個(gè)b值相同的分組里的記錄再按照c的值進(jìn)行分組蠢终,將title值相同的記錄放到一個(gè)分組里序攘。
  3. 再將上一步中產(chǎn)生的分組按照d的值分成更小的分組。

如果沒有索引的話寻拂,這個(gè)分組過程全部需要在內(nèi)存里實(shí)現(xiàn)程奠,而如果有索引的話,正好這個(gè)分組順序又和B+樹中的索引列的順序是一致的祭钉,所以可以直接使用B+樹索引進(jìn)行分組瞄沙。

使用聯(lián)合索引進(jìn)行排序或分組的注意事項(xiàng)

對于聯(lián)合索引有個(gè)問題需要注意,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;

這個(gè)查詢能使用聯(lián)合索引進(jìn)行排序是因?yàn)閎列的值相同的記錄是按照c, d排序的。

不可以使用索引進(jìn)行排序或分組的幾種情況
ASC们衙、DESC混用

對于使用聯(lián)合索引進(jìn)行排序的場景钾怔,我們要求各個(gè)排序列的排序順序是一致的,也就是要么各個(gè)列都是ASC規(guī)則排序蒙挑,要么都是DESC規(guī)則排序宗侦。

ORDER BY子句后的列如果不加ASC或者DESC默認(rèn)是按照ASC排序規(guī)則排序的,也就是升序排序的忆蚀。

select * from t1 order by b ASC, c DESC;

這個(gè)查詢是用不到索引的矾利。

如何建立索引

考慮索引選擇性

索引的選擇性(Selectivity)姑裂,是指不重復(fù)的索引值(也叫基數(shù),Cardinality)與表記錄數(shù)的比值:

選擇性=基數(shù)/記錄數(shù)

選擇性的取值范圍為(0, 1]男旗,選擇性越高的索引價(jià)值越大舶斧。如果選擇性等于1,就代表這個(gè)列的不重復(fù)值和表記錄數(shù)是一樣的察皇,那么對這個(gè)列建立索引是非常合適的茴厉,如果選擇性非常小,那么就代表這個(gè)列的重復(fù)值是很多的什荣,不適合建立索引矾缓。

考慮前綴索引

用列的前綴代替整個(gè)列作為索引key,當(dāng)前綴長度合適時(shí)稻爬,可以做到既使得前綴索引的選擇性接近全列索引嗜闻,同時(shí)因?yàn)樗饕齥ey變短而減少了索引文件的大小和維護(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表只有一個(gè)索引桅锄,那么如果我們想按名字搜索一個(gè)人琉雳,就只能全表掃描了:

EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND
last_name='Anido';

那么可以對或建立索引,看下兩個(gè)索引的選擇性:

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的前幾個(gè)字符建立索引锯茄,例如,看看其選擇性:

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity
FROM employees.employees; -- 0.7879

選擇性還不錯(cuò)茶没,但離0.9313還是有點(diǎn)距離肌幽,那么把last_name前綴加到4:

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity
FROM employees.employees; -- 0.9007

這時(shí)選擇性已經(jīng)很理想了,而這個(gè)索引的長度只有18抓半,比短了接近一半喂急,建立前綴索引的方式為:

ALTER TABLE employees.employees ADD INDEX `first_name_last_name4` (first_name,
last_name(4));

前綴索引兼顧索引大小和查詢速度,但是其缺點(diǎn)是不能用于ORDER BY和GROUP BY操作笛求,也不能用于覆蓋索引廊移。

總結(jié)

  • 索引列的類型盡量小
  • 利用索引字符串值的前綴
  • 主鍵自增
  • 定位并刪除表中的重復(fù)和冗余索引
  • 盡量使用覆蓋索引進(jìn)行查詢,避免回表帶來的性能損耗探入。

我是Java高級(jí)開發(fā)之路狡孔,專注分享程序員的干貨知識(shí)與趣事,
最后為大家分享我整理的最全的Java面試資料

在這里插入圖片描述
在這里插入圖片描述

在這里插入圖片描述
在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

聽說一鍵三連的粉絲都面試成功了蜂嗽?也祝愿所有的讀者都能夠收獲自己心儀的offer苗膝!


image.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市植旧,隨后出現(xiàn)的幾起案子辱揭,更是在濱河造成了極大的恐慌离唐,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,490評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件问窃,死亡現(xiàn)場離奇詭異亥鬓,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)泡躯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,581評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門贮竟,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人较剃,你說我怎么就攤上這事咕别。” “怎么了写穴?”我有些...
    開封第一講書人閱讀 165,830評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵惰拱,是天一觀的道長。 經(jīng)常有香客問我啊送,道長偿短,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,957評(píng)論 1 295
  • 正文 為了忘掉前任馋没,我火速辦了婚禮昔逗,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘篷朵。我一直安慰自己勾怒,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,974評(píng)論 6 393
  • 文/花漫 我一把揭開白布声旺。 她就那樣靜靜地躺著笔链,像睡著了一般。 火紅的嫁衣襯著肌膚如雪腮猖。 梳的紋絲不亂的頭發(fā)上鉴扫,一...
    開封第一講書人閱讀 51,754評(píng)論 1 307
  • 那天,我揣著相機(jī)與錄音澈缺,去河邊找鬼坪创。 笑死,一個(gè)胖子當(dāng)著我的面吹牛姐赡,可吹牛的內(nèi)容都是我干的误堡。 我是一名探鬼主播,決...
    沈念sama閱讀 40,464評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼雏吭,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了陪踩?” 一聲冷哼從身側(cè)響起杖们,我...
    開封第一講書人閱讀 39,357評(píng)論 0 276
  • 序言:老撾萬榮一對情侶失蹤悉抵,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后摘完,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體姥饰,經(jīng)...
    沈念sama閱讀 45,847評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,995評(píng)論 3 338
  • 正文 我和宋清朗相戀三年孝治,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了列粪。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,137評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡谈飒,死狀恐怖岂座,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情杭措,我是刑警寧澤费什,帶...
    沈念sama閱讀 35,819評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站手素,受9級(jí)特大地震影響鸳址,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜泉懦,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,482評(píng)論 3 331
  • 文/蒙蒙 一稿黍、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧崩哩,春花似錦巡球、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,023評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至吴超,卻和暖如春钉嘹,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背鲸阻。 一陣腳步聲響...
    開封第一講書人閱讀 33,149評(píng)論 1 272
  • 我被黑心中介騙來泰國打工跋涣, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人鸟悴。 一個(gè)月前我還...
    沈念sama閱讀 48,409評(píng)論 3 373
  • 正文 我出身青樓陈辱,卻偏偏與公主長得像,于是被迫代替她去往敵國和親细诸。 傳聞我的和親對象是個(gè)殘疾皇子沛贪,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,086評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容