[robertsdionne]

Merkel Search Trees are like B-Trees, as described in https://hal.inria.fr/hal-02303490/document, since internal nodes can store values.

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.

[adkadskhj]

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.