Package btree implements a B-tree.
According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:
- Every node has at most m children.
- Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
- The root has at least two children if it is not a leaf node.
- A non-leaf node with k children contains k − 1 keys.
- All leaves appear in the same level and carry no information.
go get github.com/hslam/btree
import "github.com/hslam/btree"
package main
import (
"fmt"
"github.com/hslam/btree"
)
func main() {
tree := btree.New(2)
str := String("Hello World")
tree.Insert(str)
fmt.Println(tree.Search(str))
tree.Delete(str)
}
type String string
func (a String) Less(b btree.Item) bool {
return a < b.(String)
}Hello World
package main
import (
"fmt"
"github.com/hslam/btree"
)
func main() {
tree := btree.New(2)
for i := 0; i < 10; i++ {
tree.Insert(Int(i))
}
iter := tree.Min().MinIterator()
for iter != nil {
fmt.Printf("%d\t", iter.Item())
iter = iter.Next()
}
}
type Int int
func (a Int) Less(b btree.Item) bool {
return a < b.(Int)
}
0 1 2 3 4 5 6 7 8 9
This package is licensed under a MIT license (Copyright (c) 2020 Meng Huang)
btree was written by Meng Huang.