LDAP indexes are extremely useful for speeding up directory searches, and come in four flavors (there are actually more than four index types, but the following four are the most common):
1 Approximate indexes
Approximate indexes are useful for speeding up seaches that look for attribute values that sound like a specific value. A good example of this is searching the directory for all first names that sound like “Amy”:
$ ldapsearch -b "dc=prefetch,dc=net" -w -D "cn=Directory Manager" 'givenName~=Amy'
2. Equality indexes
Equality indexes are useful for speed up searches that perform a direct comparison. The following search would benefit from an equality index:
$ ldapsearch -b "dc=prefetch,dc=net" -w -D "cn=Directory Manager" 'uid=matty'
3. Presence indexes
Presence indexes are useful for speeding up searches for entries that contain a specific attribute. The following search looks for all entries that contain the cn attribute, and would be a good fit for a presence index:
$ ldapsearch -b "dc=prefetch,dc=net" -w -D "cn=Directory Manager" 'cn=*'
4. Substring indexes
Substring indexes are the most complex index type to maintain, but are useful for speeding up searches that look for substrings. The following search will return all entries where the uid attribute contains the string “foo”, and would be a good fit for a substring index:
$ ldapsearch -b "dc=prefetch,dc=net" -w -D "cn=Directory Manager" 'uid=*foo*'
Figuring out which indexes to use is actually pretty easy, since most directory servers will tell you that an unindexed search was performed. If you want to determine indexes manually, your best bet is reviewing the logfiles to see which searches are perfomed, and then creating indexes based on your findings.