Emmanuel Lécharny schrieb:
> On 5/13/10 8:08 AM, Alex Karasulu wrote:
>> Hi Emmanuel,
>>
>> On Sun, May 9, 2010 at 6:42 PM, Emmanuel
>> Lecharny<[email protected]>wrote:
>> ...
>>
>> As soon as you consider that a delete operation will need to update
>> all the
>>
>>> index the deleted entry uses, you see that you can benefit from
>>> having such
>>> reverse index : you don't have to grab the entry from the backend, as
>>> you
>>> already have it's ID, which is all what you need. Thus, a delete
>>> operation
>>> is just about doing :
>>> - get the entry ID
>>> - for each index, if we have an<Entry ID> stored, then grab the
>>> associated
>>> values, and for each value, delete them from the forward index.
>>> - delete the entry from the MT
>>>
>>>
>>>
>> Yep this is one benefit of the reverse index.
> At this point, I'm questionning the fact that it's an advantage. We can
> do almost the same thing using the forward index, assuming we know the
> attribute we are dealing with, and we also have the value in the filter,
> so we can check that the entry we are looking at is present in the index
> for this attribuet. Let me explain with some example :
>
> filter : (cn=value), cn is indexed.
> you are looking for entry E(x)
> The reverse index will contain :
> E(x) --> value
> the forward index will contain :
> vaue --> E(1), E(5), ... E(x)...E(N)
>
> so you can still in a O(log(N)) find the entry in the forward index
> without fetching the entry first.
>
>> There are other uses for the
>> reverse index. To start let's just list the various index methods
>> leveraging
>> the reverse index:
>>
>>
>> boolean reverse( ID id ) throws Exception;
>>
>>
>> boolean reverse( ID id, K attrVal ) throws Exception;
>>
>>
>> boolean reverseGreaterOrEq( ID id ) throws Exception;
>>
>>
>> boolean reverseGreaterOrEq( ID id, K attrVal ) throws Exception;
>>
>>
>> boolean reverseLessOrEq( ID id ) throws Exception;
>>
>>
>> boolean reverseLessOrEq( ID id, K attrVal ) throws Exception;
>>
> In fact, those methods are not existing anymore (don't ask me why, I
> just grepped all the code). I don't know where you get them from ...
Check class org.apache.directory.server.xdbm.Index<K, O, ID>
> The only place where the reverse index is used atm is when checking that
> an entry has a value.
>>
>> These various reverse lookups are used all over the XDBM search code base
>> with various expression Evaluators and Cursors.
> Well, not anymore :)
They are still used. In fact there are more "reverse" methods in Index
class:
K reverseLookup( ID id ) throws Exception;
IndexCursor<K, O, ID> reverseCursor() throws Exception;
IndexCursor<K, O, ID> reverseCursor( ID id ) throws Exception;
Cursor<K> reverseValueCursor( ID id ) throws Exception;
I listed all callers in [1].
Kind Regards,
Stefan
[1] http://pastebin.com/dsBC3GVr
