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 >> Lecharnywrote: >> ... >> >> 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 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 > 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 reverseCursor() throws Exception; IndexCursor reverseCursor( ID id ) throws Exception; Cursor reverseValueCursor( ID id ) throws Exception; I listed all callers in [1]. Kind Regards, Stefan [1] http://pastebin.com/dsBC3GVr