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

[Undiscussed Horrific Abuse, One Victim of Many]

I remember there's an old mainstream project that does this, but I don't
remember what it is off hand very well. Anyway it basically just used
whatever the clearest approach was.

First update is first root.

Second update makes two leaves. The new root goes in the second update,
with both leaves its children.

Third update makes a third leaf and third root. The tree is binary and the
third leaf has a sibling that is waiting for the 4th update.

There is an internode between the third leaf and the third root that is the
parent of the 4th root. With the original system, I believe this internode
can be considered implicit, since everything is always a balanced binary
tree. Hence, only the data and leaf index need be stored via the storage
medium, in the extreme.

Compare my approach. Ideally I would make the same simple balanced trees,
but maybe with more internode information since leaves are not always at
the end. We could set a norm for implicit internode information, if not
provided, to optimize append-only cases further.

Let's see if I can stabilize this in my mind a little ... in the previous
way, a binary tree is built up from one side to the other, like a card
tower. For updates that are two powers, a new root is made: like a new row
of cards except in a hierarchical binary way.

First one node.

Then three.

Then seven: two threes with a seventh as the root.

That third root looks helpful for simple description. When the 4th node is
added, it is basically saying there is a new root with 1 subtree and 1 leaf
as children: anything with comparable topology or what it. Then the 5th
node becomes a sibling to the 4th. What data would be in a 5th update?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 2178 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20220713/56bed08f/attachment.txt>