Index your authentication id (uid, cn).

If you plan to use it for more than just authentication, such as authorization (group ID membership or Shibboleth federated style authentication) or if you plan to allow UNIX interactive logins where name services will be provide (e.g. when you type ls at the command prompt it looks up each file to see who uidNumber 111 is) then you may want to spread the wealth a little more.   I can't comment on the sizing in that case as I've never had more than 40k accounts against a Master/Slave setup.

I hope that is helpful.

Sellers