LDAP database management tools

Attribute index format

The LDBM backend will maintain one index file for each attribute it is asked to index. Several sets of keys must coexist in this file (for example, keys for equality and approximate equality), so the keys are prefixed with a character to ensure uniqueness. The prefixes are as follows:

=: equality keys
~: approximate equality keys
: substring equality keys
\: continuation keys

Key values are also normalized (for example, converted to upper case for case ignore attributes).

Substring indexes are maintained by generating all possible N-character substrings for a value (N is 3 by default). These substrings are then stored in the attribute index, prefixed by ``''. Additional anchors of ``^'' and ``$'' are added at the beginning and end of words. So, for example the surname of ``Antbear'' would cause the following keys to be entered in the index:

   ^AN, ANT, NTB, TBE, BEA, EAR, AR$

Approximate values are handled in a similar way, with phonetic codes being generated for each word in a value and then stored in the index, prefixed by a tilde (~).

Large blocks in the index are split into smaller ones. The smaller blocks are accessed through a level of indirection provided by the original block. They are stored in the index using the continuation key prefix of ``\''.