Xen project Mailing List

Since it's for a project, take all of this with a pinch of salt: (random thoughts follow)

A simple b-tree on disk would probably be much like an in-heap b-tree, except the nodes would be naturally wider and you would also need to track and reclaim free blocks (which the GC would normally do for you). You could do something really minimal at first (eg allocate by pointer bump, no deallocation) and then perhaps do a big stop-the-world thing (like fsck) and, if there's enough time, try something more incremental. Perhaps the "root" block would reference the tree root+a free list? You could also analyse or profile the costs in terms of disk seeks?

If it were me, I'd be happier in a project implementing a relatively pure algorithm than binding together much bigger things (like baardskeerder) which were designed for something much bigger (eg clustering?) and where impedance mismatches are more likely.

On Wed, 11 Nov 2015, 09:58ÂRupert Horlick <rh572@xxxxxxxxx> wrote:

Hmm, it seems like that is built on top of a few packages that don't exist any more to interface between Baardskeerder and Mirage.

Do you think it's worth doing a simple B-Tree implementation myself, or would it be better to try and build a new interface module for Mirage and Baardskeerder?

A B-Tree implementation would certainly be good for the project write-up, but let me know what you think.

Rupert

On Tue, Nov 10, 2015 at 8:58 PM Richard Mortier <richard.mortier@xxxxxxxxxxxx> wrote:
On 10 November 2015 at 16:49, Rupert Horlick <rh572@xxxxxxxxx> wrote:
> I'm implementing this for a Part II project, so I've decided to go ahead and
> implement my own simple FS for BLOCK, rather than using IRMIN.
>
> However, I'm coming across the difficulties that Dave mentioned,

Simple and in-memory is (surely!) still good to start with though!

> so I'm
> reading up on B-trees as we speak. I may well end up writing a simple B-tree
> library, so I'll let know you if I do.

There may be most of such a thing already I think -- Chris Greenhalgh
at Nottingham lashed something up a while ago based on Baardskeerder,
see https://github.com/cgreenhalgh/ocaml-btree (though based on a much
much earlier version of Mirage :)

--
Richard Mortier
richard.mortier@xxxxxxxxxxxx

Re: [MirageOS-devel] Irmin on BLOCK