[ot][spam][crazy] journal: doubly append-only balanced trees

Undiscussed Horrific Abuse, One Victim of Many gmkarl at gmail.com
Wed Jul 13 06:01:25 PDT 2022


Thinking of lookup data.

Say the root were included in every tip update. The root could reference
the locations where its immediate child internodes are. The important ones
would be the final updates that fill a subtree, as these have access to the
location of every leaf.

Before a subtree is filled, what to include seems a little hazy. The first
leaf needs a reference to itself, and the left largest subtree, to pretend
to be a new root.

On the second subtree leaf, a new subroot is made to hold both of them. so
it contains two indexing nodes: one to reference the last biggest subtree,
and one to reference its pairing with its neighbor.

Then the third subtree leaf actually only needs two again: a root that
references the old root and the larger subroot, and then the larger subroot
that references its sibling subtree and itself.

In a graph, basically an index is needed for what ....

Base root. Parenting subroot. It has a log2 in it somewhere i guess.

The big question is how to build indexes based on last state, that develop
the same minimal number of indexing entries. The idea comes from imagining
balanced subtrees that never move and never change after being filled.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 1534 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20220713/5c5a4f29/attachment.txt>


More information about the cypherpunks mailing list