項目場景：

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

---

問題分析與描述：

從二方面方面來思考：

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

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

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

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

????????

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

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

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

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

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

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

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

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

?如下圖所示，這個是 B+樹，B+樹的所有數(shù)據(jù)是存儲在葉子節(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ù)時，InnoDB 需要從磁盤上去讀取數(shù)據(jù)，這個過程會涉及到磁盤 IO 以及磁盤的隨機(jī) IO（如圖所示） 我們知道磁盤 IO 的性能是特別低的，特別是隨機(jī)磁盤 IO。 因為，磁盤 IO 的工作原理是，首先系統(tǒng)會把數(shù)據(jù)邏輯地址傳給磁盤，磁盤控制電路按照尋址邏輯把邏輯地址翻譯成物理地址，也就是確定要讀取的數(shù)據(jù)在哪個磁道，哪個扇區(qū)。

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

?

????????很明顯，磁盤 IO 這個過程的性能開銷是非常大的，特別是查詢的數(shù)據(jù)量比較多的情況下。 所以在 InnoDB 中，干脆對存儲在磁盤塊上的數(shù)據(jù)建立一個索引，然后把索引數(shù)據(jù)以及 索引列對應(yīng)的磁盤地址，以 B+樹的方式來存儲。 如圖所示，當(dāng)我們需要查詢目標(biāo)數(shù)據(jù)的時候，根據(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ù)庫才會采用 B 樹或者 B+樹。

結(jié)尾

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

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

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

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

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