Ralph Merkle created one of the most relevant and optimized data-structure modifications combining a hash-list and a binary tree. The patent issued pertaining to this data structure is here https://patents.google.com/patent/US4309569A/en.
For computer scientists and creators of crypto-code such as the blockchain, this data structure came to be known as the Merkle tree and is one of the most robust mechanisms to validate transactions. On distributed computer networks and peer-to-peer transaction networks since data is present in multiple locations, any alteration of data has to be verifiable, even if the data cannot be accessed in its true form. Just the ability to validate whether this data (or transaction as in the case of a blockchain) is correct provides a necessary and sufficient condition for
The algorithmic time complexity for operations such as search, retrieve and validate is similar to that of a binary tree; The following properties verbalize the data-structure.
1) Each leaf is a hash of a block of data
2) Each non-leaf node is a hash of its children
To validate data from a particular hash of data – all that is needed to validate against the root of the Merkle-tree to check whether the hash matches (or the signature matches). This is used for sync-ing up large blocks of data as in a blockchain.
Assume two computer nodes A and B having the same copy of the blockchain. B receives a new data block created by the process of mining as does A. It adds it to the block and calculates the hash. So does A. Now if we have to see if the process of data being similar on A and B, all A needs to do is receive the top level hash and validate it against the top level hash on B. If there is a mismatch – say A hasn’t synced up to the level of B as yet, all A has to do is traverse to the child nodes and check if the child nodes match. If a match is found then the new data is valid, if it isn’t then it continues traversing down the tree.
This operation is accomplished in Logarithmic time.