Микола

md5 от файла и размазываем по директориям.

/images/news/a/s/d/f/asdf....jpg

Превьюшки вообще не хранить, а делать их на лету через nginx и класть в его кэш. В крайнем случае хранить в папке рядом с оригиналом - удалять будет проще.