小史是一個(gè)應(yīng)屆生，雖然學(xué)的是電子專業(yè)，但是自己業(yè)余時(shí)間看了很多互聯(lián)網(wǎng)與編程方面的書(shū)，一心想進(jìn)BAT互聯(lián)網(wǎng)公司。
話說(shuō)兩個(gè)多月前，小史通過(guò)了A廠的一面，兩個(gè)多月后的今天，小史終于等到了A廠的二面。
簡(jiǎn)單的自我介紹后，面試官看了看小史的簡(jiǎn)歷，開(kāi)始發(fā)問(wèn)了。
面試現(xiàn)場(chǎng)
小史：沒(méi)問(wèn)題，這個(gè)項(xiàng)目前端用的react+webpack，后端用的nginx+SpringBoot+Redis+MySql，前后端分離的，最后用docker進(jìn)行容器化部署。主要模塊有師生系統(tǒng)、課程系統(tǒng)、成績(jī)系統(tǒng)、選課系統(tǒng)等。
這個(gè)項(xiàng)目的架構(gòu)和說(shuō)辭，小史早已背得溜溜的。
小史：底層MySQL是存儲(chǔ)，Redis是緩存，DAO層操作MySQL，Cache層操作Redis，Service層處理業(yè)務(wù)邏輯，Rest API層為前端提供Rest接口。前端這邊用React進(jìn)行模塊化，Webpack打包部署。網(wǎng)關(guān)Nginx進(jìn)行負(fù)載均衡。MySQL、Redis、Nginx和SpringBoot應(yīng)用都放在Docker里部署。
題目：為什么MySQL數(shù)據(jù)庫(kù)要用B+樹(shù)存儲(chǔ)索引？
小史聽(tīng)到這個(gè)題目，陷入了回憶。
前段時(shí)間的飯局
話說(shuō)呂老師給小史講完人工智能的一些知識(shí)后，他們一起回家吃小史姐姐做的飯去了。
【飯后】
呂老師：面試的時(shí)候一定是往深了問(wèn)，不精通的話容易吃虧。不過(guò)面試時(shí)一般都是根據(jù)項(xiàng)目來(lái)問(wèn)，項(xiàng)目中用到的技術(shù)，一定要多看看原理，特別是能和數(shù)據(jù)結(jié)構(gòu)和算法掛鉤的那部分。
小史：樹(shù)的話，無(wú)非就是前中后序遍歷、二叉樹(shù)、二叉搜索樹(shù)、平衡二叉樹(shù)，更高級(jí)一點(diǎn)的有紅黑樹(shù)、B樹(shù)、B+樹(shù)，還有之前你教我的字典樹(shù)。
【紅黑樹(shù)】
一聽(tīng)到紅黑樹(shù)，小史頭都大了，開(kāi)始抱怨了起來(lái)。
小史：紅黑樹(shù)看過(guò)很多遍了，但是每次都記不住，它的規(guī)則實(shí)在是太多了，光定義就有四五條規(guī)則，還有插入刪除的時(shí)候，需要調(diào)整樹(shù)，復(fù)雜得很。
呂老師：小史，問(wèn)你紅黑樹(shù)，并不是讓你背誦它的定義，或者讓你手寫(xiě)一個(gè)紅黑樹(shù)，而是想問(wèn)問(wèn)你它為什么這樣設(shè)計(jì)，它的使用場(chǎng)景有哪些。
【B樹(shù)】
呂老師：小史，你要知道，文件系統(tǒng)和數(shù)據(jù)庫(kù)的索引都是存在硬盤上的，并且如果數(shù)據(jù)量大的話，不一定能一次性加載到內(nèi)存中。
兩個(gè)月前，小史面試沒(méi)考慮內(nèi)存情況差點(diǎn)掛了，傳送門......
【B+樹(shù)】
呂老師：這也是和業(yè)務(wù)場(chǎng)景相關(guān)的，你想想，數(shù)據(jù)庫(kù)中select數(shù)據(jù)，不一定只選一條，很多時(shí)候會(huì)選多條，比如按照ID排序后選10條。
小史：我明白了，如果是多條的話，B樹(shù)需要做局部的中序遍歷，可能要跨層訪問(wèn)。而B(niǎo)+樹(shù)由于所有數(shù)據(jù)都在葉子結(jié)點(diǎn)，不用跨層，同時(shí)由于有鏈表結(jié)構(gòu)，只需要找到首尾，通過(guò)鏈表就能把所有數(shù)據(jù)取出來(lái)了。
回到現(xiàn)場(chǎng)
小史：這和業(yè)務(wù)場(chǎng)景有關(guān)。如果只選一個(gè)數(shù)據(jù)，那確實(shí)是Hash更快。但是數(shù)據(jù)庫(kù)中經(jīng)常會(huì)選擇多條，這時(shí)候由于B+樹(shù)索引有序，并且又有鏈表相連，它的查詢效率比Hash就快很多了。
小史：而且數(shù)據(jù)庫(kù)中的索引一般是在磁盤上，數(shù)據(jù)量大的情況可能無(wú)法一次裝入內(nèi)存，B+樹(shù)的設(shè)計(jì)可以允許數(shù)據(jù)分批加載，同時(shí)樹(shù)的高度較低，提高查找效率。
HR和小史簡(jiǎn)單地聊了聊基本情況，這次面試就結(jié)束了。
小史走后，面試官在系統(tǒng)中寫(xiě)下了面試評(píng)語(yǔ)：
幾天后，小史收到了A廠的offer。
親愛(ài)的讀者們，面試現(xiàn)場(chǎng)的第一季到這里就全部結(jié)束了，感謝大家的支持，我們一起期待小史后面的故事。
