Make KVStore interface have methods to getNearest entry

[ValarDragon]

Summary

When you want to use the KVStore a sorted dataset, as we do in generalized F1 data structures, and a number of other data structures, you need to be able to 'find/get' the closest key to an entry. (e.g. like sort.Search https://pkg.go.dev/sort#Search )

I propose we add a function to KVStore called KVStore.GetNearest(key []byte, round_direction enum.Round_Direction), and a new enum called Round_Direction, that has two options nearest_left, nearest_right. (I'm not at all convinced on this naming, I suspect theres better naming that could be used)

So if the entries in the tree are at keys {a, aa, ac, ad}, I should be able to do:

KVStore.GetNearest('ab', nearest_left) = 'aa'
KVStore.GetNearest('ab', nearest_right) = 'ac'
KVStore.GetNearest('ac', nearest_left) = 'ac'
KVStore.GetNearest('ab', nearest_right) = 'ac'

At the moment, this can be done via iterators (as we essentially do in osmosis here) but this has very large overheads. Making iterators is not light weight. (See constituent logic in https://github.com/cosmos/cosmos-sdk/blob/master/store/cachekv/store.go#L166 for instance)

No matter what, this is making an iterator over the underlying sorted tree, which is high overhead. However the actual operation that should be happening in most cases is actually a really cheap operation. It should be the same cost as Get.

This will require changes in tm-db as well.

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[tac0turtle]

@testinginprod what do you think of this?

[testinginprod]

@ValarDragon @tac0turtle, what I'm not understanding is this a helper method? or is this something that we expect to be implemented natively by the raw DB? I can easily implement this helper method in collections, using the Iterator  API, but I'm not sure if this is what we're looking for.

NVM, read the issue better, this should be solved natively from the raw DB, I can add a helper on collections still if we want it.

[testinginprod]

Considering we're planning to refactor store soon, I think this is something we will mainly want for the "SS" layer.

[yihuang]

This can be implemented with iterator api already I think