[spike] Discovery of possible optimization of a Trie structure for a prefix iterator

[RitaMAllenCA]

As implemented currently the Trie enum has two major variants: Leaf, which contains K, and V, and a Node which contains 255 pointers in a trie. Each pointer in the Node variant is either Leaf pointer or Node pointer. In the prefix iterator implementation when we descend into the requested prefix we have to also navigate all the trie pointer’s to get the actual Key value based on the matching prefix. The idea of this discovery ticket is to determine if we can optimize this by moving K from Trie::Leaf variant into the LeafPointer variant inside pointer block, so we can short circuit the last step, and just return the K from the LeafPointer without reading another Trie object at a pointer to get that K. We know for a fact that random IO on the slowest supported machine is super slow which led us to implement the batching migration mechanism, so we think this is worth measuring at least before making decision.

[RitaMAllenCA]

@mpapierski this is something we want to do, but it is not urgent, or the most important thing for you to do at the moment. Please finish what is in the sprint before taking this on

[devendran-m]

To do: Have a conversation with Michal and Bart before L1 Sprint planning. @devendran-m

[devendran-m]

Follow-up action as per the discussion on L1 Daily on 17-Sep-24;

• Michał to review the code to confirm if the work is already completed. If it is done, close the ticket as completed. If not, discuss with Bartłomiej to pick up the remaining work.