B+树的原理、优势及其Go语言实现

package main

import (
	"fmt"
	"sort"
)

// 定义节点结构
const (
	MaxKeys = 4 // 每个节点的最大键数
)

type Node struct {
	keys     []int      // 节点中的键
	children []*Node    // 子节点
	isLeaf   bool       // 是否是叶子节点
	next     *Node      // 叶子节点的链表指针
}

type BPlusTree struct {
	root *Node
}

// 创建一个新的节点
func newNode(isLeaf bool) *Node {
	return &Node{
		keys:     []int{},
		children: []*Node{},
		isLeaf:   isLeaf,
	}
}

// 创建 B+树
func NewBPlusTree() *BPlusTree {
	return &BPlusTree{
		root: newNode(true),
	}
}

// 查找操作
func (t *BPlusTree) Search(key int) bool {
	node := t.root
	for {
		i := sort.SearchInts(node.keys, key)
		if i < len(node.keys) && node.keys[i] == key {
			return true
		}
		if node.isLeaf {
			return false
		}
		node = node.children[i]
	}
}

// 插入操作
func (t *BPlusTree) Insert(key int) {
	root := t.root
	if len(root.keys) == MaxKeys {
		// 根节点分裂
		newRoot := newNode(false)
		newRoot.children = append(newRoot.children, root)
		t.splitChild(newRoot, 0)
		t.root = newRoot
	}
	t.insertNonFull(t.root, key)
}

// 插入非满节点
func (t *BPlusTree) insertNonFull(node *Node, key int) {
	if node.isLeaf {
		node.keys = append(node.keys, key)
		sort.Ints(node.keys)
		return
	}
	i := sort.SearchInts(node.keys, key)
	if len(node.children[i].keys) == MaxKeys {
		t.splitChild(node, i)
		if key > node.keys[i] {
			i++
		}
	}
	t.insertNonFull(node.children[i], key)
}

// 分裂子节点
func (t *BPlusTree) splitChild(parent *Node, index int) {
	child := parent.children[index]
	newChild := newNode(child.isLeaf)
	mid := MaxKeys / 2

	// 分裂键值
	parent.keys = append(parent.keys[:index], append([]int{child.keys[mid]}, parent.keys[index:]...)...)
	newChild.keys = append(newChild.keys, child.keys[mid+1:]...)
	child.keys = child.keys[:mid]

	// 分裂子节点
	if !child.isLeaf {
		newChild.children = append(newChild.children, child.children[mid+1:]...)
		child.children = child.children[:mid+1]
	}

	parent.children = append(parent.children[:index+1], append([]*Node{newChild}, parent.children[index+1:]...)...)

	// 更新链表
	if child.isLeaf {
		newChild.next = child.next
		child.next = newChild
	}
}

// 打印 B+树
func (t *BPlusTree) Print() {
	queue := []*Node{t.root}
	for len(queue) > 0 {
		nextQueue := []*Node{}
		for _, node := range queue {
			fmt.Print(node.keys, " ")
			if !node.isLeaf {
				nextQueue = append(nextQueue, node.children...)
			}
		}
		fmt.Println()
		queue = nextQueue
	}
}

func main() {
	tree := NewBPlusTree()
	tree.Insert(10)
	tree.Insert(20)
	tree.Insert(5)
	tree.Insert(6)
	tree.Insert(15)
	tree.Insert(30)

	tree.Print()
}