Re: Persistent Binary Search Trees

[Mikkel Kamstrup Erlandsen <mikkel kamstrup gmail com>]

2009/10/5 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].

Aha - now I get it :-) Thanks for clearing it up. This sounds mighty
interesting; now I just need to figure out what cool things I can use
it for :-)

-- 
Cheers,
Mikkel