[elephant-devel] Lisp Btrees: design considerations

Robert L. Read read at robertlread.net
Wed May 14 14:02:05 UTC 2008


On Wed, 2008-05-14 at 09:40 -0400, Ian Eslick wrote:
> If the BTree node binary data is stored in a lisp octet array, and
> we  
> don't want to deserialize to compare keys, then we need to write the  
> procedure that you can find in libberkeley-db.c in the src/db-bdb  
> file.  It performs a content-sensitive comparison on a byte-by-byte  
> basis.  This has huge benefits of allowing us to do key comparisons  
> 'in-place' without creating lisp objects.  We pass this C function
> to  
> BDB which uses it to compare keys and values directly in the binary  
> file pages. 

I understand the value of this, but is it not possible to write the
comparator on serialized values in LISP?  This would then be passed down
to the lowest level IO operation, which is still in LISP.

In general I'm imagining a system that does just that as its "query
language", --- take a very lisp-like specification of a predicate and
pass it down to the lowest level I/O operation, or as low as you can
get, and apply it there.  This allows us to retain the elegant "mapcar"
and "map-reduce" strategies as basic querying mechanisms.

If we make a modular serializer, that serializes on the basis of data
type, then it is indeed a challenge for the implementor to implement a
function that performs comparisons on the serialized representation of
that type...but a very worthwhile challenge, I think.





More information about the elephant-devel mailing list