I'm not sure why you need a lexically-ordered index if you use filenames as the location token. It would seem to me that what you need is a consistent ordering rather then a lexical one. I'm assumming here that we are talking about a directory which is static and we just want to make sure that we see every filename at some point.
BTW, are there any standards which speak to what one should see in the presence of directory changes? Personally, the most I would hope for in the dynamic directory case is that a program would eventually see every file that existed at opendir() time before readdir() returned no more files.