#tree #trie #immutable #persistent

vertree

A persistent trie where each node is typed and versioned

6 releases

0.2.2 Jul 26, 2017
0.2.1 Jun 29, 2017
0.1.2 May 20, 2017
0.1.1 Jan 4, 2017

#739 in Data structures

Download history 54/week @ 2020-02-27 12/week @ 2020-03-05 7/week @ 2020-03-12 24/week @ 2020-03-19 6/week @ 2020-03-26 31/week @ 2020-04-09 19/week @ 2020-04-16 1/week @ 2020-04-30 18/week @ 2020-05-14 12/week @ 2020-05-28 13/week @ 2020-06-04 7/week @ 2020-06-11

57 downloads per month

Apache-2.0

73KB
1.5K SLoC

vertree

Build Status

API Documentation

This is a library providing the "vertree" data structure. This data structure has the following core properties:

  • hierarchical storage (a tree) of data
  • rich data structures at the leaves (not just blobs)
  • linear versioning of all changes to items and subtrees
  • CAS and related operations

The hierarchical structure of vertree is similar to a traditional filesystem. Each inner (non-leaf) node is a "Directory" node, a mapping of UTF-8 strings to child nodes of that Directory. Each leaf node has a specific data type such as Blob, Queue, or Set, with corresponding operations available to modify the data in the node. The sub-items inside Queue and Set nodes are always Blob, so a leaf node itself is not arbitrarily complex in content.

One of the essential features of vertree is that every node has a version. All mutation operations on either a leaf node's content (such as pushing something into a Queue) or on the vertree itself (such as creating or deleting a node) cause the version to be incremented both at the node where the change occurred and at every node above it. This allows a special capability: operations in vertree can be conditional on either individual nodes or arbitrary subtrees, enabling easy optimistic concurrency among users that the vertree's content is exposed to.

Dependencies

~1.2–1.8MB
~37K SLoC