Merkle Tree – a hierarchy of blocks starting from data blocks at the bottom and progressing upwards to the root with a set of hash blocks. Hashes are unique and each is a fingerprint of the data from which it is computed. Each hash block can link downwards to a base data block or, at an upper level in the tree, to two hash blocks at a lower level and upwards to a single hash block. At the bottom layer, every data block has a hash value computed and it is placed in a corresponding hash block and so on as we move from left to right. The next level of hash blocks each references two lower hash blocks and have hash values concatenated from the two connected lower blocks. The root block has its hash values computed by concatenating the hash values of the blocks one level down that are linked to it. The root hash is effectively a fingerprint of the entire data set. In a file by file comparison the validity of the data in the data blocks can be verified by checking the root hash values of the two files.
If a data block is altered or deleted then its hash value will differ or vanish and this can be checked by looking at one or more of the tree of hashes above it oir the root. Merkle trees are an underlying component of blockchains and also bitcoin. Apache Cassandra uses Merkle trees to detect inconsistencies between replicas of entire databases.
