github.com/tidwall/btree

Merge pull request #50 from canibeanartisttoo/arjun/opt_alloc_delete_…

This commit adds the two new methods DeleteRange(min, max) and
DeleteAscend(min, iter) for efficiently deleting a sub-range and performing an
iteration-based delete on items.

Prior to this commit the two options for deleting data were Delete(key) and
DeleteHint(key, hint).

These worked fine in most cases where a one-off deletion is all that's needed.

But for batch or filter-like deletions, these are suboptimal because they
require knowing the keys beforehand. Meaning the user will likely need to call
something like the Ascend(min, iter) iterator to grab the keys and store them
into temporary list before looping over the list to perform the actual deletes.

The new DeleteAscend(min, iter) function, like the traditional Ascend(min, iter)
function, accepts an iterator callback and ranges over the items starting at
min. The user controls the iterator by returning an Action type. The callback
is called for each item until it reaches the end of the tree or until the user
returns Stop. If the user returns Delete, the item is deleted. The value Keep
can be returns to keep the existing item and continue iterating.

This implementation of DeleteAscend is optimized to avoid having to continually
traverse the tree for each item. Rather, it works to keep the cursor at the
leaf level as much as possible, moving up and down tree in a non-recursive loop.

The new DeleteRange(min, max) function accepts a min (inclusive) and max
(exclusive) sub-range. All items in the range are deleted and returned to the
user. This operation is very fast because in many cases branch nodes can
be completely removed without visiting their internal children. This allows for
large spans of branch node removals to feel near instant. Since this B-tree
library adopts the properties of a Counted B-tree, the number of items in the
subtrees are know at the branch node level, allowing for easy maintenance
of parent node counts.

There's also an optional param for DeleteRange that, when provided, allows for
ignoring returning the deleted items, further increasing performance.

Benchmarks

Some basic benchmarks are included in the btreeg_test.go file.

Run 'go test -run TestContiguousDelete'

It uses the Delete, DeleteHint, DeleteAscend, and DeleteRange strategies.
Also included is a DeleteRange that does not return the deleted results.

What each bench does is create a randomly sized B-tree, up to 200k items.

Then it performs a batch delete of a random window size up to 50% the number
of items in the tree. It then performs multiple runs until the total number of
deleted items is greater than 200k. Each run builds a new tree. Only the
delete operations are calculated in the duration.

These are the results on a MacBook M1.

Delete deleted 204,536 items in 0.0242 secs, 118 ns/item, 8,458,572/s
DeleteHint deleted 204,605 items in 0.0184 secs, 90 ns/item, 11,145,431/s
DeleteAscend deleted 200,598 items in 0.0120 secs, 60 ns/item, 16,771,705/s
DeleteRange deleted 200,591 items in 0.0023 secs, 11 ns/item, 87,355,868/s
DeleteRangeNoRet deleted 200,861 items in 0.0013 secs, 7 ns/item, 150,040,823/s

These new functions allow for using a path hint with iterators,
making it potentially faster when seeking to the first item in the iteration.

Benchmarks:

https://github.com/tidwall/btree-benchmark

About path hints:

https://github.com/tidwall/btree/blob/master/PATH_HINT.md

Usage:

tr.AscendHint(key, iter, &hint)   // iterate items that are >= key, ascending
tr.DescendHint(key, iter, &hint)  // iterate items that are <= key, descending
iter.SeekHint(key, &hint)         // seek to item that is >= key

This commits includes new Mut methods which ensure that values get
correctly copied, if needed, following a btree Copy() operations.

This effictively allows for the BTree Copy method to create an isolated
snapshot that cascades to the interior values. Such as a BTree that has
nested BTrees as values.

Mut methods are only useful when all of the following are true:

• The interior data of the values require changes.
• The value is a pointer type.
• The BTree has been copied using Copy() or IsoCopy().
• The value itself has a Copy() or IsoCopy() method.

Mut methods may modify the tree structure and should have the same
considerations as other mutable operations like Set, Delete, Clear, etc.

New methods include GetMut, ScanMut, AscendMut, DescendMut, ReverseMut,
IterMut, MinMut, MaxMut, etc.