徹底搞定篇–B+Tree（1）
- 2019 年 10 月 5 日
- 筆記
對話
老王：最近怎麼沒精打採的呢？
小王：最近面試卡住了，B+ tree 沒回答上來
老王：不對呀，你不早就學過嗎，經典教程都寫這呢？
小王：別提啦，當時腦中一片空白。
當時情況是這樣的！
大王：談談你對B+ tree理解？
小王：這個我知道，就是數據全部存儲到葉子節點上，在同一層次 ！
大王；然後呢。。。。
小王：支支吾吾 說不上來了。
大王：還有沒有補充的
小王：查詢效率很高。
大王：怎麼查詢的？
小王：。。。。。。。
大王：過，就到這裡。
老王：我來講一講
（老王） 我演示一下如何查找
- 查找元素6
- 查找元素12
- 查找元素17 （慢速）
（小王）我知道如何查找了
查詢tree_search (k, root) 邏輯
- 如果root為null，直接返回查詢失敗。
- 如果是root是葉子節點，if k=ki，返回查找成功，不然就失敗。
- root 如果是非葉子節點。 循環遍歷 如果 k <key1
從對應子樹 繼續尋找tree_search (k, root.1.child) 遞歸遍歷
- 循環遍歷結束。k 大於任何一個key。指針多一個 tree_search (k, root.last.child) 偽程式碼
Function: tree_search (k, node) if node is a leaf then return node; switch k do case k ≤ k_0 return tree_search(k, p_0); case k_i < k ≤ k_{i+1} return tree_search(k, p_{i+1}); case k_d < k return tree_search(k, p_{d});
小王：
我有一個疑問，查詢元素12時候，明明中間元素 已經存在，為什麼還要繼續查詢走到葉子節點才算結束， 這不是浪費時間嗎？
老王：
觀察很仔細呀，漫畫演算法：什麼是 B+ 樹。
程式設計師小灰已經給出解釋了，你不是看過一次，怎麼忘記了！
小王：
我確實看過，不過對裡面一句話根本不明白
有K個元素，K個指針 ，一個節點對應一個指針呀, 這個不對呀，2個元素會拆分3個指針呢？
（老王） 先別急著問為什麼，我演示一下插入操作
在葉子節點 (1 2 3) 上插入新元素 4 ，B tree 結果是：
在葉子節點 (1 2 3) 上插入新元素 4 ，B+ tree 結果是：
順序插入元素：1 2 3 4 5 6 7 9 10 11 創建 4 階 B+ tree 完整演示（慢速10倍）
（小王）我知道如何插入了
插入關鍵字k的步驟
- 選擇到葉子節點，然後插入對應位置
- 對葉子節點做平衡檢查，如果超過上界，選擇中間元素+1位置這個key進行拆分到paernt節點上去。
- 繼續對父節點做做平衡檢查。如果超過上界，選擇中間元素+1位置這個key進行拆分到paernt節點上去
- 重複步驟 3
（老王）請看下面刪除演示
刪除元素 5
刪除元素 7
7.gif
（小王）這個有點複雜，需要藉助相鄰的元素，這個操作我描述不出來
基本分為三個步驟
- 從葉子節點查詢到該元素，然後刪除
- 判斷是是否低於最低數量，從該節點借一個記錄代替自己。如果沒有從鄰居借去一個代替自己
- 重複步驟 2
但是漏洞很多，無法具體描述。開始支支吾吾了
(老王) 你說對，這個情況比較複雜。未完待續
最後，小王偷偷寫下這麼幾句話
B+ tree 是一個 M 階平衡搜索樹 （Balanced multiway search trees）
- 為了維持平衡，每個非葉子節點中子樹個數上下界：M/2<=x <<M。也就是說 每個結點最多有m-1個關鍵字
- 每次對葉子節點 中key的 插入，刪除等操作會引起關鍵字超過上下界，因此需要繼續進行拆分或者合併操作。
- 因為全部資訊都存儲到葉子節點，這就為什麼每次查詢，插入，刪除等操從找到葉子節點開始。
哈哈哈
你一已經猜到 一個4階B+tree，一個節點最多允許 3個key，4個子樹指針。
因為B+ tree 結構是遞歸的，我只專心看最小子問題，就是一個節點組成
typedef struct BTNode{ int keynum; /// 結點中關鍵字的個數，ceil(ORDER/2)-1<= keynum <= ORDER-1 KeyType key[ORDER-1]; /// 關鍵字向量為key[0..keynum - 1] struct BTNode* child[ORDER]; /// 孩子指針向量為child[0..keynum] char isLeaf; /// 是否是葉子節點的標誌 }BTNode;
數據結構和演算法結構化
FQA
- 一個M階的B+tree，M是什麼意思，是節點個數，還是指針個數？目前我定義來看是孩子的最大個數?
- 每個節點 n個key和m個指針 ，n和m一定相等嗎？不一定
參考
B+ treeFrom Wikipedia
MySQL索引背後的數據結構及演算法原理
漫畫演算法：什麼是 B+ 樹
演算法導論 18章
