The described technology is generally directed towards a streaming data storage system that maintains streamed events, including in a manner that facilitates the ordering of those events based on external ordering (position) data. An event is appended to an event segment, and an index segment maintains offset information to the event relative to the offsets of other previously appended events. The index segment is ordered by position data provided with the event, such that the events (e.g., for a given event routing key) can be read back in position order instead of append order. An ongoing read that returns an event (that matches ongoing read criteria) as the event arrives can also be handled. Also described is the use of a tail index and an indexing queue for more efficient handling of events prior to writing the offset information into the index segment.