Структуры данных / Дерево Меркле

Хэш-деревом называют представление данных в виде дерева с корнем, ветвями и листьями.

Построение дерева:

1. Каждый лист дерева именуется результатом хэш-функции над блоком данных этого листа;
2. Каждая ветвь и корень дерева именуется результатами хэш-функции над списком всех имён прямых потомков и блоком связанных данных при наличии таковых.

Хэш-деревья являются обобщённым видом для хэш-списков и хэш-цепочек. Хэш-деревья предоставляют эффективный и безопасный метод проверки структур данных большого размера. Проверка достоверности и принадлежности листа дерева требует обработки данных пропорционально логарифму количества узлов дерева, для хэш-списков необходимо обработать все узлы списка.

Прочие названия и применение хэш-деревьев:

• Деревья Меркле, названы по имени Ральфа Меркле, запатентовавшего идею хэш-деревьев в 1979;
• TTH (Tiger Tree Hashing), алгоритм проверки целостности данных файлов в сетях DC++, Gnutella.