好久沒寫文章了，今天回來重操舊業。畢竟現在對後端開發的要求越來越高，大家要做好各種準備。
是以，大家有可能遇到如下問題
為什麼Mysql中Innodb的索引結構采取B+樹？
回答這個問題時，給自己留一條後路，不要把B樹噴的一文不值。因為網上有些答案是說，B樹不适合做檔案存儲系統的索引結構。如果按照那種答法，自己就給自己挖了一個坑，很難收場。是以，就有了這篇文章的誕生~
文末附面試指南！
這裡的Mysql指的是Innodb的存儲引擎下的索引結構，其他存儲引擎我們暫時不讨論。
開頭，我們先回憶一下，B樹和B+樹的結構以及特點，如下所示:
B樹
注意一下B樹的兩個明顯特點
樹内的每個節點都存儲資料
葉子節點之間無指針相鄰
B+樹
注意一下B+樹的兩個明顯特點
資料隻出現在葉子節點
所有葉子節點增加了一個鍊指針
針對上面的B+樹和B樹的特點，我們做一個總結
(1)B樹的樹記憶體儲資料，是以查詢單條資料的時候，B樹的查詢效率不固定，最好的情況是O(1)。我們可以認為在做單一資料查詢的時候，使用B樹平均性能更好。但是，由于B樹中各節點之間沒有指針相鄰，是以B樹不适合做一些資料周遊操作。
(2)B+樹的資料隻出現在葉子節點上，是以在查詢單條資料的時候，查詢速度非常穩定。是以，在做單一資料的查詢上，其平均性能并不如B樹。但是，B+樹的葉子節點上有指針進行相連，是以在做資料周遊的時候，隻需要對葉子節點進行周遊即可，這個特性使得B+樹非常适合做範圍查詢。
是以，我們可以做一個推論:沒準是Mysql中資料周遊操作比較多，是以用B+樹作為索引結構。而Mongodb是做單一查詢比較多，資料周遊操作比較少，是以用B樹作為索引結構。
那麼為什麼Mysql做資料周遊操作多？而Mongodb做資料周遊操作少呢？
因為Mysql是關系型資料庫，而Mongodb是非關系型資料。
那為什麼關系型資料庫，做資料周遊操作多？而非關系型資料庫做資料周遊操作少呢？
我們繼續往下看
假設，我們此時有兩個邏輯實體:學生(Student)和班級(Class)，這兩個邏輯實體之間是一對多的關系。畢竟一個班級有多個學生，一個學生隻能屬于一個班級。
關系型資料庫
我們在關系型資料庫中，考慮的是用幾張表來表示這二者之間的實體關系。常見的無外乎是，一對一關系，用一張表就行。一對多關系，用兩張表。多對多關系，用三張表。
那這裡，我們需要用兩張表表示二者之間邏輯關系，如下所示
那我們，此時要查<code>cname</code>為<code>1班</code>的班級，有多少學生怎麼辦？
假設<code>cname</code>這列，我們建了索引！
執行SQL，如下所示！
而這，就涉及到了資料周遊操作！
因為但凡做這種關聯查詢，你躲不開join操作的！既然涉及到了join操作，無外乎從一個表中取一個資料，去另一個表中逐行比對，如果索引結構是B+樹，葉子節點上是有指針的，能夠極大的提高這種一行一行的比對速度！
有的人或許會擡杠說，如果我先執行
獲得cid後，再去循環執行
就可以避開join操作呀？
對此，我想說。你确實避開了join操作，但是你資料周遊操作還是沒避開。你還是需要在student的這張表的葉子節點上，一遍又一遍的周遊！
那在非關系型資料庫中，我們如何查詢<code>cname</code>為<code>1班</code>的班級，有多少學生？
非關系型資料庫
有人說，你可以這麼設計？也就是弄兩個集合如下所示
然後勒，執行兩次查詢去獲得結果！
确實，這麼設計是可以的，我沒說不行。隻是不符合非關系型資料庫的設計初衷。在MongoDB中，根本不推薦這麼設計。雖然，Mongodb中有一個\(lookup操作，可以做join查詢。但是理想情況下，這個\)lookup操作應該不會經常使用，如果你需要經常使用它，那麼你就使用了錯誤的資料存儲了（資料庫）：如果你有相關聯的資料，應該使用關系型資料庫（SQL）。
是以，正規的設計應該如下
假設<code>name</code>這列，我們建了索引！
我隻尋執行一次語句
這樣就能查詢出自己想要的結果。
而這，就是一種單一資料查詢!畢竟你不需要去逐行比對，不涉及周遊操作,幸運的情況下，有可能一次IO就能夠得到你想要的結果。
是以，由于關系型資料庫和非關系型資料的設計方式上的不同。導緻在關系型資料中，周遊操作比較常見，是以采用B+樹作為索引，比較合适。而在非關系型資料庫中，單一查詢比較常見，是以采用B樹作為索引，比較合适。
目前套路有如下幾種
你履歷寫了mysql，沒寫mongodb!
面試官:"說說mysql索引結構？"
我:"巴拉巴拉"
面試官:"知道為什麼用B+樹，不用B樹麼？"
這個時候正常的面試者就蒙了，會把B樹的缺點噴一通！于是乎下一問就是
面試官:"其實一些非關系型資料庫，如mongodb用的就是B樹，你知道原因麼？"
然後你就回去等通知了！
你履歷寫了mysql，也寫了mongodb!
這種情況更完美！
面試官:"你履歷寫了Mongodb，有了解過他的索引結構麼？"
面試官:"為什麼Mongodb索引用B樹，而Mysql用B+樹？"
你履歷既沒寫mysql，沒寫mongodb!
面試官；"如果你來設計資料庫，你會對他的索引用什麼資料結構？"
我:"首先不考慮紅黑樹這類，巴拉巴拉...應該會用B樹或者B+樹。"
面試官；“如果我要設計一個像Mongodb那樣的非關系型資料庫，我要用什麼資料結構當索引比較合适?”
然後你就可以回去等通知了！
上面三個套路都是真實存在的！總之，隻要面試官想問這個問題，都可以繞到這個問題上去！
其實這篇文章很早以前就想寫，後來一直耽擱着。今天有時間剛好補上，希望大家有所收獲。
作者：孤獨煙
出處： http://rjzheng.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。如果覺得還有幫助的話，可以點一下右下角的【推薦】。