B+樹節點與插入操作

設計B+樹節點

在設計B+樹的數據結構時，我們首先需要定義節點的格式，這將幫助我們理解如何進行插入、刪除以及分裂和合并操作。以下是對B+樹節點設計的詳細說明。

節點格式概述

所有的B+樹節點大小相同，這是為了后續使用自由列表機制。即使當前階段不處理磁盤數據，一個具體的節點格式仍然是必要的，因為它決定了節點的字節大小以及何時應該分裂一個節點。

節點組成部分

1. 固定大小的頭部（Header）：

   • 包含節點類型（葉節點或內部節點）。
   • 包含鍵的數量（nkeys）。

2. 子節點指針列表（僅內部節點有）：

   • 每個內部節點包含指向其子節點的指針列表。

3. KV對列表：

   • 包含鍵值對（key-value pairs），對于葉節點是實際數據，對于內部節點則是用于導航的鍵。

4. 到KV對的偏移量列表：

   • 用于支持KV對的二分查找，通過記錄每個KV對在節點中的位置來加速查找過程。

節點格式示例：

type	nkeys	pointers	offsets	key-values	unused
2B	2B	nkeys * 8B	nkeys * 2B	…	…

每個KV對的格式如下：

klen	vlen	key	val
2B	2B	…	…

簡化與限制

為了專注于學習基礎知識，而不是創建一個真實的數據庫系統，這里做出了一些簡化：

• 葉節點和內部節點使用相同的格式，盡管這會導致一些空間浪費（例如，葉節點不需要指針，內部節點不需要存儲值）。
• 內部節點的分支數為𝑛時，包含𝑛個鍵，每個鍵都是從相應子樹的最小鍵復制而來。實際上，對于𝑛個分支只需要𝑛?1個鍵。額外的鍵主要是為了簡化可視化。
• 設置節點大小為4KB，這是典型的操作系統頁面大小。然而，鍵和值可能非常大，超過單個節點的容量。解決這個問題的方法包括外部存儲大型KVs或使節點大小可變，但這些不是基礎問題的核心部分，因此我們將通過限制KV大小來避免這些問題，確保它們總是能適應于一個節點內。

這種設計使得我們可以集中精力于理解和實現B+樹的基本操作，如插入、刪除、分裂和合并，同時保持代碼的簡潔性和易理解性。

const HEADER = 4
const BTREE_PAGE_SIZE = 4096
const BTREE_MAX_KEY_SIZE = 1000
const BTREE_MAX_VAL_SIZE = 3000
func init() {node1max := HEADER + 8 + 2 + 4 + BTREE_MAX_KEY_SIZE + BTREE_MAX_VAL_SIZEassert(node1max <= BTREE_PAGE_SIZE) // maximum KV
}

鍵大小限制

鍵大小的限制也確保了內部節點總是能夠容納至少2個鍵。這對于維持B+樹的結構完整性非常重要。

內存中的數據類型

在我們的代碼中，一個節點只是一個按這種格式解釋的字節塊。從內存移動數據到磁盤時，沒有序列化步驟會更簡單。

type BNode []byte // 可以直接寫入磁盤

解耦數據結構與IO

在設計B+樹時，無論是內存中的還是磁盤上的數據結構，都需要進行空間的分配和釋放。通過使用回調函數，我們可以將這些操作抽象出來，形成數據結構與其他數據庫組件之間的邊界。

回調機制的設計

以下是Go語言中定義的BTree結構示例，它展示了如何通過回調來管理磁盤頁面：

type BTree struct {// 指針（非零頁號）root uint64// 管理磁盤頁面的回調函數get  func(uint64) []byte // 解引用一個指針new  func([]byte) uint64 // 分配一個新的頁面（寫時復制）del  func(uint64)        // 釋放一個頁面
}

對于磁盤上的B+樹，數據庫文件是一個由頁號（指針）引用的頁面（節點）數組。我們將按照以下方式實現這些回調：

• get：從磁盤讀取一個頁面。
• new：分配并寫入一個新的頁面（采用寫時復制的方式）。
• del：釋放一個頁面。

這種方法允許我們以統一的方式處理內存和磁盤上的數據結構，同時保持代碼的清晰和模塊化。

為了操作B+樹節點的字節格式，我們需要定義一些輔助函數來解析和訪問節點中的數據。以下是基于節點格式的詳細實現。

---

節點格式回顧

因為Node的類型就是[]byte，我們可以定義一些輔助函數來解析和訪問節點中的數據。

type	nkeys	pointers	offsets	key-values	unused
2B	2B	nkeys * 8B	nkeys * 2B	…	…

每個鍵值對（key-value pair）的格式為：

klen	vlen	key	val
2B	2B	…	…

---

輔助函數的實現

我們將為節點定義以下輔助函數：

1. 解析頭部信息：獲取節點類型和鍵的數量。
2. 訪問指針列表：用于內部節點的子節點指針。
3. 訪問偏移量列表：用于快速定位鍵值對。
4. 解析鍵值對：從偏移量中提取鍵和值。

解析頭部信息

節點頭部包含兩部分：

• type（2字節）：節點類型（葉節點或內部節點）。
• nkeys（2字節）：鍵的數量。

const (BNODE_NODE = 1 // internal nodes without values BNODE_LEAF = 2 // leaf nodes with values
)
func (node BNode) btype() uint16 {return binary.LittleEndian.Uint16(node[0:2])
}
func (node BNode) nkeys() uint16 {return binary.LittleEndian.Uint16(node[2:4])
}func (node BNode) setHeader(btype uint16, nkeys uint16) {binary.LittleEndian.PutUint16(node[0:2], btype)binary.LittleEndian.PutUint16(node[2:4], nkeys)
}

子節點

// pointers
func (node BNode) getPtr(idx uint16) uint64 {//assert(idx < node.nkeys())pos := HEADER + 8*idxreturn binary.LittleEndian.Uint64(node[pos:])
}
func (node BNode) setPtr(idx uint16, val uint64) {
//assert(idx < node.nkeys())pos := HEADER + 8*idxbinary.LittleEndian.PutUint64(node[pos:], val)
}

---

解析節點中的鍵值對與偏移量

在B+樹的節點中，鍵值對（KV pairs）是緊密排列存儲的。為了高效地訪問第n個鍵值對，我們引入了偏移量列表，以實現O(1)的時間復雜度來定位鍵值對，并支持節點內的二分查找。

以下是相關代碼和解釋：

---

1. 偏移量列表

偏移量列表用于快速定位鍵值對的位置。每個偏移量表示相對于第一個鍵值對起點的字節位置（即鍵值對的結束位置）。通過偏移量列表，我們可以直接跳到指定的鍵值對，而無需逐一遍歷整個節點。

// 計算偏移量列表中第idx個偏移量的位置
func offsetPos(node BNode, idx uint16) uint16 {assert(1 <= idx && idx <= node.nkeys()) // 確保索引有效return HEADER + 8*node.nkeys() + 2*(idx-1)
}// 獲取第idx個偏移量
func (node BNode) getOffset(idx uint16) uint16 {if idx == 0 {return 0 // 第一個鍵值對的起始偏移量為0}return binary.LittleEndian.Uint16(node[offsetPos(node, idx):])
}// 設置第idx個偏移量
func (node BNode) setOffset(idx uint16, offset uint16) {pos := offsetPos(node, idx)binary.LittleEndian.PutUint16(node[pos:], offset)
}

---

2. 鍵值對的位置計算

kvPos函數返回第n個鍵值對相對于整個節點的字節偏移量。它結合了偏移量列表的信息，使得可以直接定位鍵值對。

// 返回第idx個鍵值對的位置
func (node BNode) kvPos(idx uint16) uint16 {assert(idx <= node.nkeys()) // 確保索引有效return HEADER + 8*node.nkeys() + 2*node.nkeys() + node.getOffset(idx)
}

---

3. 獲取鍵和值

通過kvPos函數，我們可以輕松提取鍵值對中的鍵和值。

// 獲取第idx個鍵
func (node BNode) getKey(idx uint16) []byte {assert(idx < node.nkeys()) // 確保索引有效pos := node.kvPos(idx)klen := binary.LittleEndian.Uint16(node[pos:]) // 鍵長度return node[pos+4 : pos+4+uint16(klen)]        // 跳過klen和vlen字段
}// 獲取第idx個值
func (node BNode) getVal(idx uint16) []byte {assert(idx < node.nkeys()) // 確保索引有效pos := node.kvPos(idx)klen := binary.LittleEndian.Uint16(node[pos:])       // 鍵長度vlen := binary.LittleEndian.Uint16(node[pos+2:])     // 值長度return node[pos+4+uint16(klen) : pos+4+uint16(klen)+uint16(vlen)]
}

---

4. 節點大小

nbytes函數通過訪問最后一個鍵值對的結束位置，可以方便地計算節點中已使用的字節數。

// 返回節點的大小（已使用字節數）
func (node BNode) nbytes() uint16 {return node.kvPos(node.nkeys())
}

---

5. 節點內查找操作

節點內的查找操作是B+樹的核心功能之一，既支持范圍查詢也支持點查詢。以下是一個基于線性掃描的實現，未來可以替換為二分查找以提高效率。

// 返回第一個滿足 kid[i] <= key 的子節點索引
func nodeLookupLE(node BNode, key []byte) uint16 {nkeys := node.nkeys()found := uint16(0)// 第一個鍵是從父節點復制來的，因此總是小于等于keyfor i := uint16(1); i < nkeys; i++ {cmp := bytes.Compare(node.getKey(i), key)if cmp <= 0 {found = i // 更新找到的索引}if cmp >= 0 {break // 找到大于等于key的鍵時停止}}return found
}

---

這種設計不僅提高了節點操作的效率，還為后續擴展（如二分查找和插入刪除操作）奠定了堅實的基礎。

更新 B+ 樹節點

在 B+ 樹中，更新節點的操作涉及插入鍵值對、復制節點（Copy-on-Write）、以及處理內部節點的鏈接更新。以下是詳細的設計和實現。

---

1. 插入到葉節點

插入鍵值對到葉節點的過程包括以下步驟：

1. 使用 nodeLookupLE 找到插入位置。
2. 創建一個新節點，并將舊節點的內容復制到新節點中，同時插入新的鍵值對。

// 向葉節點插入一個新的鍵值對
func leafInsert(new BNode, old BNode, idx uint16,key []byte, val []byte,
) {// 設置新節點的頭部信息（類型為葉節點，鍵的數量增加1）new.setHeader(BNODE_LEAF, old.nkeys()+1)// 復制舊節點中 [0, idx) 范圍內的鍵值對到新節點nodeAppendRange(new, old, 0, 0, idx)// 在新節點的 idx 位置插入新的鍵值對nodeAppendKV(new, idx, 0, key, val)// 復制舊節點中 [idx, nkeys) 范圍內的鍵值對到新節點nodeAppendRange(new, old, idx+1, idx, old.nkeys()-idx)
}

---

2. 節點復制函數

為了支持高效的節點復制操作，我們定義了兩個輔助函數：

• nodeAppendKV：將單個鍵值對插入到指定位置。
• nodeAppendRange：將多個鍵值對從舊節點復制到新節點。

2.1 插入單個鍵值對

// 將一個鍵值對插入到指定位置
func nodeAppendKV(new BNode, idx uint16, ptr uint64, key []byte, val []byte) {// 設置指針（僅內部節點需要）new.setPtr(idx, ptr)// 獲取當前鍵值對的位置pos := new.kvPos(idx)// 寫入鍵長度binary.LittleEndian.PutUint16(new[pos+0:], uint16(len(key)))// 寫入值長度binary.LittleEndian.PutUint16(new[pos+2:], uint16(len(val)))// 寫入鍵copy(new[pos+4:], key)// 寫入值copy(new[pos+4+uint16(len(key)):], val)// 更新下一個鍵的偏移量new.setOffset(idx+1, new.getOffset(idx)+4+uint16(len(key)+len(val)))
}

2.2 復制多個鍵值對

// 將多個鍵值對從舊節點復制到新節點
func nodeAppendRange(new BNode, old BNode,dstNew uint16, srcOld uint16, n uint16,
) {for i := uint16(0); i < n; i++ {srcIdx := srcOld + idstIdx := dstNew + i// 復制鍵值對key := old.getKey(srcIdx)val := old.getVal(srcIdx)nodeAppendKV(new, dstIdx, old.getPtr(srcIdx), key, val)}
}

---

3. 更新內部節點

對于內部節點，當子節點被分裂時，可能需要更新多個鏈接。我們使用 nodeReplaceKidN 函數來替換一個子節點鏈接為多個鏈接。

// 替換一個子節點鏈接為多個鏈接
func nodeReplaceKidN(tree *BTree, new BNode, old BNode, idx uint16,kids ...BNode,
) {inc := uint16(len(kids)) // 新增的子節點數量// 設置新節點的頭部信息（類型為內部節點，鍵的數量增加 inc-1）new.setHeader(BNODE_NODE, old.nkeys()+inc-1)// 復制舊節點中 [0, idx) 范圍內的鍵值對到新節點nodeAppendRange(new, old, 0, 0, idx)// 插入新的子節點鏈接for i, node := range kids {// 為每個子節點分配頁號，并插入其第一個鍵作為邊界鍵nodeAppendKV(new, idx+uint16(i), tree.new(node), node.getKey(0), nil)}// 復制舊節點中 [idx+1, nkeys) 范圍內的鍵值對到新節點nodeAppendRange(new, old, idx+inc, idx+1, old.nkeys()-(idx+1))
}

---

4. 關鍵點總結

1. Copy-on-Write：

   • 每次修改節點時，都會創建一個新節點并復制舊節點的內容。這種設計確保了數據的一致性和持久性。

2. 插入邏輯：

   • 葉節點的插入通過 leafInsert 實現，而內部節點的更新通過 nodeReplaceKidN 實現。
   • 在插入過程中，鍵值對的順序必須保持一致，因為偏移量列表依賴于前一個鍵值對的位置。

3. 回調機制：

   • tree.new 回調用于分配新的子節點頁號，這使得我們可以靈活地支持內存和磁盤上的存儲。

4. 擴展性：

   • 當前實現基于線性掃描，未來可以通過二分查找優化查找效率。
   • 支持多鏈接更新，方便處理子節點分裂的情況。

---

示例用法

以下是一個簡單的例子，展示如何向葉節點插入鍵值對：

func ExampleLeafInsert() {// 創建一個舊節點old := make(BNode, 4096)old.setHeader(BNODE_LEAF, 0)// 創建一個新節點new := make(BNode, 4096)// 插入鍵值對leafInsert(new, old, 0, []byte("key1"), []byte("value1"))// 驗證插入結果fmt.Printf("Key: %s, Value: %s\n", new.getKey(0), new.getVal(0))
}

分裂 B+ 樹節點

在 B+ 樹中，由于每個節點的大小受到頁面限制（BTREE_PAGE_SIZE），當一個節點變得過大時，我們需要將其分裂為多個節點。最壞情況下，一個超大的節點可能需要被分裂為 3 個節點。

以下是詳細的設計和實現。

---

1. 分裂邏輯概述

1.1 節點分裂的基本規則

• 如果節點的大小小于等于 BTREE_PAGE_SIZE，則無需分裂。
• 如果節點的大小超過 BTREE_PAGE_SIZE，我們首先嘗試將其分裂為兩個節點：
  • 左節點：包含前半部分數據。
  • 右節點：包含后半部分數據。
• 如果左節點仍然過大，則需要進一步分裂為三個節點：
  • 左左節點：包含左節點的前半部分數據。
  • 中間節點：包含左節點的后半部分數據。
  • 右節點：保持不變。

1.2 返回值

• 函數返回分裂后的節點數量（1、2 或 3）以及對應的節點數組。

---

2. 實現細節

2.1 nodeSplit2 函數

該函數將一個超大的節點分裂為兩個節點，確保右節點始終適合一個頁面。

// 將超大的節點分裂為兩個節點
func nodeSplit2(left BNode, right BNode, old BNode) {nkeys := old.nkeys()half := nkeys / 2// 復制前半部分到左節點left.setHeader(old.NodeType(), half)nodeAppendRange(left, old, 0, 0, half)// 復制后半部分到右節點right.setHeader(old.NodeType(), nkeys-half)nodeAppendRange(right, old, 0, half, nkeys-half)
}

---

2.2 nodeSplit3 函數

該函數處理節點的完整分裂邏輯，返回 1 至 3 個節點。

// 分裂一個過大的節點，結果是 1~3 個節點
func nodeSplit3(old BNode) (uint16, [3]BNode) {if old.nbytes() <= BTREE_PAGE_SIZE {// 如果節點大小符合限制，則無需分裂old = old[:BTREE_PAGE_SIZE]return 1, [3]BNode{old, nil, nil} // 返回單個節點}// 創建臨時節點left := BNode(make([]byte, 2*BTREE_PAGE_SIZE)) // 左節點可能需要再次分裂right := BNode(make([]byte, BTREE_PAGE_SIZE))// 第一次分裂：將舊節點分裂為左節點和右節點nodeSplit2(left, right, old)if left.nbytes() <= BTREE_PAGE_SIZE {// 如果左節點大小符合限制，則返回兩個節點left = left[:BTREE_PAGE_SIZE]return 2, [3]BNode{left, right, nil}}// 如果左節點仍然過大，則需要第二次分裂leftleft := BNode(make([]byte, BTREE_PAGE_SIZE))middle := BNode(make([]byte, BTREE_PAGE_SIZE))// 第二次分裂：將左節點分裂為左左節點和中間節點nodeSplit2(leftleft, middle, left)// 驗證分裂結果assert(leftleft.nbytes() <= BTREE_PAGE_SIZE)// 返回三個節點return 3, [3]BNode{leftleft, middle, right}
}

---

3. 關鍵點分析

1. 分裂條件：

   • 如果節點的大小小于等于 BTREE_PAGE_SIZE，則無需分裂。
   • 如果節點的大小超過限制，則需要進行一次或兩次分裂。

2. 分裂策略：

   • 每次分裂都將節點分為兩部分，確保右節點始終適合一個頁面。
   • 如果左節點仍然過大，則需要進一步分裂。

3. 臨時節點：

   • 分裂過程中創建的節點是臨時分配在內存中的。
   • 這些節點只有在調用 nodeReplaceKidN 時才會真正分配到磁盤上。

4. 邊界情況：

   • 確保左節點和右節點的大小始終符合限制。
   • 使用斷言（assert）驗證分裂結果的正確性。

---

這種分裂機制為構建高效的 B+ 樹奠定了基礎，同時也為后續優化（如動態調整頁面大小）提供了良好的起點。

B+ 樹插入操作

在 B+ 樹中，插入操作是核心功能之一。我們已經實現了以下三個節點操作：

1. leafInsert：更新葉節點。
2. nodeReplaceKidN：更新內部節點。
3. nodeSplit3：分裂超大的節點。

現在，我們將這些操作組合起來，實現完整的 B+ 樹插入邏輯。插入操作從根節點開始，通過鍵查找直到到達目標葉節點，然后執行插入操作。

---

1. 插入邏輯概述

1.1 插入流程

• 從根節點開始遞歸查找，找到目標葉節點。
• 如果找到的鍵已存在，則更新其值（leafUpdate）。
• 如果鍵不存在，則插入新鍵值對（leafInsert）。
• 如果節點過大，則進行分裂（nodeSplit3）。
• 更新父節點以反映子節點的變化（nodeReplaceKidN）。

1.2 遞歸處理

• 內部節點的插入是遞歸的，每次插入完成后返回更新后的節點。
• 如果返回的節點過大，則需要分裂，并更新父節點的鏈接。

---

2. 實現細節

2.1 treeInsert 函數

該函數是 B+ 樹插入的核心入口，負責處理遞歸插入和分裂邏輯。

// 插入一個鍵值對到節點中，結果可能需要分裂。
// 調用者負責釋放輸入節點并分配分裂后的結果節點。
func treeInsert(tree *BTree, node BNode, key []byte, val []byte) BNode {// 創建一個新的臨時節點，允許其大小超過一頁new := BNode{data: make([]byte, 2*BTREE_PAGE_SIZE)}// 查找插入位置idx := nodeLookupLE(node, key)// 根據節點類型執行不同的操作switch node.btype() {case BNODE_LEAF:// 葉節點if bytes.Equal(key, node.getKey(idx)) {// 鍵已存在，更新其值leafUpdate(new, node, idx, key, val)} else {// 插入新鍵值對leafInsert(new, node, idx+1, key, val)}case BNODE_NODE:// 內部節點nodeInsert(tree, new, node, idx, key, val)default:panic("bad node!")}return new
}

---

2.2 leafUpdate 函數

leafUpdate 類似于 leafInsert，但它用于更新已存在的鍵值對，而不是插入重復的鍵。

// 更新葉節點中的現有鍵值對
func leafUpdate(new BNode, old BNode, idx uint16,key []byte, val []byte,
) {// 設置新節點的頭部信息new.setHeader(BNODE_LEAF, old.nkeys())// 復制舊節點的內容到新節點nodeAppendRange(new, old, 0, 0, old.nkeys())// 更新指定位置的鍵值對pos := new.kvPos(idx)binary.LittleEndian.PutUint16(new[pos+2:], uint16(len(val))) // 更新值長度copy(new[pos+4+uint16(len(key)):], val)                      // 更新值內容
}

---

2.3 nodeInsert 函數

對于內部節點，插入操作是遞歸的。插入完成后，需要檢查子節點是否過大，并進行分裂。

// 向內部節點插入鍵值對
func nodeInsert(tree *BTree, new BNode, node BNode, idx uint16,key []byte, val []byte,
) {// 獲取子節點的指針kptr := node.getPtr(idx)// 遞歸插入到子節點knode := treeInsert(tree, tree.get(kptr), key, val)// 分裂子節點nsplit, split := nodeSplit3(knode)// 釋放舊的子節點tree.del(kptr)// 更新父節點的鏈接nodeReplaceKidN(tree, new, node, idx, split[:nsplit]...)
}

---

3. 關鍵點分析

1. 遞歸與分裂：

   • 插入操作是遞歸的，從根節點開始，直到找到目標葉節點。
   • 每次插入完成后，如果節點過大，則需要分裂，并更新父節點的鏈接。

2. 內存管理：

   • 插入過程中創建的臨時節點需要由調用者負責釋放。
   • 使用回調函數（如 tree.new 和 tree.del）管理頁面的分配和釋放。

3. 分裂策略：

   • 使用 nodeSplit3 處理節點分裂，確保分裂后的節點始終符合頁面大小限制。
   • 分裂后的節點數量可能是 1、2 或 3。

4. 邊界情況：

   • 如果鍵已存在，則直接更新其值。
   • 如果插入導致根節點分裂，則需要創建新的根節點。

---

4. 示例用法

以下是一個簡單的例子，展示如何向 B+ 樹中插入鍵值對：

func ExampleTreeInsert() {// 初始化 B+ 樹tree := &BTree{root: 1, // 假設根節點頁號為 1get: func(pageNum uint64) []byte {// 模擬從磁盤讀取節點return loadFromDisk(pageNum)},new: func(data []byte) uint64 {// 模擬分配新頁面return allocatePage(data)},del: func(pageNum uint64) {// 模擬釋放頁面deallocatePage(pageNum)},}// 插入鍵值對key := []byte("example_key")value := []byte("example_value")// 獲取根節點rootNode := tree.get(tree.root)// 執行插入操作updatedRoot := treeInsert(tree, rootNode, key, value)// 更新根節點tree.root = tree.new(updatedRoot)
}

---

5. 總結

通過上述設計和實現，我們能夠高效地完成 B+ 樹的插入操作。關鍵點包括：

• 遞歸插入：從根節點開始，遞歸查找目標葉節點。
• 分裂機制：使用 nodeSplit3 確保節點大小始終符合限制。
• 內存管理：通過回調函數管理頁面的分配和釋放。
• 靈活性：支持動態調整樹的結構，適應不同大小的數據。

這種插入機制為構建高效的 B+ 樹奠定了基礎，同時也為后續優化（如批量插入、并發控制）提供了良好的起點。

代碼倉庫地址：database-go