為什么Mongodb索引用B樹,而Mysql用B+樹?
來源：孤獨(dú)煙
作者：孤獨(dú)煙
好久沒寫文章了，今天回來重操舊業(yè)。
今天講的這個主題，是《面試官:談?wù)勀銓ysql索引的認(rèn)識》，里頭提到的一個坑。
也就是說，如果面試官問的是，為什么Mysql中Innodb的索引結(jié)構(gòu)采取B+樹？這個問題時，給自己留一條后路，不要把B樹噴的一文不值。因?yàn)榫W(wǎng)上有些答案是說，B樹不適合做文件存儲系統(tǒng)的索引結(jié)構(gòu)。如果按照那種答法，自己就給自己挖了一個坑，很難收場。因此，就有了這篇文章的誕生~
文末附面試指南！
正文
這里的Mysql指的是Innodb的存儲引擎下的索引結(jié)構(gòu)，其他存儲引擎我們暫時不討論。
B樹和B+樹
開頭，我們先回憶一下，B樹和B+樹的結(jié)構(gòu)以及特點(diǎn)，如下所示:
B樹
注意一下B樹的兩個明顯特點(diǎn)
樹內(nèi)的每個節(jié)點(diǎn)都存儲數(shù)據(jù)
葉子節(jié)點(diǎn)之間無指針相鄰
B+樹
注意一下B樹的兩個明顯特點(diǎn)
數(shù)據(jù)只出現(xiàn)在葉子節(jié)點(diǎn)
所有葉子節(jié)點(diǎn)增加了一個鏈指針
針對上面的B+樹和B樹的特點(diǎn)，我們做一個總結(jié)
(1)B樹的樹內(nèi)存儲數(shù)據(jù)，因此查詢單條數(shù)據(jù)的時候，B樹的查詢效率不固定，最好的情況是O(1)。我們可以認(rèn)為在做單一數(shù)據(jù)查詢的時候，使用B樹平均性能更好。但是，由于B樹中各節(jié)點(diǎn)之間沒有指針相鄰，因此B樹不適合做一些數(shù)據(jù)遍歷操作。
(2)B+樹的數(shù)據(jù)只出現(xiàn)在葉子節(jié)點(diǎn)上，因此在查詢單條數(shù)據(jù)的時候，查詢速度非常穩(wěn)定。因此，在做單一數(shù)據(jù)的查詢上，其平均性能并不如B樹。但是，B+樹的葉子節(jié)點(diǎn)上有指針進(jìn)行相連，因此在做數(shù)據(jù)遍歷的時候，只需要對葉子節(jié)點(diǎn)進(jìn)行遍歷即可，這個特性使得B+樹非常適合做范圍查詢。
因此，我們可以做一個推論:沒準(zhǔn)是Mysql中數(shù)據(jù)遍歷操作比較多，所以用B+樹作為索引結(jié)構(gòu)。而Mongodb是做單一查詢比較多，數(shù)據(jù)遍歷操作比較少，所以用B樹作為索引結(jié)構(gòu)。
那么為什么Mysql做數(shù)據(jù)遍歷操作多？而Mongodb做數(shù)據(jù)遍歷操作少呢？
因?yàn)镸ysql是關(guān)系型數(shù)據(jù)庫，而Mongodb是非關(guān)系型數(shù)據(jù)。
那為什么關(guān)系型數(shù)據(jù)庫，做數(shù)據(jù)遍歷操作多？
而非關(guān)系型數(shù)據(jù)庫，做數(shù)據(jù)遍歷操作少呢？
我們繼續(xù)往下看
關(guān)系型VS非關(guān)系型
假設(shè)，我們此時有兩個邏輯實(shí)體:學(xué)生(Student)和班級(Class)，這兩個邏輯實(shí)體之間是一對多的關(guān)系。畢竟一個班級有多個學(xué)生，一個學(xué)生只能屬于一個班級。
關(guān)系型數(shù)據(jù)庫
我們在關(guān)系型數(shù)據(jù)庫中，考慮的是用幾張表來表示這二者之間的實(shí)體關(guān)系。常見的無外乎是，一對一關(guān)系，用一張表就行。一對多關(guān)系，用兩張表。多對多關(guān)系，用三張表。
那這里，我們需要用兩張表表示二者之間邏輯關(guān)系，如下所示
那我們，此時要查
cname為1班的班級，有多少學(xué)生怎么辦？假設(shè)
cname這列，我們建了索引！執(zhí)行SQL，如下所示！
SELECT?*
FROM?t_student?t1,?(
????????SELECT?cid
????????FROM?t_class
????????WHERE?cname?=?'1班'
????)?t2
WHERE?t1.cid?=?t2.cid
而這，就涉及到了數(shù)據(jù)遍歷操作！
因?yàn)榈沧鲞@種關(guān)聯(lián)查詢，你躲不開join操作的！既然涉及到了join操作，無外乎從一個表中取一個數(shù)據(jù)，去另一個表中逐行匹配，如果索引結(jié)構(gòu)是B+樹，葉子節(jié)點(diǎn)上是有指針的，能夠極大的提高這種一行一行的匹配速度！
有的人或許會抬杠說，如果我先執(zhí)行
SELECT?cid
FROM?t_class
WHERE?cname?=?'1班'
獲得cid后，再去循環(huán)執(zhí)行
SELECT?*
FROM?t_student
WHERE?cid?=?...
就可以避開join操作呀？
對此，我想說。你確實(shí)避開了join操作，但是你數(shù)據(jù)遍歷操作還是沒避開。你還是需要在student的這張表的葉子節(jié)點(diǎn)上，一遍又一遍的遍歷！
那在非關(guān)系型數(shù)據(jù)庫中，我們?nèi)绾尾樵?code style="font-size:inherit;color:rgb(248,35,117);">cname為1班的班級，有多少學(xué)生？
非關(guān)系型數(shù)據(jù)庫
有人說，你可以這么設(shè)計？也就是弄兩個集合如下所示
確實(shí)，這么設(shè)計是可以的，我沒說不行。只是不符合非關(guān)系型數(shù)據(jù)庫的設(shè)計初衷。在MongoDB中，根本不推薦這么設(shè)計。雖然，Mongodb中有一個$lookup操作，可以做join查詢。但是理想情況下，這個$lookup操作應(yīng)該不會經(jīng)常使用，如果你需要經(jīng)常使用它，那么你就使用了錯誤的數(shù)據(jù)存儲了（數(shù)據(jù)庫）：如果你有相關(guān)聯(lián)的數(shù)據(jù)，應(yīng)該使用關(guān)系型數(shù)據(jù)庫（SQL）。
因此，正規(guī)的設(shè)計應(yīng)該如下
假設(shè)
name這列，我們建了索引！我只需執(zhí)行一次語句
db.class.find(?{?name:?'1班'?}?)
這樣就能查詢出自己想要的結(jié)果。
而這，就是一種單一數(shù)據(jù)查詢!畢竟你不需要去逐行匹配，不涉及遍歷操作,幸運(yùn)的情況下，有可能一次IO就能夠得到你想要的結(jié)果。
因此，由于關(guān)系型數(shù)據(jù)庫和非關(guān)系型數(shù)據(jù)的設(shè)計方式上的不同。導(dǎo)致在關(guān)系型數(shù)據(jù)中，遍歷操作比較常見，因此采用B+樹作為索引，比較合適。而在非關(guān)系型數(shù)據(jù)庫中，單一查詢比較常見，因此采用B樹作為索引，比較合適。
面試套路
目前套路有如下幾種
套路一
你簡歷寫了mysql，沒寫mongodb!
面試官:"說說mysql索引結(jié)構(gòu)？"
我:"巴拉巴拉"
面試官:"知道為什么用B+樹，不用B樹么？"
這個時候正常的面試者就蒙了，會把B樹的缺點(diǎn)噴一通！于是乎下一問就是
面試官:"其實(shí)一些非關(guān)系型數(shù)據(jù)庫，如mongodb用的就是B樹，你知道原因么？"
然后你就回去等通知了！
套路二
你簡歷寫了mysql，也寫了mongodb!
這種情況更完美！
面試官:"說說mysql索引結(jié)構(gòu)？"
我:"巴拉巴拉"
面試官:"你簡歷寫了Mongodb，有了解過他的索引結(jié)構(gòu)么？"
我:"巴拉巴拉"
面試官:"為什么Mongodb索引用B樹，而Mysql用B+樹？"
然后你就回去等通知了！
套路三
你簡歷既沒寫mysql，沒寫mongodb!
面試官；"如果你來設(shè)計數(shù)據(jù)庫，你會對他的索引用什么數(shù)據(jù)結(jié)構(gòu)？"
我:"首先不考慮紅黑樹這類，巴拉巴拉…應(yīng)該會用B樹或者B+樹。"
面試官；“如果我要設(shè)計一個像Mongodb那樣的非關(guān)系型數(shù)據(jù)庫，我要用什么數(shù)據(jù)結(jié)構(gòu)當(dāng)索引比較合適?”
然后你就可以回去等通知了！
上面三個套路都是真實(shí)存在的！總之，只要面試官想問這個問題，都可以繞到這個問題上去！
總結(jié)
其實(shí)這篇文章很早以前就想寫，后來一直耽擱著。今天有時間剛好補(bǔ)上，希望大家有所收獲。
推薦閱讀
全部文章分類與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計算機(jī)基礎(chǔ)），持續(xù)更新
【吐血整理】那些讓你起飛的計算機(jī)基礎(chǔ)知識：學(xué)什么，怎么學(xué)？