Storing Utreexo Trees as compact arrays and use math indexing without any pointers

[Shymaa-Arafat]

Since Trees in the Utreexo forest are all full complete binary trees, they can be stored as arrays, no need for pointers at all ....

Thus saving 600M-1.2G depending on pointer size (2pointers for each node =~152m*pointerSize)

We can read how to use math indexing instead of pointers in lec8 here
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/index.htm
min15 here
https://youtu.be/Xnpo1atN-Iw

pretty simple isn't it?!

I only suggest to make it a variable size 2D array (the same space size) because having a separate row for each level will help more in visualizing & indexing our problem specific proof traversal along with normal traversals needed for insertions & deletions.

So for the famous example

The tree will be stored like that

R[0]=0,1,2,...,7
R[1]=8,9,10,11
R[2]=12,13
R[3]=14

(As written in the drawing in Utreexo, the case of nodes X,Y will never happen we either split or merge to keep all trees full)

A simple Pseudo code for fetching proof of node "i" would be (of course i mod 2=0 could be replaced by IsEven, or lowest bit is zero,...)

//direction to know + or -
If ((i mod 2)==0) drct=1;
else drct=-1;

// first, the sibling node
proof[i]=R[0,i+drct]

//add the rest thru loop
For(j=1; j≤logN; j++)
{ index= i/(2^j)+drct;
proof[i]=Add(R[j,index]);
}

Note that although Go maps are more space saving than C maps they still endure overhead fields, I'm not 100% sure the runtime implementation appears in here is the only one
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics
but from there you can see all these extra unnecessary fields in addition to the unnecessary pointers too

I guess that's all I have for now & you probably know that I posted the idea here too
https://bitcointalk.org/index.php?topic=5360009.0

[Shymaa-Arafat]

In fact any place that stores a Merkle Tree like Transaction Merkle Trees for example can benefit from both ideas; ie store it as a summation of power of 2 complete trees + store it in a compact 1D or 2D array without pointers.
It would be even easier as u build the forest once and never insert or delete just repeatedly fetch proofs.
.
I think that what Bitcoin Core does for the Block Transaction Merkle Tree
https://github.com/bitcoin/bitcoin/blob/7fcf53f7b4524572d1d0c9a5fdc388e87eb02416/src/primitives/block.h#L66
The tree is stored as a vector ( favoring the original 1D array idea)
std::vector vtx;
Also in
https://www.oreilly.com/library/view/mastering-bitcoin/9781491902639/ch07.html
Example you will find the use of push_back which is a vector fn
.
Is this what u call serialization in Utreexo?
If so, why not use it from the beginning instead of storing pointers tree then serialize it back???