Databases have a lot of overhead, so I wouldn't go there.

Maybe drop your elements into a directory, open a directory handle and read them in date order (maybe not so easy if you have to sort a million file records).

You could split them off into chucks... a manageable chuck of records added to a directory and an index added that is processed. Then the second process looks for another index...

Disk space shouldn't be an issue since a million elements in a database being constantly added and dropped is likely to take more space and have fragmentation issues related to this, etc.