README.md
1BTree implementation for Go
2===========================
3
4![Travis CI Build Status](https://api.travis-ci.org/tidwall/btree.svg?branch=master)
5[![GoDoc](https://godoc.org/github.com/tidwall/btree?status.svg)](https://godoc.org/github.com/tidwall/btree)
6
7This package provides an in-memory B-Tree implementation for Go, useful as
8an ordered, mutable data structure.
9
10This is a fork of the wonderful [google/btree](https://github.com/google/btree) package. It's has all the same great features and adds a few more.
11
12- Descend* functions for iterating backwards.
13- Iteration performance boost.
14- User defined context.
15
16User defined context
17--------------------
18This is a great new feature that allows for entering the same item into multiple B-trees, and each B-tree have a different ordering formula.
19
20For example:
21
22```go
23package main
24
25import (
26 "fmt"
27
28 "github.com/tidwall/btree"
29)
30
31type Item struct {
32 Key, Val string
33}
34
35func (i1 *Item) Less(item btree.Item, ctx interface{}) bool {
36 i2 := item.(*Item)
37 switch tag := ctx.(type) {
38 case string:
39 if tag == "vals" {
40 if i1.Val < i2.Val {
41 return true
42 } else if i1.Val > i2.Val {
43 return false
44 }
45 // Both vals are equal so we should fall though
46 // and let the key comparison take over.
47 }
48 }
49 return i1.Key < i2.Key
50}
51
52func main() {
53
54 // Create a tree for keys and a tree for values.
55 // The "keys" tree will be sorted on the Keys field.
56 // The "values" tree will be sorted on the Values field.
57 keys := btree.New(16, "keys")
58 vals := btree.New(16, "vals")
59
60 // Create some items.
61 users := []*Item{
62 &Item{Key: "user:1", Val: "Jane"},
63 &Item{Key: "user:2", Val: "Andy"},
64 &Item{Key: "user:3", Val: "Steve"},
65 &Item{Key: "user:4", Val: "Andrea"},
66 &Item{Key: "user:5", Val: "Janet"},
67 &Item{Key: "user:6", Val: "Andy"},
68 }
69
70 // Insert each user into both trees
71 for _, user := range users {
72 keys.ReplaceOrInsert(user)
73 vals.ReplaceOrInsert(user)
74 }
75
76 // Iterate over each user in the key tree
77 keys.Ascend(func(item btree.Item) bool {
78 kvi := item.(*Item)
79 fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
80 return true
81 })
82
83 fmt.Printf("\n")
84 // Iterate over each user in the val tree
85 vals.Ascend(func(item btree.Item) bool {
86 kvi := item.(*Item)
87 fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
88 return true
89 })
90}
91
92// Should see the results
93/*
94user:1 Jane
95user:2 Andy
96user:3 Steve
97user:4 Andrea
98user:5 Janet
99user:6 Andy
100
101user:4 Andrea
102user:2 Andy
103user:6 Andy
104user:1 Jane
105user:3 Steve
106*/
107```
108