What does the Indexing actually do?

["Matthew Hoskins" <matth@ponyexpress.net>]

This question may be more esoterical than practical...

I am running a directory with 50000 entries and do multiple searches on the
uid attribute.  Needless to say, without the indexing the search took
incredibly long!  I indexed the uid attribute and the searches went from 2 -
3 minutes to less than a second!  My question really is -- What exactly does
the indexing do?  I know it creates a seperate file with just the index
information, but -- what is in that file that allows for such dramatic
increases in performance?

Thanks,

Matthew Hoskins -- Cisco Certified Network Associate
Ponyexpress.net / MagicCablePC / NPGCO
Systems Administrator