Maybe you could somehow take advantage of Linux's inotify mechanism (and Linux::Inotify2) — if you're on Linux, that is, of course... but your mention of ext3 sounds like you might be.  In other words, you could scan the entire directory once, and then update the resulting data structure as you receive events about individual files being added, removed, etc.  Or something like that.  Just an idea...