---
title: DB淺談-BTree淺談
tags: DB
description: DB淺談-BTree淺談
---
<!-- more -->
許多DB都基於BTree做存儲,
這是于1971年Rudolf Bayer,Edward M. McCreight引入的概念[1].

[1]: https://en.wikipedia.org/wiki/B-tree

先來回顧什麼是BST?^[https://hackmd.io/1gUXB4RWTmOxkKAJmYE-Kg#%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%95%B8BST]
https://icode.best/i/19809535814303
https://author.baidu.com/home?from=bjh_article&app_id=1601487176886580
https://jishuin.proginn.com/p/763bfbd2fcb3

# 二分搜索樹BST
BST是一種**有序**的**記憶體數據結構**, 可以用來高效率地進行K-V查找.
BST由多個Node組成, 每一個Node由一個Key與一個該Key關聯的值與兩個child-node指針組成.

## 樹的平衡
二元樹的insert操作本身不會遵守特定模式, insert多筆後可能導致樹的不平衡情況(它的branch比令一個branch還長很多).這稱為Pathological tree(病態樹), 看起來更像一個linked list, 這查找效率並非是我們期望的對數時間(logⁿ), 而非是像這樣的線性時間(n).

AVLTree指的是高度為logⁿ的樹, 兩個branch的高度差不大於1.
如果不進行平衡, 則樹的最終形狀是由insert和delete的順序來決定的.

保持平衡的方法, 在insert/delete後進行rotate, 針對中間節點進行旋轉, 中間節點(3)稱為旋轉軸, 它就被提昇了一層上去, 原來的parent node, 就成了right node.

## 基於硬碟存儲的樹
上一節講的平衡樹跟旋轉平衡, 如果這操作是在磁碟上, 變成需要頻繁執行, 是很不切實際的, 維護的時間成本太高了.
問題在於每個節點允許擁有的最大子節點樹(扇出Fanout)太少. 就導致需要頻繁的執行平衡操作, 重新定位節點且更新子節點的指針.
且會有```局部性(Locality)問題```, 因為元素添加的順序是隨機的, 表示無法保證新inserted的節點就剛好磁區在parent node附近寫入, 這意味著child node pointer實際指到的位子, 可能要跨越多個page, 通常是使用分頁二分樹來改善.
https://zhuanlan.zhihu.com/p/106466168
https://blog.csdn.net/imzoer/article/details/8528973
https://zhuanlan.zhihu.com/p/44373474
https://www.jianshu.com/p/d689f806c745

令一個跟尋找child node pointer的開銷, 跟```BST的高度```有關係.
因為BST的扇出數是2, 所以樹的高度是log²的對數.
必須要執行O(log²N)的查找並定位要搜索的元素.
這樣的低扇出樹的結構在記憶體內是有用的, 但在硬碟上完全不實用.

所以樹結構在磁盤上要實用必須要有
- 高扇出
- 改善相近鍵值的資料局部性
- 低高度
- 減少遍尋的尋軌次數

# BTee在硬碟上的結構
## 磁盤存儲結構
硬碟操作的最小單位是```block```這在上一節也有提到.
## [Paged Binary Tree 分頁二分樹](https://www.site.uottawa.ca/~nat/Courses/DFS-Course/DFS-Lecture-10/tsld008.htm)
通過把node做分組存儲到不同的```page```上, 來作為二分樹的設計布局.
Paged Binary Tree透過在一個page上定位多個binary node來解決問題
在Paged Binary Tree中不會為了獲得一個node而花這麼大的成本, 而是一次查找, 就把該page的多個node都給讀取出來, 為了空間局部性的考量, 通常鄰近的node也會被存取.
搜尋成本為logk+1(N+1)

有了這樣的布局, 就能思考insert/balance的順序與方式了

# 無所不在的BTee
BTree可以當程式圖書管理面一個巨大的目錄室
第一部一定是找到對應的櫃子, 再來在櫃子內找到正確的層架, 選擇抽屜, 找到你要的書.
BTree構建了一個幫助快速導航跟定位的層次結構.

BTree的重點, 它是```有序的```, 樹內的節點是按照順序存儲的.
我們平常搜尋也不會只有搜尋一筆, 再大多數的查詢語言中, 透過謂詞相等(=)來單點查找
通過謂詞比較(<、>、<=、>=), 表示範圍查找來按順序查詢多筆數據.

## BTree的層次結構
BTree由多個node組成, 每個node最多可以容納N個Key和N+1個指向pointer of child node.

BTree是一種Page Organization technique(i.e., 用來組織與定位固定大小page的技術),
所以通常Node跟Page這兩個術語, 在BTree的描述下可以相互替換.

Occupancy佔用率, 講的是節點容量與實際持有的Key個數之間的關係.

BTree的特徵在於Fanout, 除存在每個Node間的key數量.
高的fanout有助於平均分攤, btree在balance時需要做出一些結構更改的磁碟開銷.
通過在單個block或多個連續block中存儲指向child node pointer與key, 可以減少尋道的次數.
平衡時的操作(分裂與合併)會在node的key達到fanout數字時, 或node的key都為空時被觸發.

## Separator Keys分隔鍵
其中Node上的Key撐為Index entry or Separator key. 它用來把Tree切割成多個Sub tree(子樹/子範圍), 每個node內的所有key已經排好順序了, 其中也包含了對應key的範圍, 方便用來二分查找

像是要找的key為K_i, 它介於K₁與K₂, 就很方便地透過指針來到下一層的child tree.

每個node的第一個指針, 指向的是小於第一個key的child tree;
最後一個指針則是指向>=最後一個key的child tree.
其中除了頭尾兩個指針指向的child tree之外的, 都滿足一個等式 :
> K_i-1<=K_s<K_i
> K是Node上的一組key, K_s則是子樹Node的Key

有些變體的BTree也提供了雙向鍊結的指針, 在Leaf level上, 以便於範圍查詢與逆向迭代
這種樹跟BTree不同的是, 建構方式不是Top-Down, 而是Buttom-UP, 隨著Leaf level的節點滋長, 內部節點的數量與高度也隨之增加.
也因為有這特戲, 這種BTree, 會在內部節點保留了額外的空間, 方便未來的插入與更新操作.

## BTree查找複雜度
從上一章知道, 每次查找Btree其實是整個Page都讀取到記憶體中;
所以查找複雜度不只是有比較的次數, 也有傳輸block的數量.

傳輸次數而言, 每個Node的Key樹為N, 則樹每往下一層, 則Node個數會增加N倍.
選定一個pointer後, 又能把搜尋空間減少到1/N(只撈取一個Node).
所以查找期間最多尋址log_kM(M表示B樹中key的總數)個page來查找一個key.
從Root node到leaf的鍊路上, 所以經過的pointer數量就等於樹的高度(層數).

知道尋軌次數與比較次數有助於理解認識搜尋.

## B樹查找算法
上一小節知道, 要找到一個項目, 必須從root到leaf node的單向遍尋.
用來```單點查詢、更新、刪除```, 以及從```這項目開始的範圍掃描與插入```是非常有用的.

Predecessor前驅節點, 其key的左子樹中最大的值
對Key17來說, 它的左子樹最大的是16, 所以Predecessor就是16
對Key12來說, Predecessor就是10.

知道Predecessor就能知道該key是否存在.
例如查找11, 知道是12要往左子樹找,但 Predecessor只有10, 所以11一定不存在.
這對於要是key間隔很大時, 能快速判斷其不存在.
所有Key的有序性在不少時候, 是Z>B的, 至少在性能考量上是這樣.

進行Range scan範圍查找時, 從找到最近的Key開始, 順著Sibling pointer同級指針在leaf level移動, 直到範圍的尾巴結束.

## Key的數量
Page通常可以保存K到2K個Key(K個是指存儲佔用率只用了50%的話),
那該Page就是可以保存最少K+1, 最多2K+1個指向child node pointer.
Root page可以容納1到2K個Key, 之後只要一個key l被引入, 任何內部節點都可以有l+1個key
但不會超過N個Key.

超過就會引發分裂Splits.

## BTree的節點分裂
分裂會出現在有新key被insert時, 必須定位目標leaf node先, 再找到插入點.
因此在insert之前, 其實都是要先執行```查找```.

定位到leaf node後, key跟value被追加到leaf node之上.
如果目標node沒有空間追加了, 那該node就會oveerflow溢出.
就需要將其分裂成兩個節點, 才能追加新的key

因此要分裂節點, 要滿足以下任一個條件
1. 對於leaf node, 節點最多可以容納N個key時, 再追加一個key就超過N
2. 非leaf node, 節點最多容耐N+1個pointer, 再追加一個pointer就超過N+1

Split主要是透過分配新node, 把一半元素從原節點移動過去(leaf node是Separator Key一起過去; 非leaf node則只有其他key過去新節點), 並且添加該新node的pointer到parent node內, 以及被設定成parent node的第一個key.
上圖, 要新增11到[10,13,15]這leaf node, 但這node已經達到N=3的限制,[10,13,15]這node取後面一半[13,15]去新的節點, 13這key被稱為```Separator Key```;
我們把13給promote到parent node的第一個key.
如此13被promote上去parent, 而parent node也滿了,
則就繼續分裂, 也可能傳播到root node上.
當root node被split, 則會導致樹的高度+1


http://www.cburch.com/cs/340/reading/btree/index.html
## BTree的節點合併
在進行delete node時, 一樣要先找到目標的leaf node, 被定位後就能進行刪除操作.
但當被進行刪除操作的node與sibling node兩個節點的key相加還是少於threshold, 則就需要進行Merge, 這種情況稱為Underflow.

BTree一樣有兩種情況要merge, Node一樣最多N個Key, internal node一樣最多N+1個pointer
1. leaf node, 相鄰兩個node的Key個數<=N
2. internal node, 相鄰兩個internal node的pointer個數<=N+1

> example 1:
目標刪除key 16
刪除之後, 與相鄰節點的key總和為3個 <= N, 進行merge操作
> - 把右邊節點的key複製到左邊節點
> - 從parent刪除原本指向右節點的pointer
> - 刪除右節點

> example 2:
> 
目標刪除key 10
刪除之後, 與相鄰節點的Pointer總和為3個 <= N+1, 進行merge操作
> - 把右邊節點的poiter與pointer複製到左邊節點
> - 從parent把原本指向右節點的key給降級到左節點內, 刪除原本指向右節點的pointer與key
> - 刪除右節點

# 小結
BTree很適合硬碟專用存取的結構, 相對於BST因為低fanout, 會引發大量數據搬遷與指針更新的操作,
所以其實不適合用在硬碟存儲上.
BTree則是透過增加fanout數, 來減少balacing發生的頻率.

## 補充, btree高度計算