Jason Dusek writes:

I'm curious because DNs are the only allowed key for the referential integrity. If they are searched using string operations, that would be pretty slow relative to shorter strings (UID) or plain old Int values.

If you need a search for an attribute to be fast, you should index that attribute if you use back-bdb/hdb. (And I presume, do something equivalent if you use back-sql.) This applies regardless of whether the search is done by a client or an overlay - like refint or unique. DN-valued attributes like secretary and seeAlso are no different from other attributes in this respect.

bdb/hdb indexing works on a hash of the attribute value. After scope and indexing (if any) has narrowed down the search, the resulting candidate entries are checked against the filter with the ordinary matching rules.

Are DNs optimized in any way, for lookup or storage? Or are they merely packed into strings and searched lexicographically?

For DN-valued attributes, see above. For the entry DNs themselves, bdb and hdb maintain a dn2id file which maps DN (bdb) or parent+RDN (hdb) to entry-ID.