linux - Removing files takes too long

Short version: rm
-rf mydir, with mydir (recursively) containing 2.5
million files, takes about 12 hours on a mostly idle
machine.

More
information: Most of the files being deleted are hard links to files in
other directories (the directory being deleted is actually the oldest backup made by
rsnapshot; the rm command is actually
given by rsnapshot). So it's mostly directory entries being
deleted - the file content itself isn't much; it's in the order of some tens of
GB.

I'm far from certain that
btrfs is the culprit. I recall backup was also very slow before
I started to use btrfs, but I'm not certain that the slowness
was in the deletion.

The machine is
an Intel Core i5 2.67 GHz with 4 GB RAM. It has two SATA disks: one has the OS and some
other stuff, and the backup disk is a 1 TB WDC
WD1002FAEX-00Z3A0. The motherboard is an Asus
P7P55D.

Edit: The
machine is a Debian wheezy with Linux 3.16.3-2~bpo70+1. This is
how the filesystem is
mounted:

root@thames:~# mount|grep
            rsnapshot
/dev/sdb1 on /var/backups/rsnapshot type btrfs
            (rw,relatime,compress=zlib,space_cache)

Edit:
Using rsync -a --delete /some/empty/dir mydir takes about 6
hours. A significant improvement over rm -rf, but still too
much I think. (Explanation of
why rsync is faster than rm:
"[M]ost filesystems store their directory structures in a btree format, the order [in]
which you delete files is ... important. One needs to avoid rebalancing the btree when
you perform the unlink.... rsync -a --delete ... does deletions
in-order")

Edit:
I attached another disk which had 2.2 million files (recursively) in a directory, but on
XFS. Here are some comparative
results:

 On the XFS disk On the
            BTRFS disk
Cached reads[1] 10 GB/s 10 GB/s
Buffered reads[1] 80 MB/s
            115 MB/s
Walk tree[2] 11 minutes 43 minutes
rm -rf mydir[3] 7
            minutes 12 hours

[1]
With hdparm -T /dev/sdX and hdparm -t
/dev/sdX.
[2] Time taken to run find mydir -print|wc
-l immediately after boot.
[3] On the XFS disk, this was soon
after walking the tree with find. On the BTRFS disk it is the
old measurement (and I don't think it was with the tree
cached).

It appears to be a problem
with btrfs.