(pkg/trie): Add child trie support for TrieDB

[dimartiro]

The way lazy loading trie (TrieDB) works is totally different than in-memory tries, so we have to figure out how to add child trie support to TrieDB in order to lazy load those child tries too.

TODO: add some links from substrate implementation and define the strategy to solve it

[EclesioMeloJunior]

The current state of Gossamer child tries are lazy loaded by default, right?

The node that contains a child trie only holds the reference to it and when needed goes to the database and retrieve the full encoded child trie then decodes it into memory, performs some operation, and finally encodes the updated child trie back to update the parent node reference.

So, if we have a lazy load trie that is responsible to decode only the nodes that are necessary to execute an insert keeping the other nodes only with the reference then we can use it also for child tries.

[dimartiro]

Thanks for the comment, Eclesio! Perhaps I wasn't too descriptive in the original issue description, but my point is:

Currently, we are handling the child tries as part of the main trie and we have special methods to handle child trie operations.

When I was reading Parity's trie code, I didn't find any reference to child tries.

Since the child tries are just "independent" tries, we can instantiate them as a simple TrieDB for example: newTrieDB(db, childRoot) could represent a child trie

I think we should handle them in a different layer on top of the trie, and the main trie node that contains a child trie will simply be a reference to a child trie root.

What I mean is: the trie shouldn't be responsible for knowing about child tries. Instead, we should build a layer that uses the trie and adds child trie features (perhaps this layer could be the overlays).

[dimartiro]

I've been talking with @timwu20 and we are going to implement this as part of the overlays layer as Parity did. So he is going to take this task