Arbre de Merkle (BD)
Un arbre de hachage où chaque feuille est le hash d'une plage de données et chaque nœud le hash de ses enfants. Il permet à deux répliques de trouver exactement où elles divergent en comparant les hashs du sommet vers le bas — sans transférer toutes les données.
Mécanique : la racine résume tout le jeu de données en un seul hash. Si les hashs racine de deux répliques sont identiques, les répliques le sont aussi (terminé). S'ils diffèrent, on compare les hashs des enfants et on ne creuse que dans les branches qui divergent → on localise les plages divergentes en temps logarithmique plutôt qu'en comparant ligne par ligne. Dans les bases de données distribuées (Dynamo, Cassandra, Riak), c'est ce qui alimente l'anti-entropie et la réparation. La même structure de données sert dans Git (les commits), les blockchains (la vérification des transactions), Certificate Transparency et IPFS — partout où l'on veut vérifier ou comparer efficacement de gros volumes de données. L'une des structures de données les plus polyvalentes des systèmes distribués. À rapprocher de l'anti-entropie et du hachage cohérent.