從頭到尾,都是精華,面試大廠應該注意哪些問題

安卓馬安 2021-09-18 22:34:18 阅读数:901

到尾 都是 注意

MySQL為何不選擇平衡二叉樹

既然平衡二叉樹解决了普通二叉樹的問題,那麼mysql為何不選擇平衡二叉樹作為索引呢?

索引需要存儲什麼

讓我們想一想,如果我們要把索引存起來,那麼應該存哪些信息呢,它應該存儲三塊信息:

  • 索引的值:就是錶裏面索引列對應的值。

  • 數據的磁盤地址(通過磁盤地址找到當前數據)或者直接存儲整條數據。

  • 子節點的引用:我們需要從根節點往下走,所以需要知道左右子節點的地址。 根據這三點,可以有如下大致的一個簡單的結構圖:

從頭到尾,都是精華,面試大廠應該注意哪些問題_程序員

上圖中數字錶示的是索引的值,0x開頭的錶示磁盤地址,根節點中存了左右節點的引用。

AVL樹用來存儲索引存在什麼問題

我們知道,頁(Page)是 Innodb 存儲引擎用於管理數據的最小磁盤單比特,頁的默認大小為16KB。頁也就是上圖中的節點,每查詢一次節點就需要進行一次IO操作,IO操作是一種非常耗時的操作,很多業務系統的瓶頸都是卡在IO操作上,所以如果我們需要提高查詢效率的辦法之一就是减少IO次數,那麼問題就來了,AVL樹一個節點上只存了一個關鍵字(索引值)+一個磁盤地址+左右節點的引用,這是遠遠達不到16KB的,會浪費了大量的空間。

上圖中如果我們要找到6這條數據,需要進行3次IO(獲取一個節點就是一個IO操作),如果這棵樹很高的話,就會進行大量的IO操作,所以說AVL樹存在的最大問題就是空間利用不足,浪費了大量空間,數據量大的時候就會成為一顆瘦高的樹,那麼我們可以怎麼改進呢?答案很明顯了,那就是每個磁盤塊多存一點東西,也就是說每個磁盤多存幾個關鍵字,因為關鍵字越多,路數越多;路數越多,樹也就越矮越胖,相應的操作IO次數就會越少。

多路平衡樹(Balanced Tree)

多路平衡樹簡稱B樹,又稱B-樹,和AVL樹一樣,B樹在枝節點和葉子節點存儲鍵值、磁盤地址、左右節點引用。請看下圖的一個多路平衡樹的示例:

從頭到尾,都是精華,面試大廠應該注意哪些問題_Java_02

B樹的特點

相比較AVL樹,B樹一個磁盤上可以存多個關鍵字(值),而且有一個特點就是:

  • 分叉數(路數)永遠比關鍵字數多1。 我們可以畫出如下簡圖(下圖中只畫了3路,即兩個關鍵字,實際取决於一頁能存儲多少個關鍵字):

從頭到尾,都是精華,面試大廠應該注意哪些問題_Java_03

從上圖可以很明顯的看出,同樣高度的樹,B樹能存的數據遠遠大於平衡二叉樹。

B樹是如何查找數據的

以上圖為例,假如我們要找key=32這個數字,首先獲取到根節點,發現18小於key,所以往右邊走,獲取到右邊的數據,54和76,這時候遵循以下原則:

  • key<54,命中最左邊分叉;

  • key=54,直接命中,返回數據;

  • 54<key<76,走中間的一個分叉;

  • key=76,直接命中,返回數據;

  • key>76,命中右邊分支; 這裏因為key=32,所以走得是第1條,命中左邊分支,這時候再去獲取左邊分支,獲取到32和50,比較發現key=32,命中,返回數據。

從上面我們可以看出B樹效率相對於AVL樹,在數據量大的情况效率已經提高了很多,那麼為什麼MySQL還是不選擇B樹作為索引呢? 那麼接下來讓我們先看看改良版的B+樹,然後再下結論吧!

B+樹

B+樹由B樹改良而來,屬於改良版的多路平衡查找樹。 首先讓我們來看看B+樹到底長什麼樣呢:

從頭到尾,都是精華,面試大廠應該注意哪些問題_Java_04

對比B+樹,我們可以發現一個很明顯的區別就是葉子節點有一個箭頭指引而且從左到右是有序的。

InnoDB中使用的B+樹相比較於傳統B+樹,改進之後的B+樹具有以下特點

InnoDB中B+樹的特點

  • 它的關鍵字的數量是跟路數相等的。

  • B+樹的根節點和枝節點中都不會存儲數據,只有葉子節點才存儲數據。而搜索到關鍵字不會直接返回,會到最後一層的葉子節點。

  • B+樹的每個葉子節點增加了一個指向相鄰葉子節點的指針,它的最後一個數據會指向下一個葉子節點的第一個數據,形成了一個有序鏈錶的結構。

  • 它是根據左閉右開的區間來檢索數據的 按照B+樹的特點,我們可以畫出一個存儲數據的簡圖,如下:

從頭到尾,都是精華,面試大廠應該注意哪些問題_Java_05

總結

無論是哪家公司,都很重視高並發高可用的技術,重視基礎,重視JVM。面試是一個雙向選擇的過程,不要抱著畏懼的心態去面試,不利於自己的發揮。同時看中的應該不止薪資,還要看你是不是真的喜歡這家公司,是不是能真的得到鍛煉。其實我寫了這麼多,只是我自己的總結,並不一定適用於所有人,相信經過一些面試,大家都會有這些感觸。

最後我整理了一些面試真題資料,技術知識點剖析教程,還有和廣大同仁一起交流學習共同進步,還有一些職業經驗的分享。

 CodeChina開源項目:【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】

從頭到尾,都是精華,面試大廠應該注意哪些問題_程序員_06

版权声明:本文为[安卓馬安]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918223418262g.html