[rucksack-devel] Btrees

[Edi Weitz]

On Sat, 05 Aug 2006 00:16:42 +0200, "Arthur Lemmens" <alemmens at xs4all.nl> wrote:

> 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?

You're right, I didn't think of that.  I just thought about "standard"
btrees with one value per key.