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 <[email protected]> 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 < > [email protected]> wrote: > >> On 10 November 2015 at 16:49, Rupert Horlick <[email protected]> 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 >> [email protected] >> >
_______________________________________________ MirageOS-devel mailing list [email protected] http://lists.xenproject.org/cgi-bin/mailman/listinfo/mirageos-devel
