Clean your Gallery 2 ImageBlockCacheMap table regularly

Supposedly, Gallery 2 has a process to clean this table periodically (through Cron, which you should always configure), but apparently sometimes this doesn't get to execute correctly. As a result, the rest of the cleanup will happen but this stable might not get cleaned, leading you to millions of rows of purely useless years-old cache junk. Fix it manually by issuing a "TRUNCATE [prefix]_ImageBlockCacheMap;" in your database, or install a more recent version of Gallery, or something like that, but make sure you always keep an eye on its size. Reference: http://galleryproject.org/node/30045