US Patent 11711204 Using sparse merkle trees for smart synchronization of S3

One example method, which may be performed in connection with an object store, includes receiving a key of a key-value pair, correlating the key to a location in a base of a Merkle tree, inserting the key at the location, hashing the value associated with the key to produce a data hash, and inserting the data hash in the Merkle tree. The Merkle tree may then be checked for consistency, and synchronized with another Merkle tree. The Merkle tree may be of a fixed size, and insertion of the key in the Merkle tree does not change the location of any keys existing in the Merkle tree prior to insertion of the new key.