【面試普通人VS高手系列】b樹和b+樹的理解
數據結構與算法問題，困擾了無數的小夥伴。
很多小夥伴對數據結構與算法的認知有一個誤區，認為工作中沒有用到，為什麼面試要問，問了能解決實際問題？
圖靈獎獲得者： Niklaus Wirth 說過： 程序=數據結構+算法， 也就說我們無時無刻都在和數據結構打交道。
只是作為Java開發，由於技術體系的成熟度較高，使得大部分人認為：程序應該等於 框架 + SQL 呀？
今天我們就來分析一道數據結構的題目：」B樹和B+樹「。
關於這個問題，我們來看看普通人和高手的回答！
普通人：
嗯. 我想想 … 嗯… Mysql裏面好像是用了B+樹來做索引的！ 然後…
高手：
為了更清晰的解答這個問題，我打算從三個方面來回答：
- 了解二叉樹、AVL樹、B樹的概念
- B樹和B+樹的應用場景
- B樹是一種多路平衡查找樹，為了更形象的理解。
二叉樹，每個節點支持兩個分支的樹結構，相比於單向鏈表，多了一個分支。
二叉查找樹，在二叉樹的基礎上增加了一個規則，左子樹的所有節點的值都小於它的根節點，右子樹的所有子節點都大於它的根節點。
二叉查找樹會出現斜樹問題，導致時間複雜度增加，因此又引入了一種平衡二叉樹，它具有二叉查找樹的所有特點，同時增加了一個規則：」它的左右兩個子樹的高度差的絕對值不超過1「。平衡二叉樹會採用左旋、右旋的方式來實現平衡。
而B樹是一種多路平衡查找樹，它滿足平衡二叉樹的規則，但是它可以有多個子樹，子樹的數量取決於關鍵字的數量，比如這個圖中根節點有兩個關鍵字3和5，那麼它能夠擁有的子路數量=關鍵字數+1。
因此從這個特徵來看，在存儲同樣數據量的情況下，平衡二叉樹的高度要大於B樹。
B+樹，其實是在B樹的基礎上做的增強，最大的區別有兩個：
-
- B樹的數據存儲在每個節點上，而B+樹中的數據是存儲在葉子節點，並且通過鏈表的方式把葉子節點中的數據進行連接。
- B+樹的子路數量等於關鍵字數
這個是B樹的存儲結構，從B樹上可以看到每個節點會存儲數據。
這個是B+樹，B+樹的所有數據是存儲在葉子節點，並且葉子節點的數據是用雙向鏈表關聯的。
2.B樹和B+樹，一般都是應用在文件系統和數據庫系統中，用來減少磁盤IO帶來的性能損耗。
以Mysql中的InnoDB為例，當我們通過select語句去查詢一條數據時，InnoDB需要從磁盤上去讀取數據，這個過程會涉及到磁盤IO以及磁盤的隨機IO
我們知道磁盤IO的性能是特別低的，特別是隨機磁盤IO。
因為，磁盤IO的工作原理是，首先系統會把數據邏輯地址傳給磁盤，磁盤控制電路按照尋址邏輯把邏輯地址翻譯成物理地址，也就是確定要讀取的數據在哪個磁道，哪個扇區。
為了讀取這個扇區的數據，需要把磁頭放在這個扇區的上面，為了實現這一個點，磁盤會不斷旋轉，把目標扇區旋轉到磁頭下面，使得磁頭找到對應的磁道，這裡涉及到尋道事件以及旋轉時間。
很明顯，磁盤IO這個過程的性能開銷是非常大的，特別是查詢的數據量比較多的情況下。
所以在InnoDB中，乾脆對存儲在磁盤塊上的數據建立一個索引，然後把索引數據以及索引列對應的磁盤地址，以B+樹的方式來存儲。
如圖所示，當我們需要查詢目標數據的時候，根據索引從B+樹中查找目標數據即可，由於B+樹分路較多，所以只需要較少次數的磁盤IO就能查找到。
3.為什麼用B樹或者B+樹來做索引結構？原因是AVL樹的高度要比B樹的高度要高，而高度就意味着磁盤IO的數量。所以為了減少磁盤IO的次數，文件系統或者數據庫才會採用B樹或者B+樹。
以上就是我對B樹和B+樹的理解！
總結
數據結構在實際開發中非常常見，比如數組、鏈表、雙向鏈表、紅黑樹、跳躍表、B樹、B+樹、隊列等。
在我看來，數據結構是編程中最重要的基本功之一。
學了順序表和鏈表，我們就能知道查詢操作比較多的場景中應該用順序表，修改操作比較多的場景應該使用鏈表。
學了隊列之後，就知道對於FIFO的場景中，應該使用隊列。
學了樹的結構後，會發現原來查找類的場景，還可以更進一步提升查詢性能。
基本功決定大家在技術這個崗位上能夠走到的高度。
好的，本期的普通人VS高手面試系列就到這裡結束了，喜歡的朋友記得點贊收藏。
如果最近大家遇到一些場景類和方案設計類的問題，歡迎私信我，我在後續的內容中給大家做解答！
部分高手面試文檔已整理，需要的小夥伴可以私信或者評論區留言。
