Years ago I was trying to use Merkle trees for checksuming and synchronizing database replicas, since everyone was doing it this way. It was immediately obvious

Years ago I was trying to use Merkle trees for checksuming and synchronizing database replicas, since everyone was doing it this way. It was immediately obvious how impractical it was. So the first thing that came to mind was to use a fixed sized Merkle tree (half trees or whatever they are called). It was essentially an array of 64k hashes with each element storing a hash for a set of database keys. That, however, required rescanning multiple keys on updates and the number of keys depended on the database size. Of course this wasn't going to work well. Naturally the same idea of adding and subtracting hashes came to mind. Adding a hash of a key on update and subtracting on removal allowed to completely eliminate reads from disk. And rescanning a particular set of keys was only necessary during background synchronization and only when a key was missing on a replica, which was pretty rare. Although I don't use this approach anymore, it did work well and was trivial to implement.