Лично я склоняюсь к БД. Например, SQLite. Только, естественно, не одним файлом, а разбить на "блоки". Идею можно посмотреть в
SAS.Планете (кэш BerkeleyDB) или в
SACS, там прямо в SQLite есть кэш.
По поводу FS - не всякая система способна выдержать такую нагрузку (
Windows XP и 50 миллионов файлов в кеше SASGIS), так что нужно смотреть на её тип и проверять под нагрузкой.
Если вопросов по надёжности FS не возникает и вы в ней уверены, то стоит рассмотреть вопрос бэкапов, а именно, удобство и скорость их создания и восстановления. Имхо, бэкапить миллионы тайлов очень неудобно, поэтому БД тут дадут фору.