btree

Package btree implements a B-tree.

Definition

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.

Benchmark

Get started

Install

go get github.com/hslam/btree

Import

import "github.com/hslam/btree"

Usage

Example

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)
}

Output

Hello World

Iterator Example

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)
}

B-Tree

Output

0    1    2    3    4    5    6    7    8    9

License

This package is licensed under a MIT license (Copyright (c) 2020 Meng Huang)

Author

btree was written by Meng Huang.