為了更好的準(zhǔn)備面試，刷題方式正式改版，每日從各處收集的面經(jīng)中選擇幾道經(jīng)典面試題分享并給出答案供參考，答案中會做與題目相關(guān)的擴(kuò)展，并且可能會拋出一定問題供思考。這些題目我會標(biāo)注具體的公司、招聘類型(校招、社招、實(shí)習(xí))以及面試階段。這些面試題會收錄到鎖屏面試題app和小程序中并整理歸類好。其他面試題也同樣在持續(xù)更新中，多謝使用和支持。下面是今日面試題:

(一)b樹:======================================================

b樹的定義

b樹就是b-樹(b-tree)，b樹是一種平衡多路查找樹，它在文件系統(tǒng)中很有用。

具有以下規(guī)則的樹是b樹(M階樹):

（1）首先強(qiáng)調(diào)的一點(diǎn)是b樹的階是由人為定義的，只有當(dāng)對一個(gè)b樹沒有明確指定多少階的時(shí)候，直接問你這個(gè)b樹的階數(shù)，才可以通過一個(gè)b樹的所有節(jié)點(diǎn)的最多分支數(shù)來說這個(gè)b樹是多少階的。如下圖中，若沒有說明是幾階，我們可以看到w所在的節(jié)點(diǎn)的分支數(shù)最多，為5，則可以說這是個(gè)5階b樹。

（2）排序方式：所有節(jié)點(diǎn)關(guān)鍵字是按遞增次序排列，并遵循左小右大原則；

（3）子節(jié)點(diǎn)數(shù)：非葉節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)>1，且<=M ，且M>=2，空樹除外；

（4）關(guān)鍵字?jǐn)?shù)：枝節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量大于等于ceil(m/2)-1個(gè)且小于等于M-1個(gè)（注：ceil()是個(gè)朝正無窮方向取整的函數(shù) 如ceil(1.1)結(jié)果為2),這個(gè)是b樹插入和刪除操作時(shí)關(guān)鍵依據(jù)。

（5）所有葉子節(jié)點(diǎn)均在同一層、葉子節(jié)點(diǎn)除了包含了關(guān)鍵字和關(guān)鍵字記錄的指針外也有指向其子節(jié)點(diǎn)的指針只不過其指針地址都為null。

b樹的查詢:

比如查找F:

(1)?從根節(jié)點(diǎn)開始，F(xiàn)<M,所以從M的左邊子節(jié)點(diǎn)開始找

(2)?得到關(guān)鍵字D和G，D<F<G,所以從D、G中間節(jié)點(diǎn)找

(3)?最終找到F

b樹的其他操作由于篇幅的問題，以及與題目關(guān)系不大，不做表述，感興趣的可以到網(wǎng)上查找資料了解下。

(二)b+樹:======================================================

b+樹的定義:

b+樹與b基本相同，主要有以下區(qū)別(樹的階數(shù)為M):

(1)?b+樹中具有n個(gè)關(guān)鍵字的的節(jié)點(diǎn)含有n個(gè)分支，而b樹中具有n個(gè)關(guān)鍵字的的節(jié)點(diǎn)含有n+1個(gè)分支

(2)?B+樹中非根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n取值范圍為ceil(M/2)≤n≤M,根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n取值范圍為2≤n≤M，而b樹中這兩個(gè)取值范圍分別為ceil(M/2)-1≤n≤M-1和2-1≤n≤M-1

(3)?b+樹中非葉子節(jié)點(diǎn)中僅僅起到索引作用，即節(jié)點(diǎn)中索引只包含對應(yīng)子樹最大關(guān)鍵字和指向子樹的指針，不包含關(guān)鍵字對應(yīng)記錄的存儲地址。而b樹中每個(gè)關(guān)鍵字包含對應(yīng)的存儲地址。

(4)?b+樹中葉子節(jié)點(diǎn)包含信息，葉子節(jié)點(diǎn)包含所有關(guān)鍵字，關(guān)鍵字包含對應(yīng)的存儲地址信息。

(5)?b+樹中有一個(gè)指針指向葉子節(jié)點(diǎn)中最小的關(guān)鍵字所在的節(jié)點(diǎn)(如下圖中P)，所有的葉子節(jié)點(diǎn)鏈接成一個(gè)線性鏈表,二b樹沒有

?

從這些區(qū)別中可引申出一個(gè)問題，mysql中為什么使用b+樹，而不使用b樹:

1、B+樹的層級更少：相較于B樹B+每個(gè)非葉子節(jié)點(diǎn)存儲的關(guān)鍵字?jǐn)?shù)更多，樹的層級更少所以查詢數(shù)據(jù)更快；

2、B+樹查詢速度更穩(wěn)定：B+所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定;

3、B+樹天然具備排序功能：B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會比B樹高。

4、B+樹全節(jié)點(diǎn)遍歷更快(全表掃描)：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點(diǎn)即可，，而不需要像B樹一樣需要對每一層進(jìn)行遍歷，這有利于數(shù)據(jù)庫做全表掃描。

更多面試題或?qū)W習(xí)資源可查看我主頁或評論獲取