B+树删除和测试

B+树删除和测试

5.1 高级接口：B+ 树作为键值存储

在本章中，我们将实现 B+ 树的高级接口，使其能够作为键值存储（Key-Value Store）使用。这些接口包括插入和删除操作，并处理根节点的维护。

---

1. 插入接口

1.1 Insert 函数

Insert 函数用于插入新键或更新现有键。以下是其实现细节：

// 插入一个新键或更新现有键
func (tree *BTree) Insert(key []byte, val []byte) {if tree.root == 0 {// 如果树为空，则创建第一个根节点root := BNode(make([]byte, BTREE_PAGE_SIZE))root.setHeader(BNODE_LEAF, 2)// 插入一个哨兵值（空键），确保树覆盖整个键空间nodeAppendKV(root, 0, 0, nil, nil)// 插入实际的键值对nodeAppendKV(root, 1, 0, key, val)// 分配页号并设置为根节点tree.root = tree.new(root)return}// 插入键值对到当前树node := treeInsert(tree, tree.get(tree.root), key, val)// 检查是否需要分裂根节点nsplit, split := nodeSplit3(node)tree.del(tree.root) // 释放旧的根节点if nsplit > 1 {// 如果根节点被分裂，则创建一个新的根节点root := BNode(make([]byte, BTREE_PAGE_SIZE))root.setHeader(BNODE_NODE, nsplit)for i, knode := range split[:nsplit] {ptr, key := tree.new(knode), knode.getKey(0)nodeAppendKV(root, uint16(i), ptr, key, nil)}// 更新根节点tree.root = tree.new(root)} else {// 如果根节点未分裂，则直接更新根节点tree.root = tree.new(split[0])}
}

1.2 关键点分析

1. 哨兵值：

   • 在创建第一个根节点时，我们插入了一个空键（哨兵值）。这是为了确保树覆盖整个键空间。
   • 哨兵值是最小的键，因此 nodeLookupLE 函数始终能找到一个位置，避免了边界情况。

2. 根节点分裂：

   • 如果插入导致根节点过大，则需要分裂根节点。
   • 分裂后，创建一个新的内部节点作为新的根节点。

3. 内存管理：

   • 使用回调函数（tree.new 和 tree.del）管理页面的分配和释放。

---

2. 删除接口

2.1 Delete 函数

Delete 函数用于删除指定的键，并返回该键是否存在。

// 删除一个键，并返回是否删除成功
func (tree *BTree) Delete(key []byte) bool {if tree.root == 0 {// 如果树为空，则直接返回 falsereturn false}// 查找并删除键node := tree.get(tree.root)idx := nodeLookupLE(node, key)if !bytes.Equal(node.getKey(idx), key) {// 如果键不存在，则返回 falsereturn false}// 执行删除操作new := leafDelete(node, idx)// 如果节点变为空，则需要合并或调整树结构if new.nkeys() == 1 && tree.root != tree.new(new) {// 如果只剩下一个哨兵值，则清空树tree.del(tree.root)tree.root = 0return true}// 更新根节点tree.root = tree.new(new)return true
}

2.2 删除叶节点中的键

// 从叶节点中删除指定索引的键值对
func leafDelete(old BNode, idx uint16) BNode {// 创建一个新的节点new := BNode(make([]byte, BTREE_PAGE_SIZE))new.setHeader(BNODE_LEAF, old.nkeys()-1)// 复制 [0, idx) 范围内的键值对nodeAppendRange(new, old, 0, 0, idx)// 复制 [idx+1, nkeys) 范围内的键值对nodeAppendRange(new, old, idx, idx+1, old.nkeys()-idx-1)return new
}

2.3 关键点分析

1. 删除后的调整：

   • 如果删除导致节点变为空，则需要合并或调整树结构。
   • 如果只剩下一个哨兵值，则清空树。

2. 边界情况：

   • 如果键不存在，则直接返回 false。
   • 如果树为空，则无需执行任何操作。

---

3. 哨兵值的作用

哨兵值是一个技巧，用于简化查找逻辑。以下是其作用的详细说明：

1. 覆盖整个键空间：

   • 哨兵值是最小的键，确保树始终覆盖整个键空间。
   • 即使插入的键小于当前树中的所有键，nodeLookupLE 函数仍然能找到一个位置。

2. 避免边界情况：

   • 如果没有哨兵值，当查找的键小于树中的最小键时，nodeLookupLE 函数可能会失败。
   • 哨兵值的存在使得查找逻辑更加健壮。

---

4. 示例用法

以下是一个简单的例子，展示如何使用 B+ 树的高级接口：

func ExampleBTreeUsage() {// 初始化 B+ 树tree := &BTree{get: func(pageNum uint64) []byte {// 模拟从磁盘读取节点return loadFromDisk(pageNum)},new: func(data []byte) uint64 {// 模拟分配新页面return allocatePage(data)},del: func(pageNum uint64) {// 模拟释放页面deallocatePage(pageNum)},}// 插入键值对tree.Insert([]byte("key1"), []byte("value1"))tree.Insert([]byte("key2"), []byte("value2"))// 删除键success := tree.Delete([]byte("key1"))fmt.Printf("Deleted key1: %v\n", success)// 尝试删除不存在的键success = tree.Delete([]byte("key3"))fmt.Printf("Deleted key3: %v\n", success)
}

---

5.2 合并节点

在 B+ 树中，删除操作可能导致某些节点变得几乎为空。为了优化存储空间，我们可以通过合并相邻节点来减少节点数量。以下是实现合并逻辑的详细设计和代码。

---

1. 合并条件

在删除键值对后，需要检查是否满足合并条件。以下是一些关键点：

1. 合并阈值：

   • 如果一个节点的大小小于 BTREE_PAGE_SIZE / 4（即页面大小的四分之一），则认为该节点可以被合并。
   • 这是一个软限制，用于尽早触发合并操作，避免树中存在大量几乎空的节点。

2. 选择兄弟节点：

   • 如果目标节点有左兄弟节点或右兄弟节点，且合并后的节点大小不超过 BTREE_PAGE_SIZE，则可以选择合并。

3. 优先级：

   • 通常优先选择左兄弟节点进行合并（如果可用）。
   • 如果左兄弟节点不可用，则尝试与右兄弟节点合并。

---

2. 实现细节

2.1 shouldMerge 函数

该函数用于判断是否需要合并，并返回应该合并的兄弟节点（左或右）。

// 判断更新后的子节点是否应与其兄弟节点合并
func shouldMerge(tree *BTree, node BNode,idx uint16, updated BNode,
) (int, BNode) {// 如果更新后的节点大小大于阈值，则无需合并if updated.nbytes() > BTREE_PAGE_SIZE/4 {return 0, BNode{}}// 检查左兄弟节点if idx > 0 {sibling := BNode(tree.get(node.getPtr(idx - 1)))merged := sibling.nbytes() + updated.nbytes() - HEADERif merged <= BTREE_PAGE_SIZE {return -1, sibling // 左兄弟节点}}// 检查右兄弟节点if idx+1 < node.nkeys() {sibling := BNode(tree.get(node.getPtr(idx + 1)))merged := sibling.nbytes() + updated.nbytes() - HEADERif merged <= BTREE_PAGE_SIZE {return +1, sibling // 右兄弟节点}}// 不满足合并条件return 0, BNode{}
}

---

2.2 leafDelete 函数

从叶节点中删除指定索引的键值对。

// 从叶节点中删除指定索引的键值对
func leafDelete(new BNode, old BNode, idx uint16) {// 设置新节点的头部信息new.setHeader(BNODE_LEAF, old.nkeys()-1)// 复制 [0, idx) 范围内的键值对nodeAppendRange(new, old, 0, 0, idx)// 复制 [idx+1, nkeys) 范围内的键值对nodeAppendRange(new, old, idx, idx+1, old.nkeys()-idx-1)
}

---

2.3 nodeMerge 函数

将两个节点合并为一个节点。

// 将两个节点合并为一个节点
func nodeMerge(new BNode, left BNode, right BNode) {// 设置新节点的头部信息new.setHeader(left.NodeType(), left.nkeys()+right.nkeys())// 复制左节点的内容nodeAppendRange(new, left, 0, 0, left.nkeys())// 复制右节点的内容nodeAppendRange(new, right, left.nkeys(), 0, right.nkeys())
}

---

2.4 nodeReplace2Kid 函数

将两个相邻的链接替换为一个链接。

// 将两个相邻链接替换为一个链接
func nodeReplace2Kid(new BNode, old BNode, idx uint16, ptr uint64, key []byte,
) {// 设置新节点的头部信息new.setHeader(old.NodeType(), old.nkeys()-1)// 复制 [0, idx) 范围内的键值对nodeAppendRange(new, old, 0, 0, idx)// 插入新的键值对nodeAppendKV(new, idx, ptr, key, nil)// 复制 [idx+2, nkeys) 范围内的键值对nodeAppendRange(new, old, idx+1, idx+2, old.nkeys()-idx-2)
}

---

3. 合并逻辑的应用

在删除操作中，当检测到某个节点满足合并条件时，执行以下步骤：

1. 选择兄弟节点：

   • 使用 shouldMerge 函数判断是否需要合并以及选择哪个兄弟节点。

2. 执行合并：

   • 使用 nodeMerge 函数将目标节点与其兄弟节点合并。

3. 更新父节点：

   • 使用 nodeReplace2Kid 函数更新父节点中的链接。

---

4. 示例用法

以下是一个简单的例子，展示如何在删除操作中应用合并逻辑：

func ExampleNodeMerge() {// 初始化 B+ 树tree := &BTree{get: func(pageNum uint64) []byte {// 模拟从磁盘读取节点return loadFromDisk(pageNum)},new: func(data []byte) uint64 {// 模拟分配新页面return allocatePage(data)},del: func(pageNum uint64) {// 模拟释放页面deallocatePage(pageNum)},}// 删除键值对node := tree.get(tree.root)idx := nodeLookupLE(node, []byte("key1"))// 执行删除操作updated := leafDelete(BNode{}, node, idx)// 检查是否需要合并direction, sibling := shouldMerge(tree, node, idx, updated)if direction != 0 {merged := BNode(make([]byte, BTREE_PAGE_SIZE))if direction == -1 {// 合并左兄弟节点nodeMerge(merged, sibling, updated)} else {// 合并右兄弟节点nodeMerge(merged, updated, sibling)}// 更新父节点nodeReplace2Kid(BNode{}, node, idx, tree.new(merged), merged.getKey(0))}fmt.Println("Node merge completed.")
}

---

5. 总结

通过实现合并逻辑，我们可以优化 B+ 树的存储空间利用率。关键点包括：

1. 合并条件：

   • 使用 BTREE_PAGE_SIZE / 4 作为软限制，尽早触发合并操作。

2. 合并操作：

   • 使用 nodeMerge 和 nodeReplace2Kid 函数完成节点合并和父节点更新。

3. 性能优化：

   • 避免树中存在大量几乎空的节点，提高查询和插入效率。

这种设计使得 B+ 树能够动态调整结构，适应频繁的插入和删除操作，同时保持高效的存储和查询性能。

5.3 B+ 树删除操作

B+ 树的删除操作与插入操作类似，但核心区别在于：插入可能会导致节点分裂，而删除可能会导致节点合并。以下是完整的删除逻辑实现。

---

1. 删除逻辑概述

1.1 删除流程

1. 递归查找：

   • 从根节点开始，递归查找目标键所在的叶节点。
   • 如果找到目标键，则执行删除操作。

2. 处理删除后的节点：

   • 如果删除后节点变为空或过小（小于 BTREE_PAGE_SIZE / 4），则检查是否需要与其兄弟节点合并。
   • 如果没有兄弟节点可供合并，则将空节点传播到父节点。

3. 更新父节点：

   • 如果发生合并，则更新父节点以反映子节点的变化。

4. 边界情况：

   • 如果树中只剩下一个空的根节点，则清空整个树。

---

2. 实现细节

2.1 treeDelete 函数

该函数是 B+ 树删除的核心入口，负责递归查找和删除目标键。

// 从树中删除一个键
func treeDelete(tree *BTree, node BNode, key []byte) BNode {// 创建一个新的临时节点new := BNode(make([]byte, BTREE_PAGE_SIZE))// 查找目标键的位置idx := nodeLookupLE(node, key)// 根据节点类型执行不同的操作switch node.btype() {case BNODE_LEAF:// 叶节点if !bytes.Equal(key, node.getKey(idx)) {return BNode{} // 键不存在}// 删除键值对leafDelete(new, node, idx)case BNODE_NODE:// 内部节点nodeDelete(tree, new, idx, key)default:panic("bad node!")}return new
}

---

2.2 nodeDelete 函数

对于内部节点，删除操作是递归的。删除完成后，需要检查是否需要合并子节点。

// 从内部节点删除一个键
func nodeDelete(tree *BTree, node BNode, idx uint16, key []byte) BNode {// 获取子节点的指针kptr := node.getPtr(idx)// 递归删除子节点中的键updated := treeDelete(tree, tree.get(kptr), key)if len(updated) == 0 {return BNode{} // 键未找到}// 释放旧的子节点tree.del(kptr)// 创建一个新的临时节点new := BNode(make([]byte, BTREE_PAGE_SIZE))// 检查是否需要合并mergeDir, sibling := shouldMerge(tree, node, idx, updated)switch {case mergeDir < 0: // 合并左兄弟节点merged := BNode(make([]byte, BTREE_PAGE_SIZE))nodeMerge(merged, sibling, updated)tree.del(node.getPtr(idx - 1))nodeReplace2Kid(new, node, idx-1, tree.new(merged), merged.getKey(0))case mergeDir > 0: // 合并右兄弟节点merged := BNode(make([]byte, BTREE_PAGE_SIZE))nodeMerge(merged, updated, sibling)tree.del(node.getPtr(idx + 1))nodeReplace2Kid(new, node, idx, tree.new(merged), merged.getKey(0))case mergeDir == 0 && updated.nkeys() == 0:// 子节点为空且没有兄弟节点assert(node.nkeys() == 1 && idx == 0) // 父节点只有一个子节点new.setHeader(BNODE_NODE, 0)          // 父节点也变为空case mergeDir == 0 && updated.nkeys() > 0:// 不需要合并，直接更新父节点nodeReplaceKidN(tree, new, node, idx, updated)}return new
}

---

2.3 关键点分析

1. 递归删除：

   • 删除操作从根节点开始，递归查找目标叶节点。
   • 如果目标键存在于叶节点中，则直接删除。

2. 合并条件：

   • 使用 shouldMerge 函数判断是否需要合并以及选择哪个兄弟节点。
   • 如果合并后的节点大小不超过 BTREE_PAGE_SIZE，则执行合并。

3. 空节点传播：

   • 如果一个节点变为空且没有兄弟节点，则将其传播到父节点。
   • 在极端情况下，如果根节点变为空，则清空整个树。

4. 边界情况：

   • 如果树中只剩下一个空的根节点，则清空树。

---

3. 示例用法

以下是一个简单的例子，展示如何使用 B+ 树的删除接口：

func ExampleTreeDelete() {// 初始化 B+ 树tree := &BTree{get: 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")node := tree.get(tree.root)// 执行删除操作updatedRoot := treeDelete(tree, node, key)// 更新根节点if len(updatedRoot) == 0 {fmt.Println("Key not found.")} else {tree.root = tree.new(updatedRoot)fmt.Println("Key deleted successfully.")}
}

---

4. 总结

通过上述设计和实现，我们完成了 B+ 树的删除操作。关键点包括：

1. 递归删除：

   • 从根节点开始递归查找目标键，直到找到目标叶节点。

2. 合并机制：

   • 使用 nodeMerge 和 nodeReplace2Kid 函数完成节点合并和父节点更新。

3. 空节点处理：

   • 如果一个节点变为空且没有兄弟节点，则将其传播到父节点，最终可能导致根节点变为空。

4. 性能优化：

   • 通过尽早触发合并操作（使用 BTREE_PAGE_SIZE / 4 作为软限制），避免树中存在大量几乎空的节点。

这种设计使得 B+ 树能够高效地支持动态数据集的删除操作，同时保持高效的存储和查询性能。

5.4 测试 B+ 树

为了测试 B+ 树的正确性和性能，我们需要模拟页面管理回调（get、new 和 del），并验证树结构和数据的一致性。以下是详细的测试设计。

---

1. 模拟内存中的页面管理

为了测试 B+ 树的功能，我们可以在内存中模拟页面管理系统。以下是实现的关键部分：

1.1 定义测试上下文 C

type C struct {tree  BTree                // B+ 树实例ref   map[string]string    // 参考数据（用于验证）pages map[uint64]BNode     // 内存中的页面
}

• tree：B+ 树实例，使用自定义的页面管理回调。
• ref：参考数据，用一个 map[string]string 来存储键值对，用于验证 B+ 树的数据一致性。
• pages：内存中的页面，用于验证指针的有效性和读取页面内容。

1.2 初始化测试上下文

func newC() *C {pages := map[uint64]BNode{}return &C{tree: BTree{get: func(ptr uint64) []byte {node, ok := pages[ptr]assert(ok) // 确保页面存在return node},new: func(node []byte) uint64 {assert(BNode(node).nbytes() <= BTREE_PAGE_SIZE) // 确保节点大小符合限制ptr := uint64(uintptr(unsafe.Pointer(&node[0]))) // 使用内存地址作为页面指针assert(pages[ptr] == nil) // 确保页面尚未分配pages[ptr] = nodereturn ptr},del: func(ptr uint64) {assert(pages[ptr] != nil) // 确保页面存在delete(pages, ptr)},},ref:   map[string]string{},pages: pages,}
}

• get：从内存中读取页面，确保页面指针有效。
• new：分配新页面，并将其存储在 pages 中。
• del：释放页面，确保页面指针有效后删除。

---

2. 测试逻辑

2.1 添加键值对

func (c *C) add(key string, val string) {c.tree.Insert([]byte(key), []byte(val)) // 插入到 B+ 树中c.ref[key] = val                       // 更新参考数据
}

• 功能：向 B+ 树插入键值对，同时更新参考数据。

2.2 删除键值对

func (c *C) remove(key string) {success := c.tree.Delete([]byte(key)) // 从 B+ 树中删除键if success {delete(c.ref, key) // 更新参考数据}
}

• 功能：从 B+ 树删除键值对，同时更新参考数据。

2.3 验证树结构

验证 B+ 树的结构是否有效：

1. 键排序：

   • 叶节点中的键必须按升序排列。
   • 内部节点中的分隔键也必须按升序排列。

2. 节点大小限制：

   • 每个节点的大小不能超过 BTREE_PAGE_SIZE。

func (c *C) validateStructure(node BNode) {switch node.btype() {case BNODE_LEAF:// 验证叶节点for i := uint16(1); i < node.nkeys(); i++ {assert(bytes.Compare(node.getKey(i-1), node.getKey(i)) < 0) // 键必须递增}case BNODE_NODE:// 验证内部节点for i := uint16(1); i < node.nkeys(); i++ {assert(bytes.Compare(node.getKey(i-1), node.getKey(i)) < 0) // 分隔键必须递增}// 递归验证子节点for i := uint16(0); i < node.nkeys(); i++ {child := c.tree.get(node.getPtr(i))c.validateStructure(child)}default:panic("bad node!")}assert(node.nbytes() <= BTREE_PAGE_SIZE) // 节点大小不能超过限制
}

2.4 验证数据一致性

验证 B+ 树中的数据是否与参考数据一致：

func (c *C) validateData() {for key, val := range c.ref {result := c.tree.Lookup([]byte(key)) // 查找键assert(result != nil && bytes.Equal(result, []byte(val))) // 数据必须匹配}
}

---

3. 测试用例

以下是一些典型的测试场景：

3.1 基本插入和查找

func TestBasicInsertAndLookup(t *testing.T) {c := newC()// 插入键值对c.add("key1", "value1")c.add("key2", "value2")c.add("key3", "value3")// 验证结构和数据c.validateStructure(c.tree.get(c.tree.root))c.validateData()
}

3.2 插入后分裂

func TestSplitOnInsert(t *testing.T) {c := newC()// 插入大量键值对以触发分裂for i := 0; i < 100; i++ {key := fmt.Sprintf("key%d", i)val := fmt.Sprintf("value%d", i)c.add(key, val)}// 验证结构和数据c.validateStructure(c.tree.get(c.tree.root))c.validateData()
}

3.3 删除后合并

func TestMergeOnDelete(t *testing.T) {c := newC()// 插入键值对for i := 0; i < 10; i++ {key := fmt.Sprintf("key%d", i)val := fmt.Sprintf("value%d", i)c.add(key, val)}// 删除部分键值对以触发合并for i := 0; i < 5; i++ {key := fmt.Sprintf("key%d", i)c.remove(key)}// 验证结构和数据c.validateStructure(c.tree.get(c.tree.root))c.validateData()
}

---

4. 总结

通过上述设计和实现，我们可以全面测试 B+ 树的功能和性能。关键点包括：

1. 模拟页面管理：

   • 在内存中模拟页面分配、读取和释放操作。

2. 验证结构：

   • 确保树结构有效（键排序、节点大小限制）。

3. 验证数据一致性：

   • 确保 B+ 树中的数据与参考数据一致。

4. 典型测试场景：

   • 基本插入和查找。
   • 插入后分裂。
   • 删除后合并。

这种测试框架为验证 B+ 树的正确性和性能提供了强大的工具，同时也为进一步优化（如磁盘存储支持）奠定了基础。

代码仓库地址：database-go