2

I am currently struggling to design a Solidity-based data structure that is meant to store bits of information indexed by a 10-character base32-encoded key (i.e. geohashes). Trick is, that I will need to be able to retrieve all key matching a certain key-prefix easily (i.e. all datasets for a specific "area").

Example:

I have three datasets data_1, data_2, and data_3 and their keys. For simplicity, let's assume the length of the keys is 4 (instead of 10) and the character set is [a,b,c] (instead of base32).

key => data
-----------
bbba => data_1
bcaa => data_2
bccb => data_3

Now, I need to retrieve all datasets with a given prefix, let's say bc. I would expect datasets data_2 and data_3 to be returned.

The typical approach for this would be a hash tree/merkle tree. Anyhow, returning all leaf node datasets for any given subtree ("hash-prefix") would be computationally quite expensive as it would require to traverse that entire subtree.

In the example below, I would need to traverse the tree to get all leaf nodes for the prefix bc, giving me back data_2 and data_3. Those, I could store in an array , which is then returned by the function. I guess this is - speaking of Gas costs - quite infeasible...

                    [root]
             /        |        \
          a           b           c
       /  |  \     /  |  \     /  |  \
     aa  ab  ac  ba  bb  bc  ca  cb  cc
    /|\ /|\ /|\ /|\ /|\  /|\ /|\ /|\ /|\
         ...        bbb bca bcc
                     |    \     \               
                   bbba   bcaa   bccb
                     |      |      |
                  data_1 data_2 data_3

Hence, I thought about storing all nodes in an array, calculating the indices for a certain subtree and returning that part of the array. Anyhow, as we're speaking Byte32-encoded 10-character keys, this would result in an array of extraordinary length (32^10).

Given the fact that we're talking about an EXTREMELY sparse dataset (at max, I think 100M datasets of the 32^10 possible leafs will be used) - is there an efficient way to store/manage/retrieve datasets in this fashion?

4
  • I'd say a mapping, just because it is the only sparse data in solidity. Use the index as the key to the mapping.
    – Ismael
    Jun 4 '21 at 4:38
  • Yes, of course mappings will be used. But: If I have a key "abcd", I want to retrieve it via "a", "ab", "abc", and "abcd". And if retrieving "ab", i want all keys starting with "ab" to be returned! (i.e. "abaa", "abab", "abac", "abad", "abba", "abbb", "abbc", "abbd", "abca", "abcb", "abcc", "abcd", "abda", "abdb", "abdc", and "abdd" !!!)
    – Xenonite
    Jun 4 '21 at 9:55
  • Unfortunately I can't help you there a mapping can't be iterated, you have to combine with something else, for example use an array to store the keys. The EVM perhaps is not the right tool, perhaps you should consider splitting in the process in two parts, some on-chain and off-chain for the more complex parts.
    – Ismael
    Jun 4 '21 at 17:40
  • Thanks for looking anyways! Anyhow, I'm afraid that this part cannot be offloaded to some off-chain part. What needs to be on-chain is the part where I specify a geohash of a certain length (i.e. an area), and all known datasets for this area are then returned. I think I found a way anyhow. I'll post my results once I've tested
    – Xenonite
    Jun 11 '21 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.