在第二章中，我们讨论过改善链式结构存储友好性的办法（团块化），本节则要把它应用到树上面。
type bNode[T constraints.Ordered] struct {
inner bool //true表示为内节点，false表示为叶节点
view []T //数据窗口，指向派生类的data字段
}
type iNode[T constraints.Ordered] struct {
bNode[T] //inner==true
data [iFullSize]T //索引
kids [iFullSize]*iNode[T] //子节点指针域（类型不安全，有可能为叶节点）
}
type lNode[T constraints.Ordered] struct {
bNode[T] //inner==false
data [lFullSize]T //负载
next *lNode[T] //链表指针域
}B+树由索引节点和存储节点组成，是一种完美平衡的多叉树。其中，索引节点中的索引值为其对应子节点内容的最大值。而存储节点作为树的叶节点同时，还构成有序块链表。
[3 6 9]
/ | \
[1 2 3] [4 5 6] [7 8 9]
[5 9]
/ \
[3 6 9] => [3 6 9] => [3 5] [6 9]
/ | \ / / \ \ / | | \
[0 1 2] [3 4 5] [6 8 9] [1 2 3] [4 5] [5 6] [7 8 9] [1 2 3] [4 5] [5 6] [7 8 9]
向已满节点插入新元素时，我们将该节点一分为二：
func (tr *Tree[T]) Insert(key T) bool {
if tr.root == nil {
//...
}
tr.path.Clear()
node, pos := tr.root, 0
if key > tr.root.ceil() { //超出上界
for node.inner {
pos = len(node.view) - 1
node.data[pos] = key //一路更新
tr.path.Push(trait[T]{node, pos})
node = node.kids[pos]
}
pos = len(node.view)
} else {
for node.inner {
pos = array.SearchFirstGE(node.view, key)
if key == node.view[pos] { return false }
tr.path.Push(trait[T]{node, pos}) //路径追踪
node = node.kids[pos]
}
pos = array.SearchFirstGE(node.view, key)
if key == node.view[pos] { return false }
}
peer := node.asLeaf().insert(pos, key).asIndex()
for peer != nil { //分裂出新节点，继续
if tr.path.IsEmpty() {
//...
} else {
last := tr.path.Pop()
last.node.view[last.idx] = node.ceil()
node, peer = last.node, last.node.insert(last.idx+1, peer)
} }
return true
} [4 9] [4 9] [4 9]
/ \ / \ / \
[2 4] [6 9] => [2 4] [6 9] => [4] [6 9] => [4 6 9]
/ | | \ / | | \ / | \ / | \
[1 2] [3 4] [5 6] [7 8 9] [1 2] [4] [5 6] [7 8 9] [1 2 4] [5 6] [7 8 9] [1 2 4] [5 6] [7 8 9]
删除元素后，我们尝试对残余数据量低的节点处理：和附近节点合并或者从附近节点分流数据。
func (tr *Tree[T]) Remove(key T) bool {
//...
node.asLeaf().remove(pos)
if tr.path.IsEmpty() { //对根节点采用直接删除
if len(node.view) == 0 {
tr.root, tr.head = nil, nil
}
return true
} //除了到根节点，len(node.view) >= 2
shrink, ceil := (pos == len(node.view)), node.ceil() //需要额外的索引修正
last := tr.path.Pop() //数据量少，考虑合并节点
for limit, isLeaf := lQuarterSize, true; len(node.view) < limit; limit, isLeaf = iQuarterSize, false {
peer := node
if last.idx == len(last.node.view)-1 { //向前
node = last.node.kids[last.idx-1]
} else { //向后
last.idx++
peer, shrink = last.node.kids[last.idx], false
}
combined := false
if isLeaf {
combined = node.asLeaf().combine(peer.asLeaf())
} else {
combined = node.combine(peer) //尝试合并
}
last.node.view[last.idx-1] = node.ceil() //修正索引
if !combined { break } //中止
last.node.remove(last.idx)
if tr.path.IsEmpty() {
if len(last.node.view) == 1 { //对根节点采用缩节处理
tr.root = last.node.kids[0]
}
return true
}
node = last.node
last = tr.path.Pop()
}
if shrink { //合并已结束，但索引修正未完成
last.node.view[last.idx] = ceil
for last.idx == len(last.node.view)-1 && //级联
!tr.path.IsEmpty() {
last = tr.path.Pop()
last.node.view[last.idx] = ceil
} }
return true
}B+树是查询、插入、删除都为O(logN)的三好学生，只是节点的分裂与合并涉及数据挪移，有一定开销。事实上，B+树虽然比较笨重，从上一节的评测中可以看出，其性能通常比二叉搜索树要强。造成此等结果的根源在于随机访存性能不理想，团块型结构往往比纯链式结构要吃香。