Many store owners will have issues with changing site structure, which makes huge trafic as well as search engine rank loss. Here is simple trick that works very well.

Add below code and modify and save in .htaccess

RedirectMatch 301 catalog/(.*)$ http://www.yournewstore.com/$1

What exactly it dose?

In my example all request on http://yourstore.com/catalog/filename.php?query are redirected to http://yourstore.com/filename.php?query with 301 (moved permanently) responce. The advantage is search engines update their database without any efforts.