Merkle Treap is my favorite data structure, it is a mutable sortable merkle tree.
Sortable means you get perfect locality of pointers, instead of the randomisation of hash maps.
Mutable meaning you can add or remove elements while changing Only the nodes on the path from the changed element to the root.
Every update happens from the top bottom, as opposed to bottom up as usual in Merkle trees like the one used in Git.
It is just a joy.
The only downside is if you are using it for set reconciliation with multiple writers, a bad writer can mine keys such that the treap degenerates into a linked list.
So for set reconciliation from multiple untrusted writers, you should use RBSR like Negentropy.
Nuh
npub1jv…s7yqz
2025-03-26 14:50:31
Author Public Key
npub1jvxvaufrwtwj79s90n79fuxmm9pntk94rd8zwderdvqv4dcclnvs9s7yqzPublished at
2025-03-26 14:50:31Event JSON
{
"id": "7598e8a93cf18707102b9eb7791127a6152f070df07bbafbfe3e988c6c1c98fe",
"pubkey": "930ccef12372dd2f16057cfc54f0dbd94335d8b51b4e2737236b00cab718fcd9",
"created_at": 1743000631,
"kind": 1,
"tags": [],
"content": "Merkle Treap is my favorite data structure, it is a mutable sortable merkle tree.\n\nSortable means you get perfect locality of pointers, instead of the randomisation of hash maps.\n\nMutable meaning you can add or remove elements while changing Only the nodes on the path from the changed element to the root.\n\nEvery update happens from the top bottom, as opposed to bottom up as usual in Merkle trees like the one used in Git.\n\nIt is just a joy.\n\nThe only downside is if you are using it for set reconciliation with multiple writers, a bad writer can mine keys such that the treap degenerates into a linked list.\n\nSo for set reconciliation from multiple untrusted writers, you should use RBSR like Negentropy.",
"sig": "23025c6dcfd1e9cee3db9275865b6f64e0d27bf7bcc406801370f6b005f33736a6e89e9b22c3e2436c78f13941ddab54c5ef8b86904c88353485d0a6619f578e"
}