We had a similar problem in the past. And found a nice solution:
- Give each image an unique guid.
- Create a database record for each image containing the name, location, guid and possible location of sub images (thumbnails, reducedsize, etc.).
- Use the first (one or two) characters of the guid to determine the toplevel folder.
- If the folders have too much files, split again. Update the references and you are ready to go.
- If the number of files and the accesses are too high, you can spread folders over different file servers.
We have experienced that using the guids, you get a more or less uniform division. And it worked like a charm.
Links which might help to generate a unique ID: