當妹子問你心裡有沒有B-Tree的時候，請把這篇文章甩給她看

2020-03-14 14:16:23 享學課堂online

B-Tree的初衷是希望通過減少存儲I / O操作來減少在計算機硬盤驅動器上花費的時間。該技術在數據庫和文件系統等計算機領域中發揮了很好的作用。B-Tree及其變體在數據存儲方面發揮著前所未有的重要作用。

什麼是B-Tree？

B-Tree是一種自平衡樹（即所有葉節點具有相同的高度級別）數據結構。但與其他如二叉樹，紅黑樹和AVL樹不只有2個子節點不同，B-Tree的節點具有2個以上的子節點。因此，有時它被稱為M-way分支樹，因為B-Tree中的節點可以具有M個子節點（M> = 2）。

圖1：B樹的一個例子

根節點，內部節點和葉節點

內部節點是具有子節點的節點。內部節點位於樹的底部上方。在圖1中，節點[3 | 6]，節點[12 | 15 | 19 | 26]和節點[33 | 36]是內部節點。

葉子節點是沒有子節點的節點。它們是樹底部的節點。在圖1中，節點[1 | 2]，節點[4 | 5]，節點[20 | 22 | 25]和節點[31 | 32]是一些葉節點。

B-Tree的根節點是一個特殊節點。B-Tree只有一個根節點，它位於樹的頂部。根據B-Tree中的項目數，根節點可以是內部節點或葉節點。節點[9 | 30]是圖1中B樹的根節點。

B-Tree節點的屬性

每個節點可以有一堆密鑰和一堆子節點（子節點），其中子節點數可以是0或其鍵的總數加1.讓我們考慮節點[x]。如果node [x]是葉子節點，那麼它將沒有任何子節點。如果它是一個內部節點，那麼它的子節點總數是n [x] + 1，其中n [x]是其鍵的總數。

B-Tree的約束

令t為B樹的最小度，其中t > = 2

約束＃1：除根節點以外的每個節點必須至少有（t -1）個密鑰。它是B-Tree節點中鍵總數的下限。

約束＃2：包含根節點的每個節點必須至多具有（2 t - 1）個密鑰。所以我們說如果節點有（2 t - 1）個鍵，那麼節點已滿。它是B-Tree節點中鍵總數的上限。

約束＃3：每個內部節點（根節點除外）必須至少有t個子節點。每個內部節點（包括根節點）必須具有至多2 級的兒童。

約束＃4：節點中的密鑰必須按升序存儲。例如，在圖1中，節點[12 | 15 | 19 | 按鍵12

約束＃5：密鑰左側的子節點的所有密鑰必須小於該密鑰。在圖1中，位於密鑰30左側的子節點是節點[12 | 15 | 19 | 26]，節點[10 | 11]，節點[13 | 14]，節點[16 | 18]，節點[20 | 22 | 25]和節點[28 | 他們的鑰匙小於30。

約束＃6：密鑰右側的子節點的所有密鑰必須大於該密鑰。例如，在圖1中，位於鍵9右側的子節點是節點[12 | 15 | 19 | 26]，節點[10 | 11]，節點[13 | 14]，節點[16 | 18]，節點[20 | 22 | 25]和節點[28 | 他們的鑰匙大於9。

對於約束＃4和約束＃5，通常鍵的左側的所有節點必須具有小於它的鍵。

對於約束＃4和約束＃6，通常鍵的右側的所有節點必須具有大於它的鍵。

在圖1中，B樹的最小度為3，因此其下界為2，其上界為5。

如果你密切關注圖1中B-Tree的例子，你會注意到任何節點中的一個鍵實際上是該鍵左側和右側較低級別節點中所有鍵的範圍分隔符。

讓我們看一下節點[9 | 30]所示，鍵9左側的下部節點的鍵（由藍色箭頭鏈接的節點中的鍵）小於9，鍵9右側的下部節點的鍵（節點中的鍵）由綠色箭頭鏈接的大於9。鍵30左側的較低節點的鍵（由綠色箭頭鏈接的節點中的鍵）小於30，右側的較低節點的鍵（由紅色箭頭鏈接的節點中的鍵）大於30。這種B-Tree模式使得鍵搜索類似於二叉樹的鍵搜索。

只要B樹操作不違反上述約束，它就會自動進行自我平衡。換句話說，約束是這樣設計的，以保持其平衡屬性。

最小度數（t）與B樹高度（h

）成反比，增加t將減少h。但是，較大的t意味著在節點中花費更多時間來搜索密鑰和遍歷子節點。

B-Tree操作的概念和偽代碼

左右兄弟節點

節點的左右兄弟是其在同一級別的右側或左側的節點。

兄弟節點

節點健的前置和後繼

在本文中，此處提到的前置節點和後繼節點僅適用於內部節點。

前置是左側子樹內的葉節點中數值最大的那個節點。

同樣的，後繼是右側子樹內的葉節點中數值最小的節點。

節點的前置和後繼

在圖3中，節點17的前置節點是[13 | 14 | 16] 因為健16其左側最大的鍵值。節點17的後繼者是節點[19 | 20 |21] 因為鍵值19是其右側的最小鍵值。

拆分節點

對於插入，如果我們要插入的節點已滿（有時也稱為溢出），我們需要拆分一個節點，使其不違反約束＃2。

圖4-a：在B-tree中分裂

圖4-a：B-Tree中的另一個分裂

左右旋轉

對於刪除，從節點中刪除密鑰可能違反約束＃1（有時也稱為下溢）。如果其中一個鍵的鍵數大於下限，我們可以將其左側或右側兄弟中的一個鍵移動（借用）到該節點。

圖5-a：左旋轉

圖5-b：右旋轉

與左右兄弟合併

如果無法左/右旋轉，則將節點與其兄弟節點合併。

圖6：左兄弟合併

實現B-tree操作的一般概念

更復雜的一些邏輯在於健值的插入，刪除動作。B-Tree鍵插入涉及拆分節點，而鍵刪除涉及旋轉和合並。

為了完成鍵值插入或刪除，我們需要遵守的一條重要原則是：在執行操作之前，目標鍵值必須位於葉子節點中。如果鍵值位於內部節點中，則需要先將其交換到葉節點中。

鍵值搜索

<code>


1.  `Key-Search  (searched-key)`

3.  `Current-Processed-Node  =  Root-Node`

5.  `While  (Current-Processed-Node  is  not NULL)`

6.  `Current-Index  =  0`

8.  `While  ((Current-Index  < key number of Current-Processed-Node) AND`

9.  `(searched-key >  Current-Processed-Node.Keys[Current-Index]))`

10.  `Current-Index++`

11.  `End  While`

14.  `If  ((Current-Index  < key number of Current-Processed-Node) AND`

15.  `(searched-key ==  Current-Processed-Node.Keys[Current-Index]))`

16.  `searched-key is found`

17.  `Return it (We are done)`

19.  `End  If`

21.  `Current-Processed-Node  =  Left/Right  Child of Current-Processed-Node`

22.  `End  While`

24.  `Return NULL`


/<code>

鍵插入

圖7：密鑰插入的示例

<code>



1.  `Split-Node(parent-node, splitted-node)`

3.  `Create  new-node`

4.  `Leaf[new-node]  =  Leaf[splitted-node]  (The  new node must have the same leaf info)`

6.  `Copy right half of the keys from splitted-node to the new node`

8.  `If  (Leaf[splitted-node]  is FALSE)  Then`

9.  `Copy right half of the child pointers from spitted-node to the new node` 


10.  `End  If`

12.  `Move some of parent children to the right accordingly`

14.  `parent-node.children[relevant index]  =  new-node`

16.  `Move some of parent keys to the right accordingly as well`

18.  `Parent-node.keys[relevant index]  = splitted-node.keys[the right-most index]`


/<code>

<code>

1.  `Insert-Key-To-Node(current-node, inserted-key)`

3.  `If  (Leaf[current-node]  == TRUE)  Then`

4.  `Put inserted-key in the node in ascending order`

5.  `Return  (We are done)`

6.  `End  If`

8.  `Find the child-node where inserted-key belong`

10.  `If  (total number of keys in child-node == UPPER BOUND)  Then`

11.  `Split-Node(current-node, child-node)`

12.  `Return  Insert-Key-To-Node(current-node, inserted-key)`

13.  `End  If`

15.  `Insert-Key-To-Node(child-node, inserted-key)`


/<code>

<code>

1.  `Insert-Key(inserted-key)`

3.  `If  (root-node is NULL)  Then` 


4.  `Allocate  for root-node`

5.  `Leaf[root-node]  = TRUE`

6.  `End  If`

9.  `If  (total number of keys in root-node == UPPER BOUND)  Then`

10.  `Create a new-node`

11.  `Assign root-node to be the child pointer of the new-node`

12.  `Assign  new-node to be the root-node`

13.  `Split-Node(new-node,  new-node.children[0])`

14.  `End  If`

16.  `Insert-Key-To-Node(new-node, inserted-key)`


/<code>

其中，Split-Node（）和Insert-Key-To-Node（）是輔助函數，最終由Insert-Key（）調用。根節點的更新由Insert-Key（）處理，其餘部分由Split-Node（）和Insert-Key-To-Node（）處理。可以觀察到，健值的插入總是發生在葉子節點處。在插入路徑期間，如果節點已滿，我們需要執行拆分並在該點重新啟動插入過程。通過這樣做，我們確保B-Tree不會因鍵值插入產生溢出問題。

鍵值刪除

圖8：鍵值刪除的示例

<code>

1.  `Delete-Key-From-Node(parent-node, current-node, deleted-key)`

3.  `If  (Leaf[current-node]  == TRUE)  Then`

4.  `Search  for deleted-key in current-node`

6.  `If  (deleted-key not found)  Then`

7.  `Return  (We are done)`

8.  `End  If`

10.  `If  (total number of keys in current-node > LOWER BOUND)  Then`

11.  `Remove the key in current-node`

12.  `Return  (We are done)`

13.  `End  If`

15.  `Get left-sibling-node and right-sibling-node of current-node`

17.  `If  (left-sibling-node is found AND total number of keys in left-sibling-node > LOWER BOUND)  Then`

18.  `Remove deleted-key from current-node`

19.  `Perform right rotation`

20.  `Return  (We are done)`

21.  `End  If`

23.  `If  (right-sibling-node is found AND total number of keys in right-sibling-node > LOWER BOUND)  Then`

24.  `Remove deleted-key from current-node`

25.  `Perform left rotation`

26.  `Return  (We are done)`

27.  `End  If` 


29.  `If  (left-sibling-node is  not NULL)  Then`

30.  `Merge current-node with left-sibling-node`

31.  `Else`

32.  `Merge current-node with right-sibling-node`

33.  `End  If`

35.  `Return  Rebalance-BTree-Upward(current-node)`

36.  `End  If`

38.  `Find predecessor-node of current-node`

40.  `Swap the right-most key of predecessor-node and deleted-key of current-node`

42.  `Delete-Key-From-Node(predecessor-parent-node, predecessor-node, deleted-key)`


/<code>

<code>

1.  `Rebalance-BTree-Upward(current-node)`

3.  `Create  Stack`

5.  `For each step of the path from root-node to current-node Then`

6.  `Stack.push(step-node)`

7.  `End  For`

9.  `While  (Stack  is  not empty)  Then`

10.  `step-node =  Stack.pop()`

11.  `If  (total number of keys in step-node < LOWER BOUND)  Then`

12.  `Rebalance-BTree-At-Node(step-node)`

13.  `Else`

14.  `Return  (We are done)`
 

15.  `End  If`

16.  `End  While`


/<code>

<code>

1.  `Rebalance-BTree-At-Node(step-node)`

3.  `If  (step-node is NULL OR step-node is root-node)  Then`

4.  `Return  (We are done)`

5.  `End  If`

7.  `Get left-sibling-node and right-sibling-node of step-node`

9.  `If  (left-sibling-node is found AND total number of keys in left-sibling-node > LOWER BOUND)  Then`

10.  `Remove deleted-key from step-node`

11.  `Perform right rotation`

12.  `Return  (We are done)`

13.  `End  If`

15.  `If  (right-sibling-node is found AND total number of keys in right-sibling-node > LOWER BOUND)  Then`

16.  `Remove deleted-key from step-node`

17.  `Perform left rotation`

18.  `Return  (We are done)`

19.  `End  If`

21.  `If  (left-sibling-node is  not NULL)  Then`

22.  `Merge step-node with left-sibling-node`

23.  `Else`

24.  `Merge step-node with right-sibling-node`

25.  `End  If` 


/<code>

<code>

1.  `Delete-Key(deleted-key)`

3.  `Delete-Key-From-Node(NULL, root-node, deleted-key)`


/<code>

根據[2]，B-Tree中有兩種流行的鍵值刪除方式：

直接在tree的最低部執行操作：在進入節點之前先重構樹，這樣當我們實際從B-Tree中刪除一個鍵時，它的結構不會違反任何約束。刪除的偽代碼可以在[3]和[4]中找到。
查找並刪除鍵值。但是我們需要向上重新平衡，因為鍵值刪除會導致B-Tree的約束違規。我們的健值刪除實例基於此策略。刪除鍵值密鑰的主方法是Delete-Key（）。稍後在Rebalance-BTree-Upward（）被調用，以在必要時重組樹。重新平衡B樹從根本上涉及左/右旋轉和左/右兄弟合併。

顯示B-Tree的工具

圖9：B樹渲染工具

最後，歡迎大家在文章下方留言進行評論，如果覺得本文寫的不錯，記得給小on 轉發、關注走一個哦！下次再會~(*￣▽￣ *)

分享到:

閱讀更多 享學課堂online 的文章

關鍵字: 數據結構電腦妹子

第二章 IoC容器和Bean配置

bean是一個對象，它是由Spring

運算裡不得不說的python模塊—math

Help

Devops度量--DevOps 現狀快速檢查表

今天主要分享一個DevOps

SOP是什麼（解讀）

SOP不是單個的，是一個體系，雖然我們可以單獨地定義每一個SOP，但真正從企業管理來看，SOP不可能只是單個的，必然是一個整體和體系，也是企業不可或缺的。

還不知道交換機上如何配置DHCP，趕緊過來圍觀吧，一分鐘包你學會

隨著終端設備的越來越多，人工干預配置IP地址，不僅工作效率低，而且，還很容易導致IP衝突，影響正常的網絡訪問。到此已經完成了，DHCP服務的配置了，我們可以在終端驗證。

還在手動配置IP地址嗎？太Low了，一分鐘教會您如何配置DHCP

Python爬蟲自學筆記：分析頭條文章網頁源文件

這兩天分析了一下頭條文章網頁的源文件，現在將分析的結果分享給大家。首先以一篇文章為例，其網址如下：https://www.toutiao.com/i6822245428176617998/如上圖網頁所示，文章中包含文字和圖片。

DNS偵查工具

我們只需要打開瀏覽器輸入例如:www.baidu.com就可以解析到該網站.為了便於記住不需要輸入長長的IP地址去訪問這就是DNS域名解析.關於域名域名的層次劃分用點來分割這時DNS把相對應的域名解析成IP地址高的在右邊.例如:www. NS簡介訪問某網站的時候最低在左邊

國人開源的異步 Python ORM：GINO

程序測評：Create React App 3.3中有哪些酷炫新功能？

Create

“明學”的魅力？我只要我覺得：駕馭終端，提高生產力

最後一個要介紹的命令是

（必收藏系列）Linux面試題——命令集

關注，後臺私信【Linux】分享Linux入門到進階電子書、Linux入門到精通視頻教程（免費）。文件管理命令cat

五分鐘學會如何在 IPFS 上部署網站

原文標題:五分鐘學會如何在

「正點原子NANO STM32F103開發板資料連載」第29章內存管理實驗

1）實驗平臺：【正點原子】

小白怎麼學Web前端開發如何成為技術達人

Web前端開發工程師已經成為了很多年輕人心中的理想工作，不僅入行門檻低、而且薪資待遇和發展前景都不錯，自然吸引了大批人加入行業。

如何開發一個web靜態服務器

我們都知道如今的web服務器有很多，比如著名的有apache，有nginx，有tomcat，有resin服務器，有sphere，有iis服務器等等，這些服務器都能提供web服務，並且幾乎都能和多種語言進行搭配使用，那麼一個web服務器都需要那些功能，開發一個web服務器都需要那些

學Java編程還有前景嗎如何才能拿到高薪

需求大、薪資高似乎是Java開發人員的標籤，不過學Java編程還有前景嗎？它架構在操作系統之上，屏蔽了底層的差異，真正實現了“Writeonce run

Python網絡爬蟲之配置篇（一）

pip

SpringBoot 整合SpringSecurity示例實現前後分離權限註解+JWT登錄認證

serverTimezone=UTC&useUnicode=true&characterEncoding=utf-8&zeroDateTimeBehavior=convertTo&useSSL=falseusername:rootpassword:

Python的運行效率太低？幾行代碼快速提升！

return的就是是你所需要的結果2.3、運行這一步就是最後一步了，只要像下面一樣輸入上述函數名，賦予參數值，點擊運行Run，就能得到你想要的結果arg1=5

python的優點是什麼？最新Python400集視頻（附教程）

2020，最新Python零基礎到精通資料教材，乾貨分享，新基礎Python教材，穩穩找到過萬工作，看這裡，這裡有你想要的所有資源哦，最強筆記，教你怎麼入門提升！獲取方式：私信小編“

MySQL中OOM故障應如何下手-愛可生

作者：孫祚龍愛可生南區分公司交付服務部成員，實習工程師。負責公司產品問題排查及日常運維工作。本文來源：原創投稿*愛可生開源社區出品，原創內容未經授權不得隨意使用，轉載請聯繫小編並註明來源。

像專家一樣使用 panic

|go

30種不同的編程語言怎麼寫“Hello, World”

printfn

percona QAN 介紹

一、背景QAN慢查詢日誌分析工具是PMM

面試官：你可以用純CSS判斷鼠標進入的方向嗎？

雖然沒什麼軟用，但是對付面試官應該是夠用了。感謝面試官提出的問題，讓我實現了這個功能，對CSS

網絡工程師職業生涯中，哪兩點是最重要的？

網絡工程師最重要的技能是紮實的基礎和非常開放的思維，微觀知識紮實、宏觀能力突出。項目經驗也會讓網絡工程師基礎更牢靠，網絡工程師是要實戰的，要避免紙上談兵，我認為對基礎理論的理解，比你清楚配置更重要。

交換機中相關術語代表什麼意思，有必要弄清楚

由淺入深瞭解以太坊 2.0：最常見問題和最全學習清單

有關以太坊2.0

【Linux簡單實用小命令001】CentOS 7、8的防火牆端口開放

yuminstall

吃透這些IPFS硬核知識點，日後搶頭礦隨時“彎道超車”

今天的你捉住IPFS機遇了嗎？我們都知道在Filecoin網絡中作為一名存儲礦工，信譽對於我們是非常重要的——信譽越高，爆塊幾率越大。那麼信譽系統現在怎麼樣了呢？

Hive分桶表

fieldsterminated

Spring中資源的加載原來是這麼一回事啊！

自己動手搭建郵件系統：怎樣讓Exchange Server 發出第一封郵件？

編輯Exchange

$【MySQL】RDS物理備份文件(.idb\.frm)恢復到MySQL自建數據庫$

【MySQL】RDS物理備份文件(.idb\.frm)恢復到MySQL自建數據庫

在阿里雲控制檯，我們能下載的文件是一個壓縮包，解壓之後，是.idb和.frm文件，你可能要問了，我可以直接把解壓好的問題件覆蓋到MySQL的data目錄下嗎？

NLP算法入門系列：隱含馬爾可夫鏈(HMM)模型的簡單介紹

即，最大化

第一章 Spring Framework概述

您可以在任何web

opencv人工智能深度學習這樣實現人臉的年齡檢測

前期的文章我們分享了人臉的識別以及如何進行人臉數據的訓練，本期文章我們結合人臉識別的模型進行人臉年齡的檢測人臉年齡的檢測步驟1、首先需要進行人臉的檢測2、把檢測到的人臉數據給年齡檢測模型去檢測3、把檢測結果呈現到圖片上人臉年齡檢測import

嵌入式linux網絡編程之——5年程序員給你深度講解socket套接字

圖8-1

深入瞭解ProcessFunction的狀態操作(Flink-1.10)

先反思為何會有上述疑惑上述疑惑產生的原因，應該是受到平時使用HashMap的影響，HashMap獲取值就是在調用get方法時指定key，設置值也是在put時指定key，所以看到state.value，看懂了這些，其實也是在瞭解DataStream/DataSetAPI的設計思路：

Redis內存分析工具--rdr安裝與使用

分析Redis

資深架構師教你源碼講解zookeeper實現分佈式鎖以及集群搭建步驟

//getData發現前一個子節點被刪除，拋出異常

一行代碼提升遷移性能

論文原址：https://arxiv.org/pdf/2003.12237.pdf開源地址：https://github.com/cuishuhao/BNM在發表在CVPR2020

利用相似幾何信息，做可泛化3D形狀分割模型

更具體的有以下三種典型的分割方案：FullyConvolutional-Like

這麼好用的開源計算器SpeedCrunch，沒有不嘗試一下的道理

介紹SpeedCrunch是一款高精度科學計算器，具有快速，鍵盤驅動的用戶界面。獲取方式在GitHub上搜索SpeedCrunch，就可以去到

分佈式緩存，真香

他是前易寶支付架構師、阿里雲MVP、騰訊雲

特徵工程的力量

在本文中，我希望教給您一些有關特徵工程的知識，以及如何使用它來對非線性決策邊界進行建模。為了說明這一點，假設恢復時間與身高和體重具有以下關係：Y=β₀+β₁+β2+β₃+noise從第三項來看，我們可以看到Y與身高和體重沒有線性關係。

java架構：天天寫面向接口編程，你考慮過性能嗎？大神都是這麼寫

public

SpringBoot如何優雅的使用RocketMQ

源碼編譯需要Maven3.2x，JDK8在根目錄進行打包:Copymvn-Prelease-all

css代碼規範工具stylelint

"mixin"