B+树

B+树（B+ Tree）是一种常用于数据库和文件系统中的数据结构，用于高效地存储和管理大量的有序数据。它是B树的一种变体，旨在提供更好的磁盘访问性能和范围查询性能。B+树广泛用于数据库管理系统中，因为它在插入、删除和查找操作上具有高效的性能。

结构

最初学习这些数据结构的时候，上来就是看概念，大段的定义，后来发现是有一点不太对。编程本来就是属于工科类的学科，所以啊，还是需要先动手，先看代码，对B+的结构有个了解，再反过头来看定义，性质等等。

要不然很多同志连那某个Node中，为什么有keys，[]*Node都不太清楚，越看概念越蒙圈。

• Golang的B+结构

type BPlusTree struct {
	root *Node
}

type Node struct {
	isLeaf  bool
	keys    []int 
	child   []*Node
}

上述Demo，定义了一个简化的B+树数据结构，它由两个结构体组成：BPlusTree 和 Node。

BPlusTree 结构体:

root *Node：这是B+树的根节点。B+树的所有操作都是从根节点开始的，因此根节点是整棵树的入口点。

Node 结构体:

isLeaf bool：这个布尔值标志了节点是否是叶子节点。在B+树中，有两种类型的节点：叶子节点和内部节点。叶子节点包含实际的数据项，而内部节点只包含索引项。这个字段用来区分节点的类型。

keys []int：这是一个整数切片，用来存储节点中的关键字或索引项。关键字是用来对数据进行排序和查找的值。在叶子节点中，这些关键字对应于实际的数据项的键值。在内部节点中，这些关键字用于在树中导航到正确的子节点。

child []*Node：这是一个指向子节点的指针切片。对于内部节点，这些指针指向该节点的子节点。对于叶子节点，这个字段通常为空，因为叶子节点没有子节点。

这两个结构体定义了B+树的基本组成部分。B+树的核心思想是使用内部节点来建立索引，以便快速导航到叶子节点，从而实现高效的数据查找和范围查询操作。这个数据结构可以用于构建数据库索引、文件系统以及其他需要高效存储和检索有序数据的应用程序中。

B+树的特点

• 平衡性：B+树是一棵平衡树，确保了在插入和删除操作后，树保持相对平衡，以维持良好的性能。
• 叶子节点存储数据：与B树不同，B+树的叶子节点存储实际数据，内部节点仅用于索引，这有助于减少磁盘访问次数。
• 有序性：B+树的叶子节点是按顺序链接的，这使得范围查询非常高效。
• 多路搜索：B+树的每个节点可以包含多个子节点，这有助于减少树的高度，提高查找效率。

B+树通常在数据库系统中用于索引管理，可以加速查找和范围查询操作。由于其优点，它被广泛用于关系型数据库管理系统（RDBMS）的索引实现中，例如MySQL和Oracle等。

Golang实现Demo

package main

import (
    "fmt"
    "sort"
)

const (
    degree = 3 // B+树的度，树节点最多有2*degree个子节点
)

type BPlusTree struct {
    root *Node
}

type Node struct {
    isLeaf   bool
    keys     []int
    children []*Node
    data     map[int]string
    parent   *Node
}

func NewBPlusTree() *BPlusTree {
    return &BPlusTree{}
}

func (t *BPlusTree) Insert(key int, value string) {
    if t.root == nil {
        t.root = &Node{isLeaf: true}
    }

    if len(t.root.keys) >= 2*degree-1 {
        newRoot := &Node{}
        newRoot.children = append(newRoot.children, t.root)
        newRoot.splitChild(0)
        t.root = newRoot
    }

    t.root.insertNonFull(key, value)
}

func (n *Node) insertNonFull(key int, value string) {
    if n.isLeaf {
        n.insertIntoLeaf(key, value)
    } else {
        i := sort.Search(len(n.keys), func(i int) bool {
            return n.keys[i] >= key
        })

        if i == len(n.keys) || n.keys[i] != key {
            if len(n.children[i].keys) >= 2*degree-1 {
                n.splitChild(i)
                if key > n.keys[i] {
                    i++
                }
            }
            n.children[i].insertNonFull(key, value)
        } else {
            n.data[key] = value
        }
    }
}

func (n *Node) insertIntoLeaf(key int, value string) {
    i := sort.Search(len(n.keys), func(i int) bool {
        return n.keys[i] >= key
    })

    n.keys = append(n.keys, 0)
    copy(n.keys[i+1:], n.keys[i:])
    n.keys[i] = key
    n.data[key] = value
}

func (n *Node) splitChild(i int) {
    child := n.children[i]
    newChild := &Node{isLeaf: child.isLeaf}
    n.keys = append(n.keys, 0)
    copy(n.keys[i+1:], n.keys[i:])
    n.keys[i] = child.keys[degree-1]

    n.children = append(n.children, nil)
    copy(n.children[i+1:], n.children[i:])
    n.children[i+1] = newChild

    n.keys = n.keys[:len(n.keys)-1]
    copy(n.keys[degree:], n.keys[degree-1:])
    n.keys[degree-1] = 0

    if !child.isLeaf {
        copy(newChild.children, child.children[degree:])
        for j := degree; j < len(child.children); j++ {
            child.children[j] = nil
        }
    }

    for j := degree - 1; j < len(child.keys); j++ {
        newChild.keys = append(newChild.keys, child.keys[j])
        newChild.data[child.keys[j]] = child.data[child.keys[j]]
    }
    child.keys = child.keys[:degree-1]
    for j := range child.data {
        delete(child.data, j)
    }
}

func (t *BPlusTree) Search(key int) (string, bool) {
    if t.root == nil {
        return "", false
    }
    return t.root.search(key)
}

func (n *Node) search(key int) (string, bool) {
    i := sort.Search(len(n.keys), func(i int) bool {
        return n.keys[i] >= key
    })

    if i < len(n.keys) && n.keys[i] == key {
        return n.data[key], true
    }

    if n.isLeaf {
        return "", false
    }

    return n.children[i].search(key)
}

func main() {
    tree := NewBPlusTree()
    tree.Insert(10, "value1")
    tree.Insert(20, "value2")
    tree.Insert(5, "value3")

    value, found := tree.Search(10)
    if found {
        fmt.Println("Key 10:", value)
    } else {
        fmt.Println("Key 10 not found")
    }

    value, found = tree.Search(15)
    if found {
        fmt.Println("Key 15:", value)
    } else {
        fmt.Println("Key 15 not found")
    }
}