B-tree数据结构

btree的go实现：https://github.com/sutoo/btree/blob/master/btree.go

// Item represents a single object in the tree.
type Item interface {
	// Less tests whether the current item is less than the given argument.
	//
	// This must provide a strict weak ordering.
	// If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
	// hold one of either a or b in the tree).
	Less(than Item) bool
}

type items []Item
// children stores child nodes in a node.
type children []*node

// node is an internal node in a tree.
//
// It must at all times maintain the invariant that either
//   * len(children) == 0, len(items) unconstrained
//   * len(children) == len(items) + 1
type node struct {
	items    items
	children children
	cow      *copyOnWriteContext
}
// BTree is an implementation of a B-Tree.
//
// BTree stores Item instances in an ordered structure, allowing easy insertion,
// removal, and iteration.
//
// Write operations are not safe for concurrent mutation by multiple
// goroutines, but Read operations are.
type BTree struct {
	degree int
	length int
	root   *node
	cow    *copyOnWriteContext
}

node是Btree中的一个节点。

items 表示key的列表， items中的gap对应一个children node。

###BTree Struct

方法介绍：

maxItems degree * 2 -1 ，每个node中，items的最大值。

minItemsdegree - 1，node中，items的最小值。

###Btree and B+tree

Btree:

B+tree: