You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
TLDR: this has the upside that it is possible to quickly query 3d ranges, as well as (this is the point where it is superior to the radix tree) querying 3d ranges sorted by any of the 3 primary dimensions path, time and subspace.
The downside compared to the radix tree is that insertion requires roughly O(log n) path comparisons, and path comparisons itself are not constant time and can be expensive. Also, the paths are stored as a whole, unlike in a radix tree where they are prefix compressed. Prefix deletion will need a naive implementation where you just iterate and delete over everything below a prefix.
My current approach is to implement the tree query ops for a generic X, Y, Z (currently using u64 for testing), then implement insert and delete. Operations are tested using proptest property based testing.
Doesn't this have to happen on every insert? I.e. prefix deletion is exactly the same as inserting a tombstone at a prefix?
Not sure what you mean with the tombstone, but yes, every insert will mean a query for possibly affected child nodes, iterating over them, and deleting those that have to go.
Twothree reasons for why this might not be quite as bad as it sounds:
in many (most?) cases the node you insert will be a leaf, so the query will return zero affected elements
for non-leaf queries initially will implement this as just iterate then delete, but longer term this can be done with a fn similar to retain that just filters the tree efficiently instead of deleting one by one
when writing to a DB, it often almost does not matter that much how much you change, just how many times you have to call sync. Unless it is a really huge change. So maybe this won't be that bad.
Another thought to keep in mind about naive prefix deletion vs more efficient radix-tree-based implementations: notifying subscribers about deletions might turn this into an O(n) (for n deleted entries) anyways. O-notation might be less important here than actual running times, but still, could be helpful to keep this in mind from the start.
After a lot of discussion with Aljoscha last week I have decided to implement the willow store roughly as proposed in https://github.com/AljoschaMeyer/kv_3d_storage
TLDR: this has the upside that it is possible to quickly query 3d ranges, as well as (this is the point where it is superior to the radix tree) querying 3d ranges sorted by any of the 3 primary dimensions path, time and subspace.
The downside compared to the radix tree is that insertion requires roughly O(log n) path comparisons, and path comparisons itself are not constant time and can be expensive. Also, the paths are stored as a whole, unlike in a radix tree where they are prefix compressed. Prefix deletion will need a naive implementation where you just iterate and delete over everything below a prefix.
My current approach is to implement the tree query ops for a generic
X
,Y
,Z
(currently using u64 for testing), then implement insert and delete. Operations are tested using proptest property based testing.I am currently working on this in a separate repository https://github.com/n0-computer/willow-store/tree/3d
Operations
Plumbing
Docs
The text was updated successfully, but these errors were encountered: