search

google / btree

BTree provides a simple, ordered, in-memory data structure for Go programs.
Apache License 2.0
3.9k stars 414 forks source link

O(1) Clone of BTree. #16

Closed gconnell closed 7 years ago

gconnell commented 7 years ago

This change allows a BTree user to quickly clone the tree, using copy-on-write logic to modify shared state. Both trees continue to reference the original tree's nodes for reading, thus the clone is O(1). Writes to either the original or new tree after the clone copy nodes instead of modifying them. These operations remain O(logn), but slow down slightly due to the additional mallocs/copies necessitated by the copy-on-write logic.

Uses a copyOnWriteContext pointer at the tree and node level to determine which nodes are able to be modified and which are read-only and must be copied before modification.

To simplify things, freelists have been made safe for concurrent access. With copy-on-write, keeping track of which freelists are being used by which btrees is very difficult. Consider the case:

t1 := New()
t2 := t1.Clone()

What freelist should t1 and t2 have? Can you write to both t1 and t2 at once? With this, the answers are "they're sharing one", and "yes".

tidwall commented 7 years ago

@gconnell Just gotta say that this feature is an excellent addition!