Howard Chu wrote:
Emmanuel Lecharny wrote:
Hi guys,
Stefan started to modify the code to get rid of the oneLevel and
subLevel index, which are more or less useless as we already have the
hierarchy stored into the rdn index.
However, this rdn index is not good enough as is to be use as a
replacement for the two other indexes. Its structure forbid us to easily
retrieve the children from a known entry.
The current RDN index structure is :
<parentId, RDN> -> Entry ID
The key is a tuple containing the parent ID to be able to rebuild the DN.
The reverse index is :
Entry ID -> <parentId, RDN>
We don't have duplicated values.
Now, when we have an entry ID, there is no simple way to get the list of
all the children for this entry.
We will have to add a third index to deal with such searches :
ParentId -> <entryId, ....>
which will list all the children of a specific entry.
I'm going to investigate around this idea i the next few days.
Thoughts ?
Currently in OpenLDAP back-hdb and back-mdb, the DN index contains
Entry ID -> <parentID, RDN> [,<child ID, RDN> ...]
So each entry's RDN is stored twice, once under its own entryID, and once
under its parent's entryID. This allows top-down DN to ID lookups and
bottom-up ID to DN lookups from a single index.
(This is a bit different from the original layout described in 2003
http://www.openldap.org/conf/odd-sfo-2003/proceedings.html )
I forgot to mention... Onelevel lookups are obviously trivial with this
scheme. back-hdb and back-mdb differ in how they perform subordinate lookups.
back-hdb recursively builds a list of subordinate members (and caches this
list for future queries). back-hdb is ridiculously slow for subordinate
lookups that haven't been cached yet.
back-mdb is a bit more straightforward; given a list of candidate entry IDs,
it simply walks up from the entryID until it hits the base of the desired
subtree (meaning candidate is present in the result set) or until it hits the
root of the tree (candidate is not present). As a further refinement (not yet
implemented) if a search yields an all-entries candidate list (unindexed
search), it can just recursively descend from the base of the desired subtree
and ignore the candidate list.
It turns out that building the cached IDLs in back-hdb is much slower than
just reading the index in back-mdb. (Not to mention being a memory pig.)
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
