樹結構系列開篇：聊聊如何學習樹結構？

樹結構圖怎麼做

本文轉載自【微信公眾號：陳樹義，ID：gh_b6f5025d4a8d 】經微信公眾號授權轉載，如需轉載與原文作者聯絡

樹是一種非常實用的資料結構，最常用的就是資料庫的索引，用於在海量資料查詢目標值。舉個例子，如果你的表有 1 億的資料。如果使用連結串列來儲存，那麼你最壞情況下需要遍歷 1 億次才能找到目標值。

但如果你使用紅黑樹來查詢，那你最壞情況下的時間複雜度為 O （logN），即最壞只需要 27 次就可以找到。27 次查詢與 1 億次的查詢，這中間相差了 300 萬倍，由此可見樹結構帶來的效率提升之巨大！

那我們應該如何去學習樹這種資料結構呢？

其實樹這種資料結構也是有其知識體系的，每一種樹結構的誕生都有其原因及實際場景。

我們需要找到這種場景，梳理出一條主線，將這些知識點串起來，形成一個知識體系。

例如我們所知道的樹結構有：

樹

二叉樹

二叉查詢樹

二叉平衡樹

AVL 樹

紅黑樹

B - 樹

B + 樹

樹堆

2-3 樹

伸展樹

Trie 樹

字母樹

哈夫曼樹

等等

關於樹的資料結構數不勝數，讓我們眼花繚亂。但在這麼多樹結構中，我梳理出了一條主要的核心鏈路。這條核心鏈路涵蓋了我們日常最長使用的樹結構，並且它們之間還是關聯密切的，這條鏈路我取名叫：

樹結構大道！

樹結構大道開始於最基礎的樹的定義，它最為簡單、沒有過多的限制。在樹定義的基礎上，如果我們限制每個節點最多有兩個子樹，那麼它就變成了二叉樹。在二叉樹的基礎上，如果我們限制左節點要小於本節點、右節點要大於本節點，那麼它就變成了二叉查詢樹（BST）。

二叉搜尋樹在最壞的情況下會演變成連結串列，即二叉搜尋樹的左右子樹失衡了（根節點的左邊一個節點都沒有，所有節點都偏向右邊了）。而我們都知道樹的查詢效率取決於樹的高度，如果演變成連結串列，那麼查詢效率就從 O （logN） 變成了 O（N）。為了控制左右子樹的高度，就誕生了平衡二叉樹這種結構。

平衡二叉樹就是用來解決二叉查詢樹失衡問題的。

我們最常聽見的 AVL 樹和紅黑樹，其實都是平衡二叉樹，只不過它們的側重點不同。AVL 樹側重於查詢多、增刪少的場景，因此其平衡度較高。而紅黑樹側重於增刪頻繁的場景，因此其平衡度較低。

平衡二叉樹基本上能解決絕大多數的問題，但此時又有一次問題誕生了。如果我們的樹結構很大，有幾十億的資料，我們如何去搭建一顆平衡二叉樹？最常見的是資料庫一個表幾十億的資料，我們如何對其進行排序？如果直接將資料載入到記憶體，那麼記憶體勢必會爆表，不可行。

此時 B 樹（B-Tree）誕生了！

B 樹採用磁碟塊的方式解決了資料儲存空間的問題。簡單地說，使用平衡二叉樹時我們的樹節點每次只能比較一個值。如果有幾十億個節點，那我們就必須往記憶體中載入幾十億個數字，構建幾十億個樹節點。而 B 樹的一個節點對應了一個磁碟塊，而這一個磁碟塊有 4KB 大小的資料，這樣我們所構建的樹節點規模就縮減了 4K 倍之巨！

B 樹透過增加每個節點的資料數量，減少了載入到記憶體的資料大小、樹的高度，從而解決了平衡二叉樹在大資料量查詢時的可行性及效率問題。

但 B 樹還有一個問題，即它在範圍查詢方面效能很差。

此時 B+ 樹（B+ Tree）誕生了！

B+ 樹在 B 樹的基礎上，在每個根節點新增一個向右的指標，可以直接獲取到下一個元素。透過這種方式，我們只需要找到查詢範圍裡最小的元素之後，再做一次連結串列查詢就可以了，極大地提高了查詢效率。

簡單地說，B+ 樹透過葉節點的指標，解決了 B 樹範圍查詢效率慢的問題。

看到這裡，我們的「樹結構大道」基本上結束了。我們從最基礎的樹結構出發，一路經過二叉樹、二叉查詢樹、平衡二叉樹（AVL 樹、紅黑樹）、B 樹、B + 樹。透過它們的誕生背景及應用場景，將它們串了起來。

要注意的是 B 樹與 B+ 樹並不是二叉樹。

經過這麼一梳理，你會發現我們所說的內容已經涵蓋大部分日常知識點。

那麼剩下的知識點怎麼辦呢？我的建議是遇到的時候單獨瞭解，然後將其新增到我們的知識體系中。

到目前為止，我的樹結構知識體系如下圖所示：