With respect to IPFS and Merkle Search Trees, can anyone "in the know" comment on how they're materially different than Probabilistic B-Trees as defined by Noms[1] and Dolt[2]? I've been playing a lot with the Noms variant (Prolly Trees) lately and have often wondered where they differ from IPFS-ish Merkle Search Trees. If at all.
Whereas Noms Prolly-Trees are like B+Trees, since all values are stored in the leaves.
Merkel Search Trees use the prefix of the hash of inserted keyvalues (number of leading zeros) to determine which layer will contain that keyvalue. This provides a deterministic tree structure for any given set of keyvalues, when you arrange them by key order.
Noms Prolly-Trees use a rolling hash across the sequence of keyvalues to determine split points, similarly when the number of leading zeros exceeds a threshold. Then those leaves are assigned as children to keyvalues on the next highest layer, which is again split in the same way, until a single root node is left.
Excellent description, thank you! While i'm mulling on what you described, are there any use cases that jump out for Merkel over Noms?
Given that i've been using Prolly-Trees for a content addressed store, a lot of the descriptions of Merkel sound similar in properties to how Prolly-Trees behave. I struggle to think of a use case where Prolly would excel over Merkel, or where Merkel would excel over Prolly.
Whereas Noms Prolly-Trees are like B+Trees, since all values are stored in the leaves.
Merkel Search Trees use the prefix of the hash of inserted keyvalues (number of leading zeros) to determine which layer will contain that keyvalue. This provides a deterministic tree structure for any given set of keyvalues, when you arrange them by key order.
Noms Prolly-Trees use a rolling hash across the sequence of keyvalues to determine split points, similarly when the number of leading zeros exceeds a threshold. Then those leaves are assigned as children to keyvalues on the next highest layer, which is again split in the same way, until a single root node is left.