directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <>
Subject [index] RDN
Date Thu, 22 Mar 2012 18:33:20 GMT

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 :

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

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.

Emmanuel L├ęcharny

View raw message