The complexity of btrfs incremental send vs rsync in batch mode

[Fadhil Kurnia <fikurnia@cs.umass.edu>]

Hi btrfs developer,

I am using btrfs-send with the hope that it has logarithmic
complexity compared to linear complexity of rsync in batch mode.

In rsync, to compare what changes between two directory
(or files), it needs to do a linear scan in both the original
and the copy directory to get the differences between them.

In incremental btrfs-send, my expectation is that it can compare
two subvolumes in logarithmic complexity (not linear) since under
the hood the subvolumes are represented in B+Tree; both subvolumes
(snapshots) also share many blocks in the tree. The expected
complexity is logarithmic as in the comparison between
two merkle-tree.

Could anyone confirm my expectation that btrfs-send run in
logarithmic complexity is correct?

Thanks,
Fadhil I. Kurnia
CS PhD Candidate,
University of Massachusetts Amherst