技术笔记

B+树详解与Go实现

Properties1
tags—

8分钟阅读

B+树详解与 Go 实现

一、B+树简介

1. 什么是 B+树？

B+树是一种自平衡的多叉搜索树，广泛应用于数据库和文件系统中，用于高效地存储和检索大量数据。与红黑树等二叉树不同，B+树的每个节点可以有多个子节点（即多路性），这使得树的高度更低，从而提高了磁盘 IO 的效率。

2. B+树的特性

  • 多路性：每个节点最多可以有 m 个子节点，m 被称为树的阶（order）。
  • 所有关键字都存储在叶子节点：内部节点仅存储用于索引的关键字，不保存实际的数据记录。
  • 叶子节点形成有序链表：所有叶子节点通过指针连接，方便范围查询和顺序访问。
  • 平衡性：树的所有叶子节点位于同一层级，保证了数据访问的均衡性。

3. B+树与 B 树的区别

  • 数据存储位置：B 树的关键字和数据都存储在内部节点和叶子节点；B+树的数据仅存储在叶子节点，内部节点只用于索引。
  • 链表结构：B+树的叶子节点通过链表连接，支持高效的顺序和范围查询；B 树没有这种链表结构。

4. 应用场景

  • 数据库索引：如 MySQL 的 InnoDB 引擎使用 B+树作为索引结构。
  • 文件系统：如 NTFS 文件系统使用 B+树来管理文件。

二、B+树的详细结构和操作

1. 节点结构

  • 内部节点（Index Node）：

    • 包含 n 个关键字和 n+1 个子节点指针。
    • 用于导航搜索路径，不存储实际数据。

  • 叶子节点（Leaf Node）：

    • 存储实际的数据记录（键值对）。
    • 包含指向下一个叶子节点的指针，形成链表结构。

2. 操作

2.1 查找（Search）

  • 从根节点开始，比较关键字，确定子树的方向。
  • 重复直到达到叶子节点。
  • 在叶子节点中查找实际的数据。

2.2 插入（Insert）

  • 在叶子节点找到插入位置，插入新的键值对。
  • 如果叶子节点未满，插入完成。
  • 如果叶子节点已满，进行节点分裂：
    • 将节点分裂为两个节点，新的关键字上移到父节点。
    • 如果父节点也满了，递归进行分裂。

2.3 删除（Delete）

  • 在叶子节点找到并删除键值对。
  • 如果删除后节点关键字数小于最小值，进行节点合并或键重分配：
    • 向兄弟节点借用关键字，或合并节点。
    • 可能导致父节点的关键字减少，递归调整。

三、用 Go 语言实现 B+树

1. 数据结构设计

1.1 常量定义

const (
    Order = 4 // B+树的阶数，实际开发中可根据需要调整
)

1.2 节点类型

type Node struct {
    isLeaf   bool
    keys     []int
    children []*Node
    next     *Node // 仅叶子节点使用，用于链表连接
}
  • isLeaf：标识是否为叶子节点。
  • keys：存储关键字。
  • children：存储子节点指针。
  • next：叶子节点的指针，形成链表。

1.3 树结构

type BPlusTree struct {
    root *Node
}

2. 关键操作实现

2.1 初始化

func NewBPlusTree() *BPlusTree {
    return &BPlusTree{
        root: &Node{
            isLeaf:   true,
            keys:     []int{},
            children: []*Node{},
            next:     nil,
        },
    }
}

2.2 查找操作

func (tree *BPlusTree) Search(key int) (*Node, int) {
    current := tree.root
    for !current.isLeaf {
        idx := sort.SearchInts(current.keys, key)
        if idx < len(current.keys) && current.keys[idx] == key {
            idx++
        }
        current = current.children[idx]
    }
    idx := sort.SearchInts(current.keys, key)
    if idx < len(current.keys) && current.keys[idx] == key {
        return current, idx
    }
    return nil, -1
}

2.3 插入操作

func (tree *BPlusTree) Insert(key int) {
    root := tree.root
    if len(root.keys) == 2*Order-1 {
        newRoot := &Node{
            isLeaf:   false,
            keys:     []int{},
            children: []*Node{root},
        }
        tree.root = newRoot
        tree.splitChild(newRoot, 0)
        tree.insertNonFull(newRoot, key)
    } else {
        tree.insertNonFull(root, key)
    }
}
 
func (tree *BPlusTree) insertNonFull(node *Node, key int) {
    if node.isLeaf {
        idx := sort.SearchInts(node.keys, key)
        node.keys = append(node.keys[:idx], append([]int{key}, node.keys[idx:]...)...)
    } else {
        idx := sort.SearchInts(node.keys, key)
        child := node.children[idx]
        if len(child.keys) == 2*Order-1 {
            tree.splitChild(node, idx)
            if key > node.keys[idx] {
                idx++
            }
        }
        tree.insertNonFull(node.children[idx], key)
    }
}
 
func (tree *BPlusTree) splitChild(parent *Node, index int) {
    node := parent.children[index]
    newNode := &Node{
        isLeaf:   node.isLeaf,
        keys:     append([]int{}, node.keys[Order:]...),
        children: append([]*Node{}, node.children[Order:]...),
    }
    node.keys = node.keys[:Order-1]
    node.children = node.children[:Order]
    parent.keys = append(parent.keys[:index], append([]int{node.keys[Order-1]}, parent.keys[index:]...)...)
    parent.children = append(parent.children[:index+1], append([]*Node{newNode}, parent.children[index+1:]...)...)
 
    if node.isLeaf {
        newNode.next = node.next
        node.next = newNode
    }
}

2.4 删除操作（可选）

由于删除操作较为复杂，此处暂不实现。

3. 示例代码

package main
 
import (
    "fmt"
    "sort"
)
 
const (
    Order = 4
)
 
type Node struct {
    isLeaf   bool
    keys     []int
    children []*Node
    next     *Node
}
 
type BPlusTree struct {
    root *Node
}
 
func NewBPlusTree() *BPlusTree {
    return &BPlusTree{
        root: &Node{
            isLeaf:   true,
            keys:     []int{},
            children: []*Node{},
            next:     nil,
        },
    }
}
 
// 实现Search、Insert、splitChild等方法（如上所示）
 
func main() {
    tree := NewBPlusTree()
    keys := []int{5, 15, 25, 35, 45, 55, 65, 75}
    for _, key := range keys {
        tree.Insert(key)
    }
 
    node, idx := tree.Search(25)
    if node != nil {
        fmt.Printf("找到关键字: %d\n", node.keys[idx])
    } else {
        fmt.Println("未找到关键字")
    }
}

4. 代码解释

  • NewBPlusTree：初始化一棵新的 B+树。
  • Insert：插入新的关键字，处理根节点满的情况。
  • insertNonFull：在非满节点中插入关键字。
  • splitChild：分裂满子节点，调整父节点的关键字和子节点指针。
  • Search：查找关键字，返回所在的叶子节点和索引。

5. 注意事项

  • 节点分裂和合并：需要仔细处理边界条件，确保树的平衡性。
  • 并发控制：在实际应用中，需要考虑并发读写的情况，使用锁或其他同步机制。
  • 磁盘 IO 优化：B+树的优势在于降低磁盘 IO，在内存中实现时需模拟磁盘行为。

四、总结

B+树作为一种高效的索引结构，在数据库和文件系统中有广泛的应用。使用 Go 语言实现 B+树，需要仔细设计数据结构和算法，确保正确性和效率。在实际开发中，还需要考虑并发控制、磁盘 IO 和性能优化等因素。

关系图谱