這篇文章以數據庫存儲的數據結構來引出本文的重點B樹,以及後面還有另一種數據結構B+樹.

試想, 如果你想持久化大量的數據在硬盤上, 同時還希望能高效的查詢和修改他們, 你會怎麼做, 使用哪種數據結構.

數組和鏈表, 他們的缺點很明顯, 我們尋找數據需要遍歷整個數據結構, 試想一下你的數據庫中有50PB的數據, 這個開銷是我們無法接受的.

哈希表, 通過給定的數據通過Hash函數生成對應的索引, 能非常高效的找到對應的數據. 但是, 哈希表不能用於範圍查詢.

二叉樹, 一種使用二分法作為查詢算法的數據結構, 在內存中, 二叉樹的效率確實非常高, 但是如果是在硬盤上, 每次讀取節點, 都需要進行一次IO, 隨著數據量的增大, 深度逐漸加深, 二叉樹的效率就會大大降低.

B Tree

B樹存在一些和二叉樹不一樣的地方: 二叉樹每個節點只保存一份數據以及兩個指針, B樹在每個節點都可以保留一樣數量的數據和指針, 指針的數量為數據的數量+1.

在B樹中還有存在一個概念, 階數, 它決定了該B樹每個節點應該有多少數據以及指針.

Rules

  • 排序方式：所有節點關鍵字是按遞增次序排列，並遵循左小右大原則；例如一個節點能存放3份數據, 該數據需要從左到右增序存放, 1, 2, 3.

  • 子節點數：非葉節點的子節點數>1，且<=M ，且M>=2，空樹除外(注：M階代表一個樹節點最多有多少個查找路徑，M=M路,當M=2則是2叉樹,M=3則是3叉)；

  • 關鍵字數：子節點的關鍵字數量大於等於ceil(m/2)-1個且小於等於M-1個(注：ceil()是個朝正無窮方向取整的函數 如ceil(1.1)結果為2);

  • 所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針只不過其指針地址都為null對應下圖最後一層節點的空格子;

Find

我們用一個圖和一個實際的例子來理解B樹(這裡為了理解方便我就直接用實際字母的大小來排列C>B>A):

BT

如上圖我要從上圖中找到E字母，查找流程如下:

  1. 獲取根節點的關鍵字進行比較，當前根節點關鍵字為M，E<M(26個字母順序)，所以往找到指向左邊的子節點(二分法規則，左小右大，左邊放小於當前節點值的子節點、右邊放大於當前節點值的子節點)；

  2. 拿到關鍵字D和G，D<E<G 所以直接找到D和G中間的節點；

  3. 拿到E和F，因為E=E 所以直接返回關鍵字和指針信息(如果樹結構裡面沒有包含所要查找的節點則返回null).

Insert

下次更新.