On Thu, Mar 22, 2012 at 8:33 PM, Emmanuel Lécharny <elecharny@gmail.com> wrote:
Hi,

a second mail about index, specifically those related to the manipulation of the DN.

RDN index
---------

First of all, let's present the data structure used for the Rdn index. It's not exactly a RDN index, as the key is a composite structure : the ParentIdAndRDN (it contains the entry ID of it's parent in the DIT and the entry's RDN). More, it's not exactly a RDN that we store, as for the partition root, we store the partition DN (which can contain more than one RDN).

One example first. Let's consider that we have a partition 'dc=example,dc=com' with one entry 'ou=apache'. The DIT will be like :

dc=example,dc=com[3]
 |
 +-- ou=apache[7]

Here, the partition has an ID = 3 and the entry has an id = 7.

Thus, the RDN index will contain the following tuples :

<0, dc=example,dc=com> --> 3   // As the parentID of a partition is the root DSE, which ID is 0
<3, ou=apache> --> 7           // The parentID is 3, and the entry ID is 7

So far, so good. Now, how do we use the index ? And should we have a forward and a reverse table, or is only one of those two table is enough ?

First, let's say we want to lookup for an entry knowing its DN. here, we want to fetch the 'ou=apache,dc=example,dc=com' entry. How do we do that ? 
We use the forward table, starting from the right of the DN.

1) dc=example,dc=com is the right part, and it's the partition. In the forward RDN index, we find :
<0, dc=example,dc=com> --> 3
when we search for the element which has 0 (rootDSE ID) as an parentID and 'dc=example,dc=com' as the current RDN.

2) Now, we can move forward in the DN, and pick the next RDN ('ou=apache'). Combined with the previous parent ID (3), we can search the Rdn forward index, searching for the entry ID for <3, ou=apache>. We get back 7, which allows us to fetch the entry from the master table.

Baseline, we *need* the forward table in the RDN index. Now, do we need the reverse table ?

Let's say we have found an entry in the master table, and that we have to return it back to the client. This entry does not have any DN, we have to construct it.

This is done using the reverse RDN index, this way :

1) We fetch the ParentIdAndRdn from the reverse table, for the entry ID. In our example, using 7 as the key, we get back <3, ou=apache>. The left part of the DN is now known : 'ou=apache'

2) With the previous ParentIdAndRdn, we can fetch the parent element using the parent ID (3). We get back <0, dc=example,dc=com>. We can now concatenate the found RDN to the previous one, giving 'ou=apache,dc=example,dc=com'.

We are done, we have built back the DN, usinhg the reverse index.

So basically, yes, the two table (forward and reverse) are mandatory for this table.

Agreed. 

--
Best Regards,
-- Alex