項(xiàng)目場(chǎng)景：

圖靈獎(jiǎng)獲得者（Niklaus Wirth ）說過： 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法， 也就說我們無時(shí)無刻 都在和數(shù)據(jù)結(jié)構(gòu)打交道。 只是作為 Java 開發(fā)，由于技術(shù)體系的成熟度較高，使得大部分人認(rèn)為：程序應(yīng)該等于 框 架 + SQL ？

---

問題分析與描述：

從二方面方面來思考：

• 了解二叉樹、AVL 樹、B 樹的概念
• B 樹和 B+樹的應(yīng)用

1. B 樹是一種多路平衡查找樹，為了更形象的理解，如下圖所示。

????????二叉樹，每個(gè)節(jié)點(diǎn)支持兩個(gè)分支的樹結(jié)構(gòu)，相比于單向鏈表，多了一個(gè)分支。

????????二叉查找樹，在二叉樹的基礎(chǔ)上增加了一個(gè)規(guī)則，左子樹的所有節(jié)點(diǎn)的值都小于它的根 節(jié)點(diǎn)，右子樹的所有子節(jié)點(diǎn)都大于它的根節(jié)點(diǎn)。如下圖所示。

????????

????????二叉查找樹會(huì)出現(xiàn)斜樹問題，導(dǎo)致時(shí)間復(fù)雜度增加，因此又引入了一種平衡二叉樹，它具有二叉查找樹的所有特點(diǎn)，同時(shí)增加了一個(gè)規(guī)則：”它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1“。平衡二叉樹會(huì)采用左旋、右旋的方式來實(shí)現(xiàn)平衡。如下圖所示。

????????而 B 樹是一種多路平衡查找樹，它滿足平衡二叉樹的規(guī)則，但是它可以有多個(gè)子樹，子樹的數(shù)量取決于關(guān)鍵字的數(shù)量，比如這個(gè)圖中根節(jié)點(diǎn)有兩個(gè)關(guān)鍵字 3 和 5， 那么它能夠擁有的子路數(shù)量=關(guān)鍵字?jǐn)?shù)+1。 如下圖所示。?

????????因此從這個(gè)特征來看，在存儲(chǔ)同樣數(shù)據(jù)量的情況下，平衡二叉樹的高度要大于 B 樹

B+樹，其實(shí)是在 B 樹的基礎(chǔ)上做的增強(qiáng)，最大的區(qū)別有兩個(gè)：

???????? a. B 樹的數(shù)據(jù)存儲(chǔ)在每個(gè)節(jié)點(diǎn)上，而 B+樹中的數(shù)據(jù)是存儲(chǔ)在葉子節(jié)點(diǎn)，并且通過鏈表的方? ? ? ? ? ? ? ?式把葉子節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行連接。

????????b. B+樹的子路數(shù)量等于關(guān)鍵字?jǐn)?shù)

---------------------------------------------------------------------------------------------------------------------------------

如下圖所示，這個(gè)是 B 樹的存儲(chǔ)結(jié)構(gòu)，從 B 樹上可以看到每個(gè)節(jié)點(diǎn)會(huì)存儲(chǔ)數(shù)據(jù)。

?如下圖所示，這個(gè)是 B+樹，B+樹的所有數(shù)據(jù)是存儲(chǔ)在葉子節(jié)點(diǎn)，并且葉子節(jié)點(diǎn)的數(shù)據(jù)是用雙向鏈表關(guān)聯(lián)的。

????????2. B 樹和 B+樹，一般都是應(yīng)用在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中，用來減少磁盤 IO 帶來的性能損耗。

???????? 以 Mysql 中的 InnoDB 為例，當(dāng)我們通過 select 語句去查詢一條數(shù)據(jù)時(shí)，InnoDB 需要從磁盤上去讀取數(shù)據(jù)，這個(gè)過程會(huì)涉及到磁盤 IO 以及磁盤的隨機(jī) IO（如圖所示） 我們知道磁盤 IO 的性能是特別低的，特別是隨機(jī)磁盤 IO。 因?yàn)?#xff0c;磁盤 IO 的工作原理是，首先系統(tǒng)會(huì)把數(shù)據(jù)邏輯地址傳給磁盤，磁盤控制電路按照尋址邏輯把邏輯地址翻譯成物理地址，也就是確定要讀取的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。

????????為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要把磁頭放在這個(gè)扇區(qū)的上面，為了實(shí)現(xiàn)這一個(gè)點(diǎn)，磁盤 會(huì)不斷旋轉(zhuǎn)，把目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下面，使得磁頭找到對(duì)應(yīng)的磁道，這里涉及到尋道事件以及旋轉(zhuǎn)時(shí)間。

?

????????很明顯，磁盤 IO 這個(gè)過程的性能開銷是非常大的，特別是查詢的數(shù)據(jù)量比較多的情況下。 所以在 InnoDB 中，干脆對(duì)存儲(chǔ)在磁盤塊上的數(shù)據(jù)建立一個(gè)索引，然后把索引數(shù)據(jù)以及 索引列對(duì)應(yīng)的磁盤地址，以 B+樹的方式來存儲(chǔ)。 如圖所示，當(dāng)我們需要查詢目標(biāo)數(shù)據(jù)的時(shí)候，根據(jù)索引從 B+樹中查找目標(biāo)數(shù)據(jù)即可， 由于 B+樹分路較多，所以只需要較少次數(shù)的磁盤 IO 就能查找到。

?

????????3. 為什么用 B 樹或者 B+樹來做索引結(jié)構(gòu)？原因是 AVL 樹的高度要比 B 樹的高度要高，而高度就意味著磁盤 IO 的數(shù)量。所以為了減少磁盤 IO 的次數(shù)，文件系統(tǒng)或者數(shù)據(jù)庫才會(huì)采用 B 樹或者 B+樹。

結(jié)尾

????????數(shù)據(jù)結(jié)構(gòu)在實(shí)際開發(fā)中非常常見，比如數(shù)組、鏈表、雙向鏈表、紅黑樹、跳躍表、B 樹、 B+樹、隊(duì)列等。 數(shù)據(jù)結(jié)構(gòu)是編程中最重要的基本功之一。

????????學(xué)了順序表和鏈表，我們就能知道查詢操作比較多的場(chǎng)景中應(yīng)該用順序表，修改操作比 較多的場(chǎng)景應(yīng)該使用鏈表。

????????學(xué)了隊(duì)列之后，就知道對(duì)于 FIFO 的場(chǎng)景中，應(yīng)該使用隊(duì)列。

????????學(xué)了樹的結(jié)構(gòu)后，會(huì)發(fā)現(xiàn)原來查找類的場(chǎng)景，還可以更進(jìn)一步提升查詢性能。

基本功決定大家在技術(shù)這個(gè)崗位上能夠走到的高度。