Your question about appropriate choice of data structure doesn't provide quite enough detail about the problem you are trying to solve. Questions I would have asked in-person when trying to help you include:
- How many active sessions do you expect on average and maximum? That is, what's the N-value we need to worry about for the asymptotic complexity of operations?
- What are your response latency and memory consumption constraints?
- What is the relative mix of add/remove/query operations?
- Can you make a reasonably reliable estimate of which order TIDs will arrive in? (If yes, most operations on our data structure will be at the beginning or end, with little need for searching operations)
- Do you know for sure that all the TIDs you are holding will eventually receive an update? (Alternative: some items in your in-memory data structure correspond to TIDs you will never see again, because you're not always guaranteed to see an "end-session" event).
Not knowing these things (I'm not familiar with the application domain or the "size" if your planned system) I can only make what I think are reasonable guesses, but please forgive me if I guess wrong.
I'm going to guess:
- Many; allow the resulting data structure to fill memory if necessary.
- Latency requirements are in the 1ms-100ms range, meaning that we should ideally avoid disk accesses - in this case, avoidable database operations. Memory consumption requirements are much vaguer but let's assume we can't use a sparse data structure (for example a hash table). The rationale here is that if we have some amount of memory, there are probably other kinds of data it's more useful to keep in it than this information (again, if I knew more about your application domain this would help...)
- add:remove:query ratios are close to 1:1:1.
- Assume we can't predict the TID arrival order
- Assume that we can't be sure that we'll see all sessions neatly closed (so we need to adopt a data structure which allows some kind of separate housekeeper process to occasionally delete stale TIDs).
If these guesses are more or less right, I'd probably use a heap. Heaps are denser than linked lists and much denser than hash tables. Each heap entry would contain the TID as the key and whatever other payload data your have (you didn't say; but if there is no additional payload, that's fine too).
Using a heap means that all the operations (insert, delete, lookup) are O(log(N)). If queries are much more common than insert/delete, then we should consider paying memory to get speed (for example using a hash table; the operations are O(1) but more memory is used). Contrariwise, if your data structure might get very large, you should consider using a B-heap instead of a regulat binary heap, because it's kinder to the virtual-memory system. See You're Doing It Wrong by Poul-Henning Kamp, which describes a cache system with some (rather small) degree of similarity to what you're doing.
If your heap is represented as an array, you may have trouble growing it beyond the initial size of the array. Using the traditional scheme of doubling the size of the array when it fills will amortize the overhead of the copying operation so that we can maintain logarithmic performance. But it would mean that occasionally, one of the insert operations will take much, much longer than others. The other property of a heap is that most implementations are designed for single-threaded use. If either of these two issues are going to be a problem for you, consider using a balanced tree instead of a heap.