So, we had this problem with a client with a fairly high number of users and experiencing serious performance issues (Open LDAP + BDB backend) . We were running slapd 2.4.23 and bdb 4.6 version.
The first thing I did was to upgrade to the lattest version of bdb (4.9) and use lattest utils which comes along with it.
Slapd by default runs with only one thread. Running multiple threads will improve the performance of the slapd considerably.
This instance of the detail involved very fewer writes and considerably large number of reads. Hence heavy indexing shouldnt affect the write performance, but indeed make search operation faster which is crucial to our needs.
Next crucial part of the performance is determined by the backend database that we use. We use Berkley Database (formerly known as sleepycat), since its heavily tunable and has a decent documentation to its part.
The first factored to be tuned was the cache size of the DB. Then I tuned the number locks. By default maximum number of locks used by tbhe BDB is 500. But the values between 1500-3000 should be good enough depending upon number of reads. Due to our WORM( Write Once Read Many times) use-case, I decided to go for 1500.
The transaction logs can also be tuned but we didnt need it much due to our less frequent writes.
There are many other possible tunings ( dbnosync,io methods etc) but our case didnt require much. The choice of directory server basically depends on the use case and in case of places where heavy writing is involved OpenDJ looks good (though I havent personally tested it). I am planning to benchmark openDJ, 389ds , openldap and write about it in the next week.
Please throw in your suggestions and opinions about several directory services with regards to perf. and stability. You can mail me at firstname.lastname@example.org or find me on irc with handle sarguru__ in freenode.