btree

README

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.

Documentation

Overview

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: https://en.wikipedia.org/wiki/B-tree

1. Every node has at most m children.

2. Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.

3. The root has at least two children if it is not a leaf node.

4. A non-leaf node with k children contains k − 1 keys.

5. All leaves appear in the same level and carry no information.

Index

• type Int
  • func (a Int) Less(b Item) bool
• type Item
• type Iterator
  • func (i *Iterator) Clone() *Iterator
  • func (i *Iterator) Item() Item
  • func (i *Iterator) Last() (last *Iterator)
  • func (i *Iterator) Next() (next *Iterator)
• type Node
  • func (n *Node) Children() []*Node
  • func (n *Node) Items() []Item
  • func (n *Node) Iterator(index int) *Iterator
  • func (n *Node) MaxIterator() *Iterator
  • func (n *Node) MinIterator() *Iterator
  • func (n *Node) Parent() *Node
• type String
  • func (a String) Less(b Item) bool
• type Tree
  • func New(degree int) *Tree
  • func (t *Tree) Clear()
  • func (t *Tree) Delete(item Item)
  • func (t *Tree) Insert(item Item)
  • func (t *Tree) Length() int
  • func (t *Tree) Max() *Node
  • func (t *Tree) MaxItems() int
  • func (t *Tree) Min() *Node
  • func (t *Tree) MinItems() int
  • func (t *Tree) Root() *Node
  • func (t *Tree) Search(item Item) Item
  • func (t *Tree) SearchIterator(item Item) *Iterator
  • func (t *Tree) SearchNode(item Item) *Node

Types

type Int

type Int int

Int implements the Item interface for int.

func (Int) Less

func (a Int) Less(b Item) bool

Less returns true if int(a) < int(b).

type Item

type Item interface {
	// Less compares whether the current item is less than the given Item.
	Less(than Item) bool
}

Item represents a value in the tree.

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator represents an iterator in the B-tree.

func (*Iterator) Clone

func (i *Iterator) Clone() *Iterator

Clone returns the clone of this iterator.

func (*Iterator) Item

func (i *Iterator) Item() Item

Item returns the item of this iterator.

func (*Iterator) Last

func (i *Iterator) Last() (last *Iterator)

Last returns the last iterator less than this iterator.

func (*Iterator) Next

func (i *Iterator) Next() (next *Iterator)

Next returns the next iterator more than this iterator.

type Node

type Node struct {
	// contains filtered or unexported fields
}

Node represents a node in the B-tree.

func (*Node) Children

func (n *Node) Children() []*Node

Children returns the children of this node.

func (*Node) Items

func (n *Node) Items() []Item

Items returns the items of this node.

func (*Node) Iterator

func (n *Node) Iterator(index int) *Iterator

Iterator returns the iterator with the item index of this node.

func (*Node) MaxIterator

func (n *Node) MaxIterator() *Iterator

MaxIterator returns the iterator with the max item index of this node.

func (*Node) MinIterator

func (n *Node) MinIterator() *Iterator

MinIterator returns the iterator with the min item index of this node.

func (*Node) Parent

func (n *Node) Parent() *Node

Parent returns the parent node.

type String

type String string

String implements the Item interface for string.

func (String) Less

func (a String) Less(b Item) bool

Less returns true if string(a) < string(b).

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree represents a B-tree.

func New

func New(degree int) *Tree

New returns a new B-tree with the given degree.

func (*Tree) Clear

func (t *Tree) Clear()

Clear removes all items from the B-tree.

func (*Tree) Delete

func (t *Tree) Delete(item Item)

Delete deletes the node of the B-tree with the item.

func (*Tree) Insert

func (t *Tree) Insert(item Item)

Insert inserts the item into the B-tree.

func (*Tree) Length

func (t *Tree) Length() int

Length returns the number of items currently in the B-tree.

func (*Tree) Max

func (t *Tree) Max() *Node

Max returns the max node of the B-tree.

func (*Tree) MaxItems

func (t *Tree) MaxItems() int

MaxItems returns the max number of items to allow per Node.

func (*Tree) Min

func (t *Tree) Min() *Node

Min returns the min node of the B-tree.

func (*Tree) MinItems

func (t *Tree) MinItems() int

MinItems returns the min number of items to allow per node (ignored for the root node).

func (*Tree) Root

func (t *Tree) Root() *Node

Root returns the root node of the B-tree.

func (*Tree) Search

func (t *Tree) Search(item Item) Item

Search searches the Item of the B-tree.

func (*Tree) SearchIterator

func (t *Tree) SearchIterator(item Item) *Iterator

SearchIterator searches the iterator of the B-tree with the item.

func (*Tree) SearchNode

func (t *Tree) SearchNode(item Item) *Node

SearchNode searches the node of the B-tree with the item.