Skip to content

Trie: Create an efficient Map which uses TrieHash as keys directly #36

@tomusdrw

Description

@tomusdrw

Introduced in:

// TODO [ToDr] [crit] We can't use `TrieHash` directly in the map,

Related PR: #29

JavaScript Map object uses === comparison to match the keys when querying it. Since we want to use TrieHash (which internally is Bytes<32>) as keys, we can't really do that unless we internalize all bytes objects (i.e. make sure they have the same references) which does not sound like a good idea initially (although we can measure that :)).

The goal is to implement a Map that can have any object as it's keys and use some sort of Equal interface (or maybe better Comparable to be able to do bin search) to compare them.

If that makes sense we can also have something more specialized towards Bytes<32>:
I can imagine splitting the Bytes<32> sequence into chunks of 6 bytes and creating JS number types (we need to keep it below SAFE INTEGER (2**53 iirc); alternatively we could use BigInt and use 8 bytes). and create a 6-time nested Map to store the keys, like that:
Map<First6bytes, Map<Second6bytes, Map<Third6bytes, Map<Forth6bytes, Map<Fifth6bytes, Map<Last2bytes, Value>...>

It's worth testing though if that approach is faster than simply having some form of sorted list of keys and doing binary searches.

Obviously to take a good decision about this data structure we need to know exactly how many values we might be storing, but that requires a real-world data (the gut feeling though is: a lot, think millions)

Metadata

Metadata

Assignees

Labels

M-databaseDatabase-related tasks & features (state management, storing blocks, etc).P-optimisationPossible optimisations of the code (measure!).

Type

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions