📅 Original date posted:2012-06-19
📝 Original message:Alan Reiner wrote:
> A PATRICIA tree/trie would be ideal, in my mind, as it also has a
> completely deterministic structure, and is an order-of-magnitude more
> space-efficient. Insert, delete and query times are still O(1).
> However, it is not a trivial implementation. I have occasionally looked
> for implementations, but not found any that were satisfactory.
PATRICIA Tries (aka Radix trees) have worst-case O(k), where k is the
number of bits in the key. Notice that since we would storing k-bit
hashes, the number of elements must be less than 2^k, or else by
birthday paradox we would have a hash collision! So O(log N) <= O(k).
You're right, though, that such a trie would have the property that
any two trees containing the same data (leaves) will be identical. I
can't think of any reason why this is useful, although I am hoping we
can figure out what is triggering your intuition to desire this! I am
indeed assuming that the tree will be incrementally constructed
according to the canonical (blockchain) ordering of transactions, and
that the balancing rules are agreed on as part of the protocol.
--
Andrew Miller
Andrew Miller [ARCHIVE] /
npub1rh…jcxem
2023-06-07 10:18:34
in reply to nevent1q…0n68
Author Public Key
npub1rhmu9sjnhraz783t3ffylkdwu75ld98ncelrdtwstup36p92tgnqfjcxemPublished at
2023-06-07 10:18:34Event JSON
{
"id": "2e1504f65d93d4c3141aeec056c8af824f809e0e040d7277e49e6fa1af455360",
"pubkey": "1df7c2c253b8fa2f1e2b8a524fd9aee7a9f694f3c67e36add05f031d04aa5a26",
"created_at": 1686133114,
"kind": 1,
"tags": [
[
"e",
"330d8e7bde9735c3f2b971e767f7ffbe4f47b36f7ea2112bca899a8b62371b85",
"",
"root"
],
[
"e",
"b9bc9df1bf56f87d49e19258d90b84b5cecfe3926189a52854ab26b36fe29f76",
"",
"reply"
],
[
"p",
"4aa6cf9aa5c8e98f401dac603c6a10207509b6a07317676e9d6615f3d7103d73"
]
],
"content": "📅 Original date posted:2012-06-19\n📝 Original message:Alan Reiner wrote:\n\u003e A PATRICIA tree/trie would be ideal, in my mind, as it also has a\n\u003e completely deterministic structure, and is an order-of-magnitude more\n\u003e space-efficient. Insert, delete and query times are still O(1).\n\u003e However, it is not a trivial implementation. I have occasionally looked\n\u003e for implementations, but not found any that were satisfactory.\n\nPATRICIA Tries (aka Radix trees) have worst-case O(k), where k is the\nnumber of bits in the key. Notice that since we would storing k-bit\nhashes, the number of elements must be less than 2^k, or else by\nbirthday paradox we would have a hash collision! So O(log N) \u003c= O(k).\n\nYou're right, though, that such a trie would have the property that\nany two trees containing the same data (leaves) will be identical. I\ncan't think of any reason why this is useful, although I am hoping we\ncan figure out what is triggering your intuition to desire this! I am\nindeed assuming that the tree will be incrementally constructed\naccording to the canonical (blockchain) ordering of transactions, and\nthat the balancing rules are agreed on as part of the protocol.\n\n-- \nAndrew Miller",
"sig": "b5c978f34cfc7b2fb7b36602e0e090f62b73be26c176e0b7498463d65a66addbf893ee17e814f1c4882662ec9bac892e519f4215b4b7913fca3c79edeb0bbcbe"
}