淺談B樹 B+樹 紅黑樹

• 二叉查找樹（BST）
• • 特性
  • 結構
• 紅黑樹
• • 定義
  • 結構
  • 性質
  • 變換方式
  • • 1.改變顔色（紅變黑，黑變紅）
    • 2.左旋
    • 3.右旋
  • mysql索引是否可以使用紅黑樹
• B樹（二叉排序樹） B-Tree：B樹 N叉的排序樹
• • 定義
  • m 階的定義
  • 結構
  • • 根節點
    • 内部節點
    • 葉子節點
  • 分裂
  • • 分裂示例
• B+樹
• • 定義
  • 結構
  • B+Tree和BTree的差別
  • 建構一個B+Tree的過程
  • 每一個結點中是如何決定要存儲多少資料的呢
  • 為什麼mysql使用B+Tree做索引而不是使用BTree或者是紅黑樹
• 參考文章

二叉查找樹（BST）

特性

1.如果它的左子樹不為空，則左子樹上結點的值都小于根結點

2.如果它的右子樹不為空，則右子樹上結點的值都大于根節點

3.子樹同樣也要遵循以上兩點

4.二叉樹的周遊方式：前 中 後 層次

5.隻要一棵樹是二叉搜尋樹，那麼它的中序周遊一定是有序的。

結構

紅黑樹

定義

一種自平衡的二叉查找樹。

結構

性質

1.每個結點不是紅色就是黑色

2.不可能有連在一起的紅色結點

3.根結點都是黑色root

4.每個紅色結點的兩個子結點都是黑色；葉子節點都是黑色：出度為0，滿足了性質就可以近似為0了。

5.每個葉子節點（NIL）是黑色。 注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點

6.如果一個結點是紅色的，則它的子結點必須是黑色的

7.從一個結點到該結點的子孫結點的所有路徑上包含相同數目的黑節點。確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對接近平衡的二叉樹。

變換方式

為了滿足紅黑樹的性質，紅黑樹有三種變換方式：

1.改變顔色（紅變黑，黑變紅）

目前結點的父親是紅色，且它的祖父結點的另一個子結點也是紅色（叔叔結點）
1）把父節點設為黑色
2）把叔叔結點設為黑色
3）把祖父也就是父親的父親設為紅色（爺爺）
4）把指針定義到祖父結點設為目前要操作的（爺爺）分析的點變換的規則
           

2.左旋

針對于左旋，但是點上面的子樹也要跟着旋轉。

目前父結點是紅色，叔叔是黑色的時候，且目前的結點是右子樹。左旋以父結點作為左旋。
           

3.右旋

目前父結點是紅色，叔叔是黑色的時候，且目前的結點是左子樹，進行右旋。
1）把父結點變為黑色
2）把祖父結點變為紅色
3）以祖父結點旋轉（爺爺）
           

總之：

左旋隻影響旋轉結點和其右子樹的結構，把右子樹的結點往左子樹挪了。

右旋隻影響旋轉結點和其左子樹的結構，把左子樹的結點往右子樹挪了。

mysql索引是否可以使用紅黑樹

首先我們先了解一下磁盤，記憶體和固态硬碟的速度，從快到慢依次為：記憶體>固态硬碟>磁盤。原因：在磁盤中存儲資料的時候，是一頁一頁的存儲的。每一頁可以存儲16k左右的資料，且一批資料存儲的時候，在磁盤上存儲的位置是不連續的。是以從磁盤讀取資料的時候，無法連續的擷取到資料。如：A和B資料存儲在了磁盤上，但是存儲到了不同的區間，讀取的時候，先擷取到了A資料，然後再進行第二次磁盤讀取去擷取B資料。

是以通過磁盤讀取資料的時候，存在兩個問題：

1.讀取磁盤的次數過多

2.讀取磁盤的浪費太多

B樹（二叉排序樹） B-Tree：B樹 N叉的排序樹

BTree和B+Tree的參考連結

https://www.jianshu.com/p/ac12d2c83708.

定義

B 樹是為了磁盤或其它儲存設備而設計的一種多叉平衡查找樹。（相對于二叉，B樹每個内結點有多個分支，即多叉）

B樹又可以寫成B-樹/B-Tree，并不是B“減”樹，橫杠為連接配接符，容易被誤導

通常我們說m階的B樹，它必須滿足如下條件：

每個節點最多隻有m個子節點。

每個非葉子節點（除了根）具有至少⌈ m/2⌉子節點。

如果根不是葉節點，則根至少有兩個子節點。

具有k個子節點的非葉節點包含k -1個鍵。

所有葉子都出現在同一水準，沒有任何資訊（高度一緻）。

m 階的定義

一個節點能擁有的最大子節點數來表示這顆樹的階數。

舉個例子：

如果一個節點最多有 n 個key，那麼這個節點最多就會有 n+1 個子節點，這棵樹就叫做 n+1（m=n+1）階樹

結構

B樹中一個節點的子節點數目的最大值，用m表示，假如最大值為10，則為10階，如圖

根節點

節點【10】即為根節點，特征：根節點擁有的子節點數量的上限和内部節點相同，如果根節點不是樹中唯一節點的話，至少有倆個子節點（不然就變成單支了）。在m階B樹中（根節點非樹中唯一節點），那麼有關系式2<= M <=m，M為子節點數量；包含的元素數量 1<= K <=m-1,K為元素數量。

内部節點

節點【13,16,19】、節點【3,6】都為内部節點，特征：内部節點是除葉子節點和根節點之外的所有節點，擁有父節點和子節點。假定m階B樹的内部節點的子節點數量為M，則一定要符合（m/2）<= M <=m關系式，包含元素數量M-1；包含的元素數量 （m/2）-1<= K <=m-1,K為元素數量。m/2向上取整。

葉子節點

節點【1,2】、節點【11,12】等最後一層都為葉子節點，葉子節點對元素的數量有相同的限制，但是沒有子節點，也沒有指向子節點的指針。特征：在m階B樹中葉子節點的元素符合（m/2）-1<= K <=m-1。

分裂

紅黑樹如果不滿足紅黑樹性質的時候，會發生改變顔色，左旋和右旋。同理，B樹如果不滿足它的性質的時候，會發生分裂。

分裂示例

如上圖是一個5階的B樹，此時需要插入8。正常來說會被插入到7和14之間，但是由于該B樹是5階，是以需要進行分裂。分裂過程為：7所在的結點為中間結點，是以将7結點更新為父節點，左側的1核3作為7的左子節點，右側的8核14作為7的右子節點。

B+樹

定義

mysql的索引主要有兩種結構：B+Tree索引和Hash索引。我們平常所說的索引，如果沒有特别指明，一般都是指B樹結構組織的索引(B+Tree索引)。

結構

B+Tree和BTree的差別

1.葉子結點連接配接起來了（看第三層）

2.非葉子結點不存儲資料

3.資料和結點一樣多

從上圖中可以看到，在根節點中有兩個資料，一個是9，一個是18，9是左子節點的最右側，18是右子節點的最右側。在左子節點中：有三個子節點，其中1是最左的子節點的最右側，8是中間子節點的最右側，9是右邊子節點的最右側。同理右子節點。是以這樣在第三行的結點中，資料便是一個有序的順序了。

BTree所有的點都會存儲資料，那麼就會造成空間浪費。沒有解決範圍查找。B+Tree解決了這個問題：

B+Tree的性質：所有非葉子結點都不存mysql的資料，在葉子結點上加了一個雙向連結清單。

1.每個結點最多有m個子節點

2.除了根節點之外，每個結點至少有m/2個子節點，如果結果除不盡，就向上取整。

3.根節點要麼是空，要麼是獨根，否則至少有2個子節點。

4.有k個子節點的結點必有k個關鍵碼

5.葉子結點的高度一緻。

建構一個B+Tree的過程

mysql索引查詢的時候有最左原則

假設我們使用了A+B+C建立了聯合索引，實際上是使用A作為root結點建立了一個樹。當我們查詢的時候，根據查詢條件中的A=x從root開始查找，找到x之後，在x的子節點中尋找B，然後再找C，這樣就走了索引。是以如果在查詢條件中沒有A的話，就不會走root索引了。

但是如果查詢條件是B+C，而沒有A的話，其實還是走了索引的，隻不過是進行全表掃描所有的索引。

另外：

每一個結點中是如何決定要存儲多少資料的呢

首先磁盤中的每一頁能夠存儲的資料大小是16k左右。當我們給mysql建立索引的時候，選擇了某一個字段建立索引，這個字段值是有大小的。如果該字段值小，那麼每一個結點中能夠存儲的數量就可以多，如果字段值大，那麼每一個結點中能夠存儲的數量就會小，這樣的話，該B+Tree的層級就會很高，不利于快速查找。

為什麼mysql使用B+Tree做索引而不是使用BTree或者是紅黑樹

首先，BTree和紅黑樹都是在結點上存儲資料，而B+Tree的結點隻存儲索引，隻有葉子結點存儲資料。

B樹的内部節點都是存儲實際資料的，增大了節點大小，增加了磁盤IO次數（磁盤IO一次讀出的資料量大小是固定的，單個資料變大，每次讀出的就少，IO次數增多，一次IO多耗時）

B+樹内部節點隻作為導向作用，b+樹的每個節點的孩子數更多，整個樹的高度就更低，大大增加查詢效率。

B+樹的葉子節點有連結清單相連，适合範圍查詢，相鄰頁直接讀取。

在大規模資料存儲的時候，紅黑樹往往出現由于樹的深度過深而造成磁盤 IO 讀寫過于頻繁，進而導緻效率低下的情況。

B+ 樹的深度更小，IO較少，效率更高

參考文章

https://blog.csdn.net/endlu/article/details/51720299.

https://www.cnblogs.com/skywang12345/p/3245399.html.

https://www.jianshu.com/p/e136ec79235c.

https://blog.csdn.net/qq_36610462/article/details/83277524.

https://www.cnblogs.com/lianzhilei/p/11250589.html.