[From nobody Wed Dec 29 17:57:51 2004
Date: Thu, 16 Dec 2004 21:30:28 GMT
Message-Id: <200412162130.iBGLUS324758@johns-22209-001.dsvr.co.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: Olly Betts <olly@survex.com>, Richard Boulton <richard@tartarus.org>
From: martin.porter@grapeshot.co.uk (Martin Porter)
Subject: Re: dividing B-trees
Content-Length: 1356
Lines: 42


Well, we have been through this before, here is an email of 15 Sep 2000 to
Richard:

------------------------
Re: Endianness

The issue over truncating keys to right in the index of the B-tree comes
back to me now. If a key at a lower level is trucated, e.g.



            o---->   ... rat, rats, ratting, 
            rattl
            o---->   rattled, rattling ...
            
it separates the two branches for simple lookup purposes, but won't help us
find the nearest key in a consistent way. So if you look for 'rattle' you
take the second pointer and discover that 'rattled' is the first key after
'rattle'. But if you want to be at the last key before 'rattle' ('ratting')
there is no way of knowing which pointer to take. For 'rattle' you would
need the first pointer, for 'rattles' the second.

If the B-tree only supports simple lookup by key you can take this shortcut.
If, as is the case with OM, we need to be able to go to the nearest key in a
consistent way we have to keep the full key in the lower index levels.

Martin

--------------------------------

Your idea of splitting blocks at points which generate small index keys is
ingenious. I suppose one is sacrificing data space to get tighter index
space, which would lead to faster retrieval -- the customary tradeoff of
space for time. 

I'll give it a bit more thought ...

M




]