Comment 18 for bug 398870

Cron work-around: a weekly "cd /var/lib/dpkg && mv info info.bak && cp -a info.bak info && rm -R info.bak" to keep the directory contiguous.

ReiserFS work-around: create a ReiserFS partition especially to hold /var/lib/dpkg/info. ReiserFS was specifically designed to handle zillions of tiny files in one massive directory (under the philosophy that databases mostly because filesystems aren't up to the task). As /var/lib/dpkg/info demonstrates, ext3 is having having fragmentation trouble on huge database-like directories.

Short-term solution: Have the default Ubuntu installation defragment /var/lib/dpkg/info regularly

Long-term solution: Have dpkg use a database instead of /var/lib/dpkg/info. I deduce that the person who specified /var/lib/dpkg/info as a massive directory of tiny files was expecting ReiserFS to become the standard filesystem. Since that's not going to happen, it's about time to use a database.