[rucksack-devel] Btrees

[Arthur Lemmens]

Edi Weitz wrote:

> The attached patch cleans up (at least I hope so) the btree code a bit
> and adds the missing delete function and some more tests.

Very nice, thanks a lot.

> In particular, I convinced myself that KEY= is really not needed
> although I said the opposite at the ECLM.

Yes, I suppose you're right.  At the time I thought it might be useful
to support keys that only have a partial order, but that probably
doesn't make any sense.


> Also, the old version of BTREE-NODE-INSERT sometimes split too early
> because it eagerly split downwards.  The new version splits upwards
> and only if needed.

Great.  I've committed your patch (with some minor modifications).

But there's one thing in your patch that I think is wrong.  You removed
the VALUE argument for INDEX-DELETE:

> -(defgeneric index-delete (index key value &key if-does-not-exist)
> -  (:documentation "Remove a key/value pair from an index.
> +(defgeneric index-delete (index key &key if-does-not-exist)
> +  (:documentation "Remove a key from an index.

And your new BTREE-DELETE function doesn't take a VALUE argument either:

> (defgeneric btree-delete (btree key &key if-does-not-exist))

That's fine for btrees with unique keys (where each key corresponds to
one value), but I think it's not good enough for btrees with non-unique
keys (where each key can correspond to more than one value).

The most important reason for also having btrees with non-unique keys is
that they can be used to implement indexing for slot values.  The index
for slots that don't have unique values can be implemented as a btree
where the keys are the slot values and the values are the instances
containing that slot value.  (I'm not explaining this very well, but I
hope you understand what I mean.)

Suppose an object EDI of class PERSON has an indexed slot AGE.  Suppose
this AGE slot changes from 20 to 21.  Then we need to do something like

(INDEX-DELETE <index of AGE slot> 20 EDI)
(INDEX-ADD <index of AGE slot> 21 EDI)

We can't just do

(INDEX-DELETE <index of AGE slot> 20)

because that would remove all persons of age 20 from the index.
(See also the definition of RUCKSACK-MAYBE-INDEX-CHANGED-SLOT.)

So I think that INDEX-DELETE needs the VALUE argument, and so does
BTREE-DELETE.

Do you agree with this or am I missing something?

Arthur