Description

Deletion process produces unexpected result based on current implementation.

Steps to reproduce the issue: 1 Prepare the following test case in btree_test.go

package btree

import (
    "flag"
    "fmt"
    "testing"
    "os"
)

var btreeDegree = flag.Int("degree", 3, "B-Tree degree")

func TestForBTreeDeletion(t *testing.T) {
    tree := New(*btreeDegree)
    fmt.Println(tree)

    for i := 0; i < 21; i++ {
        if x := tree.ReplaceOrInsert(Int(i)); x != nil {
            t.Fatal("insert found item", i)
        }
    }
    fmt.Println("Before deletion")
    tree.Print(os.Stdout)

    for i := 0; i < 3; i++ {
        if x := tree.Delete(Int(i)); x == nil {
            t.Fatal("insert didn't find item", i)
        }
        fmt.Println("After deleting ", i)
        tree.Print(os.Stdout)
    }

}

2 Add a tree.Print method for debugging purpose in btree.go

// Print is for debugging purpose on CLI
func (t *BTree) Print(w io.Writer) {
    t.root.print(w, 0)
}

3 Run the test suite

go test -v

Describe the results you received:

Before deletion  *[<===== This is the original tree with degree of 3 after inserting 0 to 20]*
NODE:[8]
  NODE:[2 5]
    NODE:[0 1]
    NODE:[3 4]
    NODE:[6 7]
  NODE:[11 14 17]
    NODE:[9 10]
    NODE:[12 13]
    NODE:[15 16]
    NODE:[18 19 20]

After deleting  0 *[<====== After deleting 0, `NODE[0 1]` underflows and causes redistribution ]*
NODE:[11]
  NODE:[5 8]
    NODE:[1 2 3 4]     **[<====== This NODE has enough items so that deleting 1 shouldn't cause an underflow]**
    NODE:[6 7]
    NODE:[9 10]
  NODE:[14 17]
    NODE:[12 13]
    NODE:[15 16]
    NODE:[18 19 20]

After deleting  1  [<===== WRONG: The underlying B-tree is redistributed]
NODE:[5 8 11 14 17]
  NODE:[2 3 4]
  NODE:[6 7]
  NODE:[9 10]
  NODE:[12 13]
  NODE:[15 16]
  NODE:[18 19 20]

After deleting  2
NODE:[5 8 11 14 17]
  NODE:[3 4]
  NODE:[6 7]
  NODE:[9 10]
  NODE:[12 13]
  NODE:[15 16]
  NODE:[18 19 20]

Describe the results you expected:

See my comment inline in the above section.

To double check the behavior, try to run a visualized b-tree insertion from this website. 1 Selecting max degree as 6 2 Manually insert 0 to 20 (inclusively). [Same underlying tree as above] 3 Manually delete 0 [Correct: Underflow causes redistribution] 4 Delete 1 [Correct: No redistribution. Whereas in the issue reported, the tree is redistributed]

Additional information you deem important (e.g. issue happens only occasionally):

Output of go version: go version go1.6.2 linux/amd64

Additional environment details (AWS, VirtualBox, physical, etc.):

Added DescendRange, DescendLessOrEqual, DescendGreaterThan, and Descend functions. These are modeled after the existing Ascend.. methods.

Also modified the iteration function to remove the from() and to() in favor of adding a start and stop parameters instead. There is a modest performance ~10% boost by avoiding superfluous function calls.

before:

BenchmarkAscend-8          10000        216529 ns/op
BenchmarkAscendRange-8      3000        433896 ns/op

after:

BenchmarkAscend-8          10000        196143 ns/op
BenchmarkAscendRange-8      3000        396469 ns/op

The benchmark code is not included in the source, but I did create a gist at iteration_test.go

I hope you find this update useful and thanks a ton for such a fantastic library!

I am serializing snapshots of the btree to be restored later. For saving I only need a read lock, for restoring I obtain a write lock on the tree. I was able to amortize all the costs of serialization and cheapen the restore process with a generous free list capacity. For larger restores the process of removing all the items from an existing tree is taxing. You have to visit N nodes to store in a temporary list (I cached this and reset[0:0] each restore), then iterate the temporary list to make N calls to delete.

I tried some other possibility such as creating an entirely new tree and replace the existing one, but without first deleting all the items in the tree my FreeList is empty so the allocations kill me instead. I could probably work around this with rotating between two trees and deleting in the background, but this would be much simpler if accepted. It provides around 2.5-3x speedup for removing all items from a btree and lowers my latency below the downstream tick rate.

Small note: I included "Inserts" in the benchmarks because I was running into that issue that pops up sometimes with the benchmark timers where it runs forever on the Reset() test otherwise and I nothing I tried fixed it.

BenchmarkDeleteAll-24 100 11680090 ns/op 523832 B/op 709 allocs/op BenchmarkReset-24 300 6648212 ns/op 367997 B/op 723 allocs/op

This patch provides around a 3 time speed up for my restore process

Added a method that returns the ith item in the btree. In order to do this, each node has an idea of the number of items in the tree of which it is the root. I've updated all relevant insert/delete functions to maintain each node's length. The performance is unchanged.

Looking forward to suggestions that can improve this feature. Cheers.

With support for generics, we can replace interfaces with generic types. The use of generics avoids variables escaping to heap when calling the B-tree functions yielding 20-30% improvement.

Below are some comparisons between benchmarks (taken from original repository) done with benchstat:

name                                 old time/op    new time/op    delta
Insert-8                                121ns ± 1%      89ns ± 1%   -27.04%  (p=0.008 n=5+5)
Seek-8                                  115ns ± 1%      78ns ± 0%   -31.56%  (p=0.008 n=5+5)
DeleteInsert-8                          248ns ± 0%     185ns ± 1%   -25.51%  (p=0.008 n=5+5)
DeleteInsertCloneEachTime-8            1.10µs ± 5%    0.61µs ± 1%   -44.45%  (p=0.008 n=5+5)
Delete-8                                138ns ± 1%     101ns ± 1%   -26.62%  (p=0.008 n=5+5)
Get-8                                   102ns ± 1%      71ns ± 0%   -30.46%  (p=0.008 n=5+5)
Ascend-8                               40.2µs ± 1%    31.7µs ± 0%   -21.18%  (p=0.008 n=5+5)
Descend-8                              39.3µs ± 1%    30.7µs ± 1%   -21.91%  (p=0.008 n=5+5)
AscendRange-8                          72.3µs ± 1%    57.6µs ± 1%   -20.39%  (p=0.008 n=5+5)
DescendRange-8                         92.9µs ± 1%    77.6µs ± 1%   -16.45%  (p=0.008 n=5+5)

name                                 old alloc/op   new alloc/op   delta
Insert-8                                35.6B ± 4%     18.4B ± 3%   -48.31%  (p=0.008 n=5+5)
Seek-8                                  7.00B ± 0%     0.00B       -100.00%  (p=0.008 n=5+5)
DeleteInsert-8                          0.00B          0.00B           ~     (all equal)
DeleteInsertCloneEachTime-8            2.98kB ± 5%    1.91kB ± 1%   -36.16%  (p=0.008 n=5+5)
Delete-8                                0.00B          0.00B           ~     (all equal)
Get-8                                   0.00B          0.00B           ~     (all equal)
Ascend-8                                0.00B          0.00B           ~     (all equal)
Descend-8                               0.00B          0.00B           ~     (all equal)
AscendRange-8                           0.00B          0.00B           ~     (all equal)
DescendRange-8                          0.00B          0.00B           ~     (all equal)

name                                 old allocs/op  new allocs/op  delta
Insert-8                                 0.00           0.00           ~     (all equal)
Seek-8                                   0.00           0.00           ~     (all equal)
DeleteInsert-8                           0.00           0.00           ~     (all equal)
DeleteInsertCloneEachTime-8              11.0 ± 0%      11.0 ± 0%      ~     (all equal)
Delete-8                                 0.00           0.00           ~     (all equal)
Get-8                                    0.00           0.00           ~     (all equal)
Ascend-8                                 0.00           0.00           ~     (all equal)
Descend-8                                0.00           0.00           ~     (all equal)
AscendRange-8                            0.00           0.00           ~     (all equal)
DescendRange-8                           0.00           0.00           ~     (all equal)

In case of plain Insert Benchmark, the results are even better:

name      old time/op    new time/op    delta
Insert-8     200ns ± 2%     137ns ± 1%   -31.20%  (p=0.008 n=5+5)

name      old alloc/op   new alloc/op   delta
Insert-8     60.0B ± 0%     27.0B ± 0%   -55.00%  (p=0.008 n=5+5)

name      old allocs/op  new allocs/op  delta
Insert-8      1.00 ± 0%      0.00       -100.00%  (p=0.008 n=5+5)

func BenchmarkInsert(b *testing.B) {
    b.StopTimer()
    tr := btree.New(32)
    b.StartTimer()
    for i := 0; i < b.N; i++ {
        tr.ReplaceOrInsert(btree.Int(i))
    }
}

Unfortunately the functions that return nil do not work ex. func (t *BTree) Delete(item Item) Item. We can't simply return zero value for generic type, because it's still a valid value, so I decided to change the API, so that:

func (t *BTree[T]) Delete(item T) (T, bool) { ... }

we also return bool which indicates whether anything was really deleted. Of course, we can implement B-tree on pointers to generic types, but it harms performance in many cases (like having B-tree for numeric types).

Changes of API destroy backward compatibility, but because of reasons mentioned above, I believe that this approach is justified.

Here is link to forked repository with generic B-tree: https://github.com/Michal-Leszczynski/btree

How do you suggest we further proceed with this effort.

Hi, In our scenario, we frequently use the iterate, and the Less compare is expenses when key is large. This PR mainly improve the iterate location. uses binary search to quickly locates the start item. before:

BenchmarkSeek-4          3000000               452 ns/op
BenchmarkSeek-4          3000000               513 ns/op
BenchmarkSeek-4          3000000               454 ns/op
BenchmarkSeek-4          3000000               450 ns/op

after:

BenchmarkSeek-4         10000000               225 ns/op
BenchmarkSeek-4         10000000               222 ns/op
BenchmarkSeek-4         10000000               223 ns/op
BenchmarkSeek-4         10000000               224 ns/op

This fixes an issue where the Go garbage collector does not release some items which have been removed from the BTree because a reference to the item still exists in the items and children slices.

This change allows multiple btrees to share the same node freelist rather than each btree having its own node freelist.

We are developing an application that uses 32 GB of memory. Because of the amount of memory that we use we want the memory footprint of our application to change very little. Therefore, we make special effort to pre-allocate what we need at application startup and use free lists to reuse memory rather than allocating memory as we go and relying on the garbage collector to free memory.

I was delighted to discover that this btree package uses freelists to provide some relief for the GC. However, our application consists of two btrees. As our application runs, we are constantly moving thousands of btree items at a time between the two btrees. At the beginning, one of the btrees has all the items while the second btree has none. Sometime later, the second btree may have all the items while the first btree has none. Sometimes, the items may be split up evenly between the two btrees. The sum of the sizes of the 2 btrees always remains constant.

If each btree has its own free list, we would still have to allocate large amounts of space off the heap for the second btree as it acquires items for the first time. Moreover, the current freelists are limited in size to 32 btree nodes which is too small for our application.

By having our two btrees share the same freelist we put even less strain on the GC. As the first btree gives up items, it places nodes on the common freelist. The second btree can reuse the old nodes from the first btree rather than allocating new ones which means fewer heap allocations and less strain on the GC.

We understand that a separate freelist for each btree suffices for most applications, but in our particular case, we benefit from having our two btrees share the same freelist which is what this pull request allows.

Thank you in advance for considering this pull request.

Created a few more iterators to be used by the public interface for performance improvements. I did this in two commits, the second one changes the private interface signatures from funcs (technically same signature as ItemIterator) to Item, but since the public interface never actually exposes funcs for ascending I figured this would be okay.

Before:

~/.../github.com/cstockton/gbtree$ go test -test.bench=.*
1
PASS
BenchmarkInsert  3000000           411 ns/op
BenchmarkDelete  3000000           424 ns/op
BenchmarkGet     5000000           363 ns/op
BenchmarkIterateAscend      3000        474049 ns/op
BenchmarkIterateAscendLessThan      5000        274409 ns/op
BenchmarkIterateAscendGreaterOrEqual        5000        277208 ns/op
BenchmarkIterateAscendRange    10000        216873 ns/op
ok      github.com/cstockton/gbtree 16.429s

After:

~/.../github.com/cstockton/btree$ go test -test.bench=.*
1
PASS
BenchmarkInsert  3000000           408 ns/op
BenchmarkDelete  3000000           422 ns/op
BenchmarkGet     5000000           360 ns/op
BenchmarkIterateAscend      3000        431754 ns/op
BenchmarkIterateAscendLessThan      5000        257723 ns/op
BenchmarkIterateAscendGreaterOrEqual        5000        257560 ns/op
BenchmarkIterateAscendRange    10000        205764 ns/op
ok      github.com/cstockton/btree  15.984s

With the introduction of generics in Go 1.18, we have the opportunity to use them for our btrees. However, we want to make sure that our API remains compatible with past uses. So, we introduce a new BTreeG which is a generic API. We then utilize it to recreate the original BTree of Item interfaces.

Go compilers <1.18 will compile btree.go, containing just the original BTree of Items. Go compilers >=1.18 instead compile btree_generic.go which creates the BTreeG generic and uses it to make a BTree of Items with the same API as that exposed in btree.go.

One major difference between the APIs of BTree and BTreeG is that, for BTree, we could return a nil Item to connote "nothing was found". For generics, users may often want to store the zero value, so we can't treat the zero value as "missing". For that reason, you'll see these differences in APIs:

  func (t *Btree)     Get(item Item) Item      { ... }
  func (t *BtreeG[T]) Get(item T)    (T, bool) { ... }

Note that we now return a second boolean return value, which is true if the value was found and false otherwise.

Using the generic for base types like int greatly speeds up processing, since it removes the need for the Item interface to be created/malloc'd, and it allows more contiguous storage of values within the BTree's nodes themselves.

As expected, all G (generic) ops are notably faster than their associated Int Item ops, because of the removal of interface overhead. Untested here, but they should also be far less memory-fragmented, since values are stored within the node item arrays rather than pointed to by interfaces within those arrays.

BenchmarkInsertG-4 3014830 355.2 ns/op BenchmarkInsert-4 2296561 639.9 ns/op

BenchmarkSeekG-4 5478997 218.6 ns/op BenchmarkSeek-4 2880756 396.0 ns/op

BenchmarkDeleteInsertG-4 1720306 653.0 ns/op BenchmarkDeleteInsert-4 1304244 1131 ns/op

BenchmarkDeleteInsertCloneOnceG-4 1834026 647.3 ns/op BenchmarkDeleteInsertCloneOnce-4 1293346 932.3 ns/op

BenchmarkDeleteInsertCloneEachTimeG-4 545394 2878 ns/op BenchmarkDeleteInsertCloneEachTime-4 353428 4173 ns/op

BenchmarkDeleteG-4 3223182 366.9 ns/op BenchmarkDelete-4 1979107 600.4 ns/op

BenchmarkGetG-4 4265853 293.2 ns/op BenchmarkGet-4 3091616 431.8 ns/op

BenchmarkGetCloneEachTimeG-4 1990131 693.3 ns/op BenchmarkGetCloneEachTime-4 1705196 610.0 ns/op

BenchmarkAscendG-4 14222 83445 ns/op BenchmarkAscend-4 12345 94486 ns/op

BenchmarkDescendG-4 14335 80779 ns/op BenchmarkDescend-4 11686 98627 ns/op

BenchmarkAscendRangeG-4 8803 134915 ns/op BenchmarkAscendRange-4 5586 209962 ns/op

BenchmarkDescendRangeG-4 6590 182179 ns/op BenchmarkDescendRange-4 3591 323628 ns/op

BenchmarkAscendGreaterOrEqualG-4 12984 92049 ns/op BenchmarkAscendGreaterOrEqual-4 9915 121264 ns/op

BenchmarkDescendLessOrEqualG-4 7876 152083 ns/op BenchmarkDescendLessOrEqual-4 4945 231001 ns/op

BenchmarkDeleteAndRestoreG/CopyBigFreeList-4 100 10167381 ns/op 75390 B/op 15 allocs/op BenchmarkDeleteAndRestore/CopyBigFreeList-4 73 15137467 ns/op 141924 B/op 19 allocs/op

BenchmarkDeleteAndRestoreG/Copy-4 104 12522643 ns/op 235632 B/op 1195 allocs/op BenchmarkDeleteAndRestore/Copy-4 80 16853292 ns/op 433896 B/op 1151 allocs/op

BenchmarkDeleteAndRestoreG/ClearBigFreelist-4 207 5434805 ns/op 670 B/op 4 allocs/op BenchmarkDeleteAndRestore/ClearBigFreelist-4 147 7954534 ns/op 980 B/op 6 allocs/op

BenchmarkDeleteAndRestoreG/Clear-4 198 6781077 ns/op 148424 B/op 1086 allocs/op BenchmarkDeleteAndRestore/Clear-4 134 8639437 ns/op 268872 B/op 1041 allocs/op

https://github.com/google/btree/blob/be84af90a1f71c9eeac820a4cdacb863122396d6/btree.go#L204

I'm curious if this bounds issue is important? I'm using this implementation as a learning opportunity for Go and ran into this while studying the code.

The check whether the index is less than the length seems like it would prevent an unnecessary copy. But instead, this would result in a bounds error when attempting to set the item.

This isn't an issue per se, but more of a reaching out to the btree maintainer(s) to talk about a another module that might work well with btree since PR #43 is switching btree to use generics.

I have this module at https://github.com/keep94/consume2 documentation at https://pkg.go.dev/github.com/keep94/consume2 that I use primarily to read from databases. The main actor in this module is the Consumer interface that serves a similar purpose as ItemIterator in the btree module. The Consumer interface is used to collect values out of a database query just like the ItemIterator is used to collect values out of a btree. With this consume2 module, one can build more complicated Consumers out of simpler ones ultimately constructing complex pipelines to gather various results while executing the database query just once.

I would like users of the btree module to have the option of leveraging the consume2 module when iterating over a btree.

The following code can be used to convert a Consumer instance into an ItemIterator

func AsItemIterator[T Item[T]](consumer Consumer[T]) ItemIterator[T] {
    return func(value T) bool {
        consumer.Consume(value)
        return consumer.CanConsume()
    }
}

As you can see the Consumer interface has a CanConsume() method and a Consume() method whereas the ItemIterator is a simple function that returns false when consumption is done.

I thought about changing my Consumer interface to have just one method Consume() that returns a bool, like ItemIterator, but I am not sure if that would be better or worse than what I have now. The advantage of having a CanConsume() method is you can test to see if a Consumer can Consume a value without needing to consume a value. That may offer some advantages over just having one Consume() method that returns a bool indicating whether it can accept more values. The disadvantage of having a CanConsume() method is that the Consume() method has to repeat the logic of CanConsume() in case the caller decides to call Consume() without calling CanConsume() first.

So I have three choices:

1. Leave the Consumer interface as it is, and add a method called AsItemIterator() to consume2 that converts a Consumer instance to an ItemIterator.
2. Change the Consumer interface so that it has one method Consume() that returns a bool similar to how ItemIterator works.
3. Replace the Consumer interface with a function type that accepts a T value and returns a bool.

I think option 3 would be kind of confusing since I also have functions that accept a T value and return a bool that act as filters. I am leaning toward option 1 or option 2.

What do you think would be best for the community?

Thank you for your feedback.

when calling DescendRange methods, an iteration is performed.

All items between [lessOrEqual, greaterThan ) are iterated.

Suppose there're n items in the range, I though Less function is called log(n) times.

However, Less is called more than n times as a matter of

if stop != nil && !n.items[i].Less(stop) {
				return hit, false
			}

Why make comparisons this way? I though if parent node can decide all its children are in the range, most Less(stop) call can be optimized out.

Are there anything wrong with this idea?

I'm using btree to provide an in-memory key-value store for use as a non-persistent substitute for other key-value databases in a cacheing application. The interface that I need to implement using this package requires that I provide an iterator which exposes Next() and Prev() methods.

I have done this using the AscendGreaterOrEqual and DescendLessOrEqual methods as follows: I store a pointer to the current item, and use it as a reference to ascend or descend from, when Next() or Prev() are called, respectively.

While, I believe that internally, iteration within the provided method calls is O(1), in my case, I believe that the lookup of the current item is always O(logN). Since there is not another obvious, O(1) way (to me at least) to restart iteration from a given Item, and move forward or backward one position in the manner I need, and which is common in most key-value store interfaces, I was wondering if the authors thought it might be useful to expose another way to control iteration in a step-by-step manner - O(1) - which keeps track of the current item.

Hey there Google Team! Are there any plans to support the BinaryMarshaler interface? This would be super useful if someone want's to store B-Tree's to disk.

My case: I have always two clones, one for updating and the other for read traversal, every time a "transaction" is done I clone again the tree to force the next update to copy the nodes.

The problem with cow: even for this case it may occur that the reader traverses a subtree that's sill being modified (i.e. and incomplete). The cause is that mutableFor() changes t.root immediately and the changes are applied to the new root. The same happens for children derived from mutableChildren() that changes the also n.children[i].

The solution is to delay the change to the original pointer (root or children) until all changes in the subtree are finished.

I prepared a first patch wit the idea, only for t.root: https://github.com/google/btree/compare/master...gallir:cow

If it's correct and you agree I can prepare a patch for children and items if needed.