[Metakit] Implementing a search tree in Metakit?

[Jack Diederich]

On Wed, Nov 30, 2005 at 08:51:15PM +0100, Magnus Lie Hetland wrote:
> I'm thinking of using Metakit for implementing a disk-based search
> tree with a B-tree-like node structure. How feasible is this? I can
> live with more than one disk access per node, for example, but not too
> many... I've been thinking of simply using recursive subviews for the
> nodes, and using a subview somewhat like key[value:int] for the key
> (which is, in this case, a vector -- but I might have other similar
> key objects), the idea being to reduce the number of columns (and
> thereby disk accesses) for each key.
> 
> Does this seem like a reasonable approach?
> 
> What if I have a structure like "roots[key[value:I],children[^]]"; if
> I iterate over the keys and read out the ints, would I need a separate
> disk access for each subview? Perhaps hand-encoding a key and using
> key:S would be better?
> 

Why not just use a library that does B-trees?  If you are using python
check out the bsddb module, even if you aren't check out sleepycat.com
(Berkeley DB maintainers).  The library is available in Java and of
course C flavors.

If you want B-trees the easiest thing to do would be to use B-trees...

-jack