B-tree implementation for Go

Overview

btree

GoDoc

An efficient B-tree implementation in Go.

Features

  • Support for Generics (Go 1.18).
  • Map and Set types for ordered key-value maps and sets,
  • Fast bulk loading for pre-ordered data using the Load() method.
  • Copy() method with copy-on-write support.
  • Thread-safe operations.
  • Path hinting optimization for operations with nearby keys.

Using

To start using this package, install Go and run:

$ go get github.com/tidwall/btree

To use the generics version of this library, install Go 1.18 beta and run:

$ go get github.com/tidwall/[email protected]

B-tree types

This package includes the following types of B-trees:

  • btree.Map: A fast B-tree for storing ordered key value pairs. Go 1.18+
  • btree.Set: Like Map, but only for storing keys. Go 1.18+
  • btree.Generic: A feature-rich B-tree for storing data using a custom comparator. Go 1.18+
  • btree.BTree: Like Generic but uses the interface{} type for data. Backwards compatible. Go 1.16+

btree.Map

// Basic
Set(key, value)    // insert or replace an item
Get(key, value)    // get an existing item
Delete(key)        // delete an item
Len()              // return the number of items in the map

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key, value)   // load presorted items into tree

Example

package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a map
	var users btree.Map[string, string]

	// add some users
	users.Set("user:4", "Andrea")
	users.Set("user:6", "Andy")
	users.Set("user:2", "Andy")
	users.Set("user:1", "Jane")
	users.Set("user:5", "Janet")
	users.Set("user:3", "Steve")

	// Iterate over the maps and print each user
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	users.Delete("user:5")
	users.Delete("user:1")

	// print the map again
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

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

btree.Set

// Basic
Insert(key)        // insert an item
Contains(key)      // test if item exists
Delete(key)        // delete an item
Len()              // return the number of items in the set

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key)          // load presorted item into tree

Example

package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a set
	var names btree.Set[string]

	// add some names
	names.Insert("Jane")
	names.Insert("Andrea")
	names.Insert("Steve")
	names.Insert("Andy")
	names.Insert("Janet")
	names.Insert("Andy")

	// Iterate over the maps and print each user
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	names.Delete("Steve")
	names.Delete("Andy")

	// print the map again
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Output:
	// Andrea
	// Andy
	// Jane
	// Janet
	// Steve
	//
	// Andrea
	// Jane
	// Janet
}

btree.Generic

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

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

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

// Copy-on-write
Copy()                  // copy the btree

Example

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 Item) bool {
	return a.Key < b.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b Item) bool {
	if a.Val < b.Val {
		return true
	}
	if a.Val > b.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.NewGeneric[Item](byKeys)
	vals := btree.NewGeneric[Item](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.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.Val)
		return true
	})
	fmt.Printf("\n")

	// Iterate over each user in the val tree
	vals.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.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
}

btree.BTree

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

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

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

// Copy-on-write
Copy()                  // copy the btree

Example

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
}

Performance

This implementation was designed with performance in mind.

  • google: The google/btree package (without generics)
  • tidwall: The tidwall/btree package (without generics)
  • tidwall(G): The tidwall/btree package (generics using the btree.Generic type)
  • tidwall(M): The tidwall/btree package (generics using the btree.Map type)
  • go-arr: A simple Go array

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

** sequential set **
google:     set-seq        1,000,000 ops in 156ms, 6,426,724/sec, 155 ns/op, 39.0 MB, 40 bytes/op
tidwall:    set-seq        1,000,000 ops in 135ms, 7,380,627/sec, 135 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): set-seq        1,000,000 ops in 78ms, 12,881,995/sec, 77 ns/op, 8.2 MB, 8 bytes/op
tidwall(M): set-seq        1,000,000 ops in 46ms, 21,892,141/sec, 45 ns/op, 8.2 MB, 8 bytes/op
tidwall:    set-seq-hint   1,000,000 ops in 73ms, 13,789,017/sec, 72 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): set-seq-hint   1,000,000 ops in 48ms, 20,969,431/sec, 47 ns/op, 8.2 MB, 8 bytes/op
tidwall:    load-seq       1,000,000 ops in 45ms, 22,452,523/sec, 44 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): load-seq       1,000,000 ops in 22ms, 46,242,274/sec, 21 ns/op, 8.2 MB, 8 bytes/op
tidwall(M): load-seq       1,000,000 ops in 13ms, 74,371,903/sec, 13 ns/op, 8.2 MB, 8 bytes/op
go-arr:     append         1,000,000 ops in 21ms, 47,141,875/sec, 21 ns/op, 8.1 MB, 8 bytes/op

** sequential get **
google:     get-seq        1,000,000 ops in 119ms, 8,389,459/sec, 119 ns/op
tidwall:    get-seq        1,000,000 ops in 110ms, 9,068,759/sec, 110 ns/op
tidwall(G): get-seq        1,000,000 ops in 78ms, 12,813,135/sec, 78 ns/op
tidwall(M): get-seq        1,000,000 ops in 62ms, 16,053,728/sec, 62 ns/op
tidwall:    get-seq-hint   1,000,000 ops in 64ms, 15,509,696/sec, 64 ns/op
tidwall(G): get-seq-hint   1,000,000 ops in 41ms, 24,144,951/sec, 41 ns/op

** random set **
google:     set-rand       1,000,000 ops in 563ms, 1,777,592/sec, 562 ns/op, 29.7 MB, 31 bytes/op
tidwall:    set-rand       1,000,000 ops in 542ms, 1,844,397/sec, 542 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): set-rand       1,000,000 ops in 234ms, 4,271,764/sec, 234 ns/op, 11.2 MB, 11 bytes/op
tidwall(M): set-rand       1,000,000 ops in 189ms, 5,292,236/sec, 188 ns/op, 11.2 MB, 11 bytes/op
tidwall:    set-rand-hint  1,000,000 ops in 602ms, 1,659,852/sec, 602 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): set-rand-hint  1,000,000 ops in 278ms, 3,595,435/sec, 278 ns/op, 11.2 MB, 11 bytes/op
tidwall:    set-after-copy 1,000,000 ops in 679ms, 1,471,954/sec, 679 ns/op
tidwall(G): set-after-copy 1,000,000 ops in 238ms, 4,196,854/sec, 238 ns/op
tidwall:    load-rand      1,000,000 ops in 532ms, 1,880,877/sec, 531 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): load-rand      1,000,000 ops in 232ms, 4,316,475/sec, 231 ns/op, 11.2 MB, 11 bytes/op
tidwall(M): load-rand      1,000,000 ops in 209ms, 4,790,169/sec, 208 ns/op, 11.2 MB, 11 bytes/op

** random get **
google:     get-rand       1,000,000 ops in 807ms, 1,238,703/sec, 807 ns/op
tidwall:    get-rand       1,000,000 ops in 812ms, 1,231,551/sec, 811 ns/op
tidwall(G): get-rand       1,000,000 ops in 255ms, 3,914,819/sec, 255 ns/op
tidwall(M): get-rand       1,000,000 ops in 190ms, 5,249,966/sec, 190 ns/op
tidwall:    get-rand-hint  1,000,000 ops in 876ms, 1,141,313/sec, 876 ns/op
tidwall(G): get-rand-hint  1,000,000 ops in 258ms, 3,877,775/sec, 257 ns/op

** range **
google:     ascend        1,000,000 ops in 26ms, 39,101,882/sec, 25 ns/op
tidwall:    ascend        1,000,000 ops in 20ms, 50,223,988/sec, 19 ns/op
tidwall(G): iter          1,000,000 ops in 8ms, 119,155,937/sec, 8 ns/op
tidwall(G): scan          1,000,000 ops in 6ms, 168,275,407/sec, 5 ns/op
tidwall(G): walk          1,000,000 ops in 5ms, 186,941,046/sec, 5 ns/op
go-arr:     for-loop      1,000,000 ops in 4ms, 272,234,997/sec, 3 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.

Issues
  • Nice. Does it come with a disk backed version one?

    Nice. Does it come with a disk backed version one?

    Basically wanting to use btree on disk but these are too large. for empty db creation, it uses 1mb. Can you create one that uses less than 100b with yours? Just looking for a disk backed version. Thx in advance.

        "github.com/timtadh/fs2/bptree"
        "github.com/timtadh/fs2/fmap"
    
    opened by hiqsociety 8
  • Generics

    Generics

    I saw you have a few commits planning to use generics. Do you have a work in progress for this? I would be willing to try it out in anacrolix/torrent, where I'm dealing with a lot of heap allocation overhead due to stuffing things into google/btree's Item interface.

    opened by anacrolix 8
  • Delete during Ascend in thread-safe tree

    Delete during Ascend in thread-safe tree

    Thanks for publishing this library!

    I have a case where I want to delete some items in a range, which would be something like

    bt.Ascend(start, func(item interface{}) {
      if filter(item) {
        bt.Delete(item)
      }
    })
    

    But since sync.Mutex isn't re-entrant, it deadlocks.

    • Is it safe to do delete inside an Ascend with the non-safe version (provided outside locking)?
    • If so, could Ascend unlock while the callback is running?

    If not, would I have to do something like

    delitem := start
    for {
      bt.Ascend(delitem, func(item interface{}) {
        if filter(item) {
          delitem = item
          return false
        }
      })
      if isEnd(delitem) {
        break
      }
      bt.Delete(delitem)
    }
    

    In that case, it seems like there should be an AscendHint to complement DeleteHint.

    opened by tommie 5
  • Added context getter and setter

    Added context getter and setter

    Allows changing the context of a tree.

    In my scenario the context is the parent data structure that holds the tree. If I clone that data structure and the tree using Clone I need to update the context to point to the new data structure to prevent leaking memory.

    Might be useful to others as well.

    opened by 256dpi 3
  • fix a typo and drop one maybe useless else, outdent its block

    fix a typo and drop one maybe useless else, outdent its block

    1. fix the typo of "contruction" to "construction" in line 66
    2. remove the else {} in line 672, mv the code outdent of this block
    opened by maxwell92 1
  • fix t.Fatal calls with formatting directives

    fix t.Fatal calls with formatting directives

    In Go 1.12, running go test exits with the following errors:

    ./btree_test.go:707:3: Fatal call has possible formatting directive %v
    ./btree_test.go:718:3: Fatal call has possible formatting directive %v
    

    This PR fixes those issues.

    opened by alexedwards 1
  •  Add poweron architecture ppc64le to travis build

    Add poweron architecture ppc64le to travis build

    This is part of the Ubuntu distribution for ppc64le. This helps us simplify testing later when distributions are re-building and re-releasing,We typically build applications for customers and ISVs, and while we don't use this package directly, we do count on all of the packages in debian/ubuntu to build other packages. So we more likely have this as a second or third level dependency and couldn't tell you explicitly which features we use or our usage model,For more info tag @gerrith3.

    opened by asellappen 1
  • Add some more documentation to internal functions

    Add some more documentation to internal functions

    Added some documentation that I found helpful while trying to understand & use the code!

    opened by ValarDragon 1
  • Fixed typo in docstring

    Fixed typo in docstring

    opened by tidwall 0
  • The Map[K, V].find() API design discussion

    The Map[K, V].find() API design discussion

    can you export

    func (tr *Map[K, V]) find(n *mapNode[K, V], key K) (index int, found bool)
    

    to public domain, like:

    func (tr *Map[K, V]) Find(n *mapNode[K, V], key K) (index int, found bool)
    

    for method to use:

    func (tr *Map[K, V]) GetAt(index int) (K, V, bool)
    
    opened by sarrow104 2
  • ADMIN

    ADMIN

    ADMIN

    #- [ ] ____New on here```

    opened by cristy-davis 0
  • What is the purpose of path hints?

    What is the purpose of path hints?

    I am trying to understand how exactly I can use path hint methods. Could you please give some examples in the Readme. That would be helpful.

    opened by sandeeprapido 5
Owner
Josh Baker
Josh Baker
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 17 Dec 28, 2021
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Yasushi Saito 19 Jan 2, 2020
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 170 Jan 9, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

HashiCorp 779 Jan 21, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 189 Jan 2, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 2 Sep 13, 2021
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 18 Aug 26, 2021
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Michael Lore 26 Dec 8, 2021
an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Daniel Connelly 499 Jan 17, 2022
Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Josh Baker 93 Oct 8, 2021
Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Arun Shaji 3 Oct 6, 2021
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Arthur Abeilice 0 Oct 14, 2021
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

web_developer 1 Oct 9, 2021
Segment tree for bytes in Go

bsegtree Segment tree for bytes in Go Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges. For

Temple3x 2 Dec 20, 2021
A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Victor Zeddys 1 Nov 1, 2021
A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

null 0 Nov 24, 2021
publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Lutz Behnke 0 Dec 20, 2021
Mmpxmas-go - ModMyPi Programmable Christmas Tree examples written in Go with go-rpio

ModMyPi Programmable Christmas Tree examples in Go This small program contains examples similar to the examples provided by ModMyPi for interacting wi

Tyler Darnell 0 Jan 4, 2022
watch for file changes (matching a suffix whitelist) in a directory tree and run a command when they change

watchspawn what is it? Watches for file creates and writes in and below the current directory and when any of them (matching a suffix list) change, ru

John Slee 0 Jan 16, 2022