3 ms·
What would prevent you from applying the splay tree re-balancing technique to a Merkle Tree? Or, is this something that is routinely done today? I could not fin
by bob1029 5y ago
What would prevent you from applying the splay tree re-balancing technique to a Merkle Tree? Or, is this something that is routinely done today? I could not find any examples out there.
Hypothetically, this technique could speed-up processing of trees for transactions that occur in real-time (i.e. historical operations filter to the bottom of the tree).
Also, the fact that Merkle Trees are keyed by hash automatically eliminates the only caveat of the splay tree algorithm WRT insertions.
The reason I really like the splay tree algorithm is that it is very friendly to linear storage operations. You only need to write a minimal subtree update to disk each time you make a series of updates (batches being ideal).