Fast Cache - Optimize GetWithIndex by including leaf hash to fast nodes

[p0mvn]

Background

There are several potential opportunities to optimize GetWithIndex and GetByIndex. Research needs to be done whether the following are possible:

1. Combine Get and GetWithIndex by introducing leafHash to fast nodes
   Currently, there are 2 methods for getting values from iavl+ - Get and GetWithIndex. The changes were introduced in Fast storage optimization for queries and iterations  #5. We would like to avoid having 2 implementations where one is slow only to be able to return the index. The current limitation results from the fast node not knowing the index of the regular node in the tree. We can probably combine the 2 methods together by having leafHash introduced to the fast node.

2. GetWithIndex and GetByIndex - iterate over fast cache
   Currently, to determine the index or get by index, we need to traverse the tree that does a lot of queries with no data locality.
   Instead, if the fast cache is enabled, we could simply iterate over fast nodes since they are already sorted by keys and maintain the same order as in-order traversal of the keys of iavl+ (since iavl+ is sorted by keys)

Acceptance Criteria

• research into all opportunities to optimize
• leaf hash is introduced to fast node
• GetWithIndex is optimized.
• GetByIndex is opt
• unit tests where applicable

[p0mvn]

After looking into this, I could not find a way to utilize leaf hash in fast nodes in order to optimize.

I attempted to iterate over fast cache in GetWithIndex and GetByIndex but it only made the performance worse. The benchmark is documented here: #12

I'm closing this issue for now.

@ValarDragon FYI

[ValarDragon]

Sweet, thanks!