Data stream storage system

A device for recording at least part of a data stream therein, the data stream including a plurality of instances of a plurality of event types such that each one of the event types has at least one of the instances in the data stream, the data stream also including a plurality of positions such that each of the instances is located at one of the positions or within a range of the positions, each of the instances having a value, the device including a recording module to:

• record a plurality of records divided among a plurality of segments, the records including an instance record for each of the instances, the instance record of each one of the instances including:
• the one event type of the one instance and at least one of the positions identifying the one instance, each of the segments covering a range of the positions in the data stream such that different segments cover different ranges of the positions, wherein the arrival order of the instances arriving at the recording module may be out of position order, the recording module being operative to record the instance records of each one of the plurality of segments by appending the instance records to the one segment according to the arrival order of the instances;
• record the value of each one of the instances such that:
• the instance record of the one instance includes the value of the one instance;
• or the value of the one instance is stored externally to the instance record of the one instance, the instance record of the one instance including a reference to the externally stored value of the one instance;
• create a refresh region at the beginning and/or the end of each of the segments, the refresh region including a plurality of refresh region records such that the records in each of the segments include the instance record for each of the instances and the refresh region records, the refresh region records including data from a most recently recorded instance record of each one of the event types such that each of the refresh region records includes the data for a different one of the event types, wherein the refresh region record of the one event type includes:
• the at least one position identifying the most recently recorded instance record of the one event type;
• the one event type;
• and the value of the most recently recorded instance record of the one event type or a reference to the value of the most recently recorded instance record of the one event type;
• create a plurality of links between the records to enable traversing the records in position order even when the instance records are recorded out of position order, wherein the links include:
• a plurality of bidirectional links between nearest neighbors of the records, independent of the event-types, in the one segment, the nearest neighbors being nearest neighbors according to the positions included in the records;
• and a plurality of bidirectional links between nearest neighbors of the records of the same one of the event types in the one segment;
• and
• create an indexing table including an entry for each of the segments, the entry for each one of the segments including the range of the positions covered by the records of the one segment.