What is the difference between trickle-dag and merkle-dag?

From @xloem on Mon Jan 09 2017 11:40:41 GMT+0000 (UTC)

What is the difference between trickle-dag and merkle-dag?

Copied from original issue: https://github.com/ipfs/faq/issues/218

2 Likes

From @Kubuxu on Tue Jan 10 2017 11:52:36 GMT+0000 (UTC)

tricker-dag is a merkle-dag in the definition sense but when we think about merkle-dag we default to thinking about balanced tree DAG. This isn’t the case in with trickle-dag that has other structure (list-of-lists).

From @xloem on Tue Jan 10 2017 23:33:27 GMT+0000 (UTC)

I guess I mean, what is the effective difference for the user: when should trickle-dag be used?

From @mateon1 on Fri Jan 13 2017 10:42:33 GMT+0000 (UTC)

Trickle-dag is optimized for reading data in sequence, while the merkle-dag improves random access time. It might make sense to use trickle-dag for long videos, but in my experience it’s not a massive difference.

1 Like

After coming across this question I still had a similar question:
Why and how is trickle-dag more efficient for streaming in comparison to balanced-dag which is more efficient for random access?

The following visualisation is pretty helpful:


TL;DR as explained by @Jorropo

That’s because in trickle-dag the bytes of the start of the file are closer to the root.
With balanced-dag all the leaves are at a constant distance from the root (more or less).
With trickle the start of the file is linked in the root, then the further it is in the file the further it is from the root.

This matters for bitswap where you need one round trip for every layer in the dag. For trustless gateway the impacts are really small if not nil.