dpkg: unrecoverable fatal error, aborting:
 unable to create `/var/lib/dpkg/updates/tmp.i': No space left on device
E: Sub-process /usr/bin/dpkg returned an error code (2)
E: Failed to write temporary StateFile /var/lib/apt/extended_states.tmp

dpkg: error: unable to create new file '/var/lib/dpkg/status-new': No space left on device

Could not create temporary file for /var/cache/apt/pkgcache.bin

df -h might show that your device has plenty of space left.

Filesystem               Size  Used Avail Use% Mounted on
udev                     2.0G  4.0K  2.0G   1% /dev
tmpfs                    395M  416K  395M   1% /run
/dev/dm-1                4.5G  1.7G  2.7G  38% /
none                     4.0K     0  4.0K   0% /sys/fs/cgroup
none                     5.0M     0  5.0M   0% /run/lock
none                     2.0G     0  2.0G   0% /run/shm
none                     100M     0  100M   0% /run/user
/dev/mapper/system-tmp   1.8G  2.9M  1.8G   1% /tmp
/dev/sda1                184M   39M  136M  23% /boot
/dev/mapper/system-home  4.5G  373M  3.9G   9% /home
/dev/mapper/system-var   4.5G  3.1G  1.3G  72% /var
/dev/mapper/system-usr   9.1G  1.5G  7.1G  18% /usr

df -i will show a full device, because of to many inodes.

Filesystem              Inodes  IUsed  IFree IUse% Mounted on
udev                    502234    466 501768    1% /dev
tmpfs                   505135    422 504713    1% /run
/dev/dm-1               305216  42913 262303   15% /
none                    505135      2 505133    1% /sys/fs/cgroup
none                    505135      2 505133    1% /run/lock
none                    505135      1 505134    1% /run/shm
none                    505135      2 505133    1% /run/user
/dev/mapper/system-tmp  121920     19 121901    1% /tmp
/dev/mapper/system-home 305216   9542 295674    4% /home
/dev/sda1                48768    299  48469    1% /boot
/dev/mapper/system-var  305216 305216      0  100% /var
/dev/mapper/system-usr  610800  80660 530140   14% /usr

Find these inodes with the following command

for i in /var/*; do echo $i; find $i |wc -l; done

Go into the correct dir and delete the inodes if not needed (WARNING: THE FOLLOWING COMMAND WILL REMOVE EVERTHING IN THE CURRENT DIR!)

cd /var/bla
for i in * ; do rm $i ; done

if too many

mkdir empty_dir
rsync -a --delete empty_dir/ yourdirectory/

In my case 296093 files in “/var/spool/icinga2/perfdata/”