Xapian devel - Dec 2004 - dividing B-trees

[I originally sent this mail to Martin and Richard, but then realised
it's of wider interest, so I'm resending it to the list with
Martin's
reply attached (with his consent)]

I was talking to Richard about trying to use shortened dividing keys in
the B-trees.  Shorter keys are better because you can then fit more in
each block, so you need fewer B-tree levels for the same data.

Quartz only shortens keys when going from the leaf level to the next
level above, which Richard and I thought was a missed opportunity.  But
I tried doing this for higher (if the root is the top) levels, but it
doesn't work because there may be a lower sorting key which is the wrong
side of the truncated key.  For example:


         |   mat   |   muz   |                
        /          |          \
       /           |           \
      |            |            | 
      V            V            V
[... mad] [matter ... muscat] [muzzle ...]   <--(keys in leaf blocks)


If we try to truncate a key to separate "mat" and "muz", we
get "mu",
but this divides "matter" and "muscat" which are in the same
block.
The higher level dividing key must match a leaf level block division,
which is clearly why the existing code does what it does!

But what if we approach this from the other direction.  Say we have a
leaf block "[matter ... muscat muzzle ... needy]" which we want to
split.  Instead of splitting as close to halfway as we can (which it
turns out is between "muscat" and "muzzle"), we try to find
a split
point with a short dividing key (but also one as close to halfway as we
can manage given this primary criterion).  So in this case, our dividing
key would be "n" instead of "muz".

This seems plausible, except it creates blocks less than half full.
I've not looked at this myself, but Richard said something about
the proof of the complexity of B-tree operations assumed blocks were
always half-full (or something like that).

What if we always ensure that we pick a key such that they're at least
1/3 full, say?  So we look for the best split point in the middle 1/3,
which might be "mu" instead of "n", but that's still
shorter than "muz".

Except that in sequential mode (which we will usually be in for large
database builds) we split at the insertion point.

Actually, sometimes it may be worth splitting slightly before the
insertion point.

Say that we can split at the insertion point and get a 240 character
dividing key, or one item back to get a 1 character dividing key.  If we
split at the insertion point, we can expect to use an extra 239 bytes
per level in the B-tree, whereas by splitting one earlier, we waste the
size of the item which we could fit here, but choose not to.  If the
tags are small and the Btree has several levels, that could easily be a
win.  But this example is rather extreme...

Or perhaps there's some other cunning way to go about this...

Cheers,
    Olly
-------------- next part --------------
An embedded message was scrubbed...
From: martin.porter at grapeshot.co.uk (Martin Porter)
Subject: Re: dividing B-trees
Date: Thu, 16 Dec 2004 21:30:28 GMT
Size: 1747
URL:
<http://lists.xapian.org/pipermail/xapian-devel/attachments/20041229/5c2e6792/attachment.mht>

Martin Porter writes:
> 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. 
It may not even be a trade - it's conceivable that we can save more on
index space than we sacrifice on data space, especially in tables where
the key names are long and the tags fairly short (this is largely true
for of the position table).

The other point I've realised is that in the postlist table we insert
throughout the table even when we're just appending documents to the
database (which is a very common case we want to handle especially
well).  In this case, choosing the split point to fill the block right
now is probably futile, as it won't be optimal once more tags have been
inserted.

So perhaps I should start by trying this out on the non-sequential
addition case, and see what difference it makes to the postlist table
size and structure.

Cheers,
    Olly