Дерево Меркла (БД)
Хеш-дерево, в котором каждый лист — хеш диапазона данных, а каждый узел — хеш своих потомков. Позволяет двум репликам найти, где именно они различаются, сравнивая хеши сверху вниз, — не передавая сами данные.
Механика: корень описывает весь набор данных одним хешем. Если корневые хеши двух реплик совпадают, реплики идентичны — готово. Если нет, сравниваются хеши потомков, и спуск идёт только по ветвям с расхождением: различающиеся диапазоны находятся за логарифмическое время, а не построчным сравнением. В распределённых БД (Dynamo, Cassandra, Riak) на этом держится anti-entropy-ремонт. Та же структура работает в Git (коммиты), блокчейнах (проверка транзакций), Certificate Transparency и IPFS — везде, где нужно эффективно проверять или сравнивать большие наборы данных. Одна из самых универсальных структур в распределённых системах.