directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <akaras...@apache.org>
Subject Re: [index] RDN
Date Wed, 28 Mar 2012 15:25:01 GMT
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

Mime
View raw message