Investigate more efficient storage and access of Indexed Merkle Tree snapshots

[alexghr]

In #3468 and #3504 we've added tree snapshots to access historical data in contracts. The snapshots for an indexed tree store a copy of the tree structure at every snapshots point (basically every block). This does produce a valid snapshot but it is not very space-efficient because the tree leaves are modified on every insert (in order to maintain the sorted linked-list).

Look for a more efficient way of storing this data, potentially trading off storage needs for more hashing needs when accessing historical data (e.g. like we did for append only trees).

Also consider adding indexes so that queries regarding historical leaves are answered efficiently.

[sirasistant]

Also consider adding indexes so that queries regarding historical leaves are answered efficiently.

In the case of indexed trees we'd need an efficient way (akin of the standard_indexed_tree implementation done in https://github.com/AztecProtocol/aztec-packages/pull/3530/files#diff-035dc3bdb3ff63fe6f604fa8895674ecf6673c3f330af5caf4b1bee34543aecfR133) to resolve findIndexOfPreviousKey