Re: Persistent Binary Search Trees

[Dana Jansens <dana cg scs carleton ca>]

2009/10/5 Mikkel Kamstrup Erlandsen <mikkel kamstrup gmail com>:
> Don't let that hold you back. As far as I can imagine I don't have any
> use case ready, but that is probably because I've never had a
> persistent BST at hand :-)
>
> If I where you I'd probably just develop on out-of-tree library for
> the datastructure, keeping the API aligned with glib, and making an
> effort to make it easy to merge to glib should the desire arise.
>
> Then do some lobbying for the lib in some areas where you can see use
> cases. If you can get tracktion from some real world apps, the chances
> of getting into glib are higher. As an alternative you could develop
> the datastructure for the collections library used by Vala; libgee.
> They have a much more rich collections API and are also still less
> frozen API-wise.

Thanks for your suggestions.

> I also have a few questions:
> What is the relation to the copy-on-write B-trees like used in Btrfs?
> Can I version sub-trees or is it always the entire tree?

I'm not very familiar with the copy-on-write trees in Btrfs, but from
reading about it briefly, and from general intuition, it doesn't sound
quite like the same idea, though with the same effect. A simpler
implementation of a persistent BST can simply copy the path from the
root down along any changes for each insert/delete.  However this
requires a lot more space than the implementation I am suggesting.
Instead, each node in the tree can keep a history of pointers to its
children, which are changed (and remembered) over time.  Only one copy
of any node in the tree ever exists, and only O(1) pointers are
changed to perform an insert/delete.

The difference to the Btrfs trees is that, in that case, the data is
changing within a node, so you need to copy the old data.  In a
persistent BST as proposed, the data within a node is not what is
preserved, but the structure of the tree itself, as the tree evolves
with time.  The persistence mechanism is described in this paper [1].

Hope that answers your question.

Cheers,
Dana

[1] J. R. Driscol, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making
data structures persistent. Journal of Computer and System Sciences,
38(1), pp 86–124, February 1989.