btree

README

btree

An efficient B-tree implementation in Go.

Check out the generics branch if you want to try out btree with generic support for Go 1.18+

Features

• Copy() method with copy-on-write support.
• Fast bulk loading for pre-ordered data using the Load() method.
• All operations are thread-safe.
• Path hinting optimization for operations with nearby keys.

Installing

To start using btree, install Go and run go get:

$ go get -u github.com/tidwall/btree

Usage

package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

type Item struct {
	Key, Val string
}

// byKeys is a comparison function that compares item keys and returns true
// when a is less than b.
func byKeys(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	return i1.Key < i2.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	if i1.Val < i2.Val {
		return true
	}
	if i1.Val > i2.Val {
		return false
	}
	// Both vals are equal so we should fall though
	// and let the key comparison take over.
	return byKeys(a, b)
}

func main() {
	// Create a tree for keys and a tree for values.
	// The "keys" tree will be sorted on the Keys field.
	// The "values" tree will be sorted on the Values field.
	keys := btree.New(byKeys)
	vals := btree.New(byVals)

	// Create some items.
	users := []*Item{
		&Item{Key: "user:1", Val: "Jane"},
		&Item{Key: "user:2", Val: "Andy"},
		&Item{Key: "user:3", Val: "Steve"},
		&Item{Key: "user:4", Val: "Andrea"},
		&Item{Key: "user:5", Val: "Janet"},
		&Item{Key: "user:6", Val: "Andy"},
	}

	// Insert each user into both trees
	for _, user := range users {
		keys.Set(user)
		vals.Set(user)
	}

	// Iterate over each user in the key tree
	keys.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	fmt.Printf("\n")
	// Iterate over each user in the val tree
	vals.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:4 Andrea
	// user:2 Andy
	// user:6 Andy
	// user:1 Jane
	// user:5 Janet
	// user:3 Steve
}

Operations

Basic

Len()                   # return the number of items in the btree
Set(item)               # insert or replace an existing item
Get(item)               # get an existing item
Delete(item)            # delete an item

Iteration

Ascend(pivot, iter)     # scan items in ascending order starting at pivot.
Descend(pivot, iter)    # scan items in descending order starting at pivot.

Queues

Min()                   # return the first item in the btree
Max()                   # return the last item in the btree
PopMin()                # remove and return the first item in the btree
PopMax()                # remove and return the last item in the btree

Bulk loading

Load(item)              # load presorted items into tree

Path hints

SetHint(item, *hint)    # insert or replace an existing item
GetHint(item, *hint)    # get an existing item
DeleteHint(item, *hint) # delete an item

Array-like operations

GetAt(index)     # returns the value at index
DeleteAt(index)  # deletes the item at index

Performance

This implementation was designed with performance in mind.

The following benchmarks were run on my 2019 Macbook Pro (2.4 GHz 8-Core Intel Core i9) using Go 1.17.3. The items are simple 8-byte ints.

• google: The google/btree package
• tidwall: The tidwall/btree package
• go-arr: Just a simple Go array

** sequential set **
google:  set-seq        1,000,000 ops in 178ms, 5,618,049/sec, 177 ns/op, 39.0 MB, 40 bytes/op
tidwall: set-seq        1,000,000 ops in 156ms, 6,389,837/sec, 156 ns/op, 23.5 MB, 24 bytes/op
tidwall: set-seq-hint   1,000,000 ops in 78ms, 12,895,355/sec, 77 ns/op, 23.5 MB, 24 bytes/op
tidwall: load-seq       1,000,000 ops in 53ms, 18,937,400/sec, 52 ns/op, 23.5 MB, 24 bytes/op
go-arr:  append         1,000,000 ops in 78ms, 12,843,432/sec, 77 ns/op

** random set **
google:  set-rand       1,000,000 ops in 555ms, 1,803,133/sec, 554 ns/op, 29.7 MB, 31 bytes/op
tidwall: set-rand       1,000,000 ops in 545ms, 1,835,818/sec, 544 ns/op, 29.6 MB, 31 bytes/op
tidwall: set-rand-hint  1,000,000 ops in 670ms, 1,493,473/sec, 669 ns/op, 29.6 MB, 31 bytes/op
tidwall: set-again      1,000,000 ops in 681ms, 1,469,038/sec, 680 ns/op
tidwall: set-after-copy 1,000,000 ops in 670ms, 1,493,230/sec, 669 ns/op
tidwall: load-rand      1,000,000 ops in 569ms, 1,756,187/sec, 569 ns/op, 29.6 MB, 31 bytes/op

** sequential get **
google:  get-seq        1,000,000 ops in 165ms, 6,048,307/sec, 165 ns/op
tidwall: get-seq        1,000,000 ops in 144ms, 6,940,120/sec, 144 ns/op
tidwall: get-seq-hint   1,000,000 ops in 78ms, 12,815,243/sec, 78 ns/op

** random get **
google:  get-rand       1,000,000 ops in 701ms, 1,427,507/sec, 700 ns/op
tidwall: get-rand       1,000,000 ops in 679ms, 1,473,531/sec, 678 ns/op
tidwall: get-rand-hint  1,000,000 ops in 824ms, 1,213,805/sec, 823 ns/op

You can find the benchmark utility at tidwall/btree-benchmark

Contact

Josh Baker @tidwall

License

Source code is available under the MIT License.

Documentation

Overview

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Index

• type BTree
  • func New(less func(a, b interface{}) bool) *BTree
  • func NewNonConcurrent(less func(a, b interface{}) bool) *BTree
  • func (tr *BTree) Ascend(pivot interface{}, iter func(item interface{}) bool)
  • func (tr *BTree) Copy() *BTree
  • func (tr *BTree) Delete(key interface{}) interface{}
  • func (tr *BTree) DeleteAt(index int) interface{}
  • func (tr *BTree) DeleteHint(key interface{}, hint *PathHint) interface{}
  • func (tr *BTree) Descend(pivot interface{}, iter func(item interface{}) bool)
  • func (tr *BTree) Get(key interface{}) interface{}
  • func (tr *BTree) GetAt(index int) interface{}
  • func (tr *BTree) GetHint(key interface{}, hint *PathHint) interface{}
  • func (tr *BTree) Height() int
  • func (tr *BTree) Len() int
  • func (tr *BTree) Less(a, b interface{}) bool
  • func (tr *BTree) Load(item interface{}) interface{}
  • func (tr *BTree) Max() interface{}
  • func (tr *BTree) Min() interface{}
  • func (tr *BTree) PopMax() interface{}
  • func (tr *BTree) PopMin() interface{}
  • func (tr *BTree) Set(item interface{}) interface{}
  • func (tr *BTree) SetHint(item interface{}, hint *PathHint) (prev interface{})
  • func (tr *BTree) Walk(iter func(items []interface{}))
• type PathHint

Types

type BTree

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

func New

func New(less func(a, b interface{}) bool) *BTree

New returns a new BTree

func NewNonConcurrent

func NewNonConcurrent(less func(a, b interface{}) bool) *BTree

NewNonConcurrent returns a new BTree which is not safe for concurrent write operations by multiple goroutines.

This is useful for when you do not need the BTree to manage the locking, but would rather do it yourself.

func (*BTree) Ascend

func (tr *BTree) Ascend(pivot interface{}, iter func(item interface{}) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*BTree) Copy

func (tr *BTree) Copy() *BTree

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*BTree) Delete

func (tr *BTree) Delete(key interface{}) interface{}

Delete a value for a key

func (*BTree) DeleteAt

func (tr *BTree) DeleteAt(index int) interface{}

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) DeleteHint

func (tr *BTree) DeleteHint(key interface{}, hint *PathHint) interface{}

DeleteHint deletes a value for a key using a path hint

func (*BTree) Descend

func (tr *BTree) Descend(pivot interface{}, iter func(item interface{}) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*BTree) Get

func (tr *BTree) Get(key interface{}) interface{}

Get a value for key

func (*BTree) GetAt

func (tr *BTree) GetAt(index int) interface{}

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) GetHint

func (tr *BTree) GetHint(key interface{}, hint *PathHint) interface{}

GetHint gets a value for key using a path hint

func (*BTree) Height

func (tr *BTree) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*BTree) Len

func (tr *BTree) Len() int

Len returns the number of items in the tree

func (*BTree) Less

func (tr *BTree) Less(a, b interface{}) bool

Less is a convenience function that performs a comparison of two items using the same "less" function provided to New.

func (*BTree) Load

func (tr *BTree) Load(item interface{}) interface{}

Load is for bulk loading pre-sorted items

func (*BTree) Max

func (tr *BTree) Max() interface{}

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*BTree) Min

func (tr *BTree) Min() interface{}

Min returns the minimum item in tree. Returns nil if the tree has no items.

func (*BTree) PopMax

func (tr *BTree) PopMax() interface{}

PopMax removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) PopMin

func (tr *BTree) PopMin() interface{}

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) Set

func (tr *BTree) Set(item interface{}) interface{}

Set or replace a value for a key

func (*BTree) SetHint

func (tr *BTree) SetHint(item interface{}, hint *PathHint) (prev interface{})

SetHint sets or replace a value for a key using a path hint

func (*BTree) Walk

func (tr *BTree) Walk(iter func(items []interface{}))

Walk iterates over all items in tree, in order. The items param will contain one or more items.

type PathHint

type PathHint = btree.PathHint

PathHint is a utility type used with the *Hint() functions. Hints provide faster operations for clustered keys.