You may also consider indexing your objects on every write, based on the property that binds distinct groups of them together across the ordered data structure.
This will increment memory usage and make each individual write more expensive - but not much so, if the right data structures are leveraged (e.g. a gb_tree for the ordered bit and a Map of lists for indexing stuff.)
The coordinated management of the two data structures (the main one plus the index) can be kept behind an API to keep it simple to use and reason about.
