Normally in LDAP there are three basic index types implemented:
The various LDAP server implementations may have other indexes.
Almost no applications use presence filters in their search queries. Presence indexing is pointless when the target attribute exists on the majority of entries in the database. In most LDAP deployments presence indexing should not be done, it's just wasted overhead.
Here's the capsule summary of how a search works - if you're searching on a filter that has been indexed, then the search reads the index and pulls exactly the entries that are referenced by the index. If the filter term has not been indexed, then the search must read every single entry in the target scope and test to see if each entry matches the filter. Obviously indexing can save a lot of work when it's used correctly.
But assuming your application actually *does* use presence filters, if the target attribute exists on the majority of entries in your target scope, then all of those entries are going to be read anyway, because they are valid members of the result set. In a sendmail MTA subtree, where 100% of the entries are going to contain the sendmail attributes, the presence index does absolutely NOTHING to benefit the search because 100% of the entries match that presence filter. So the resource cost of generating the index is a complete waste of CPU time, disk, and memory. Don't do it unless you know that it will be used, and that the attribute in question occurs very infrequently in the target data. The most common message you'll see that you should pay attention to is:
"<= bdb_equality_candidates: (foo) index_param failed (18)"
That means somebody tried to use an equality filter (foo=<somevalue>) and attribute foo does not have an equality index. If you see a lot of these messages, you should add the index. If you see one every month or so, it may be acceptable to ignore it.