Run updatedb via root's crontab, at whatever times are appropriate for you... I like to run it once a day at 5am when no-one will be using the computer (heavy disk access kills the responsiveness of my system). Since cron runs programs periodically, there's always going to be some sort of delay between adding new files and being able to find them with locate - the only way to avoid that is to run updatedb yourself if you've just added or moved files you want to find.
|