search

linera-io / linera-protocol

Main repository for the Linera protocol
Apache License 2.0
1.44k stars 168 forks source link

Implement the `trie` data structure #1282

Open MathieuDutSik opened 11 months ago

MathieuDutSik commented 11 months ago

The prefix search as currently done in GreatestLowerBoundIterator is a clumsy data structure despite its recent improvement. We need a true trie data structure.

Requirements:

More precision: The complexity of a trie search is linear in the length of the key being tested.

The complexity of a single search to GreatestLowerBoundIterator is O(log(M) N) with N the length of the key being tested and M the number of prefixes in the database. This complexity is the one we are exposed to in get and multi_get. However for the function call for_each_key_while and similar, the complexity is better since the keys being called are lexicographically ordered and so the search is more efficient in that case.

ashu26jha commented 11 months ago

Hello @MathieuDutSik I think the description of the issue needs to be slighlty changed after #1381 i.e. changing fromGreatestLowerBoundIterator to SuffixClosedSetIterator