Search for the most recently added node

I'm adding vertices with a certain label to a graph (currently using gremlin-python over gremlinv3.3). I'm manually adding a "timestamp" property to these nodes. I want to be able to find the most recently added vertex with this label so that I can then retrieve a certain number of vertices backwards down the chain from there. Adding a set of a "next" type edges from the second-newest to the newest vertex at each addition will allow me to perform the backwards search once I've found the newest vertex.
I want to be able to locate the most recently added vertex in sub-linear time (ideally O(1) time). Here are a couple of ideas how to do that:

I could manually maintain a node of type "newest" which points to the newest vertex of this type and then search for that.
I could create a binary tree of index vertices over these vertices as I add them, so that searching up the tree and back down from any of these vertices delivers me to the newest node in O(log(n)) time.
It may also be that I could exploit the timestamp property to search efficiently, but it's not clear to me how.

The problem is, I don't know enough about how the graph search is implemented under the hood to know which of these strategies is best. Can anyone help? It's also likely that what I create will get redeployed in an amazon-neptune instance, and again, it's not clear to me whether that would change the best strategy.

Solution

I could manually maintain a node of type "newest" which points to the newest vertex of this type and then search for that.

That's the simplest and fastest solution. Solutions based on other search queries require some kind of index structure that will not allow you to access the latest vertex in O(1).