ok, im still not quite clear on what problem you're trying to solve. but im going to describe it as "you have some odd game mechanic that means you want to jump around randomly within a set timeline". and that the timeline itself has no logic (which you usually see with cutscene animation tools).
the difficult part here is that usually for cutscene animation tools, you'll trigger an animation at particular frames, and that animation will have been authored in a different tool, and you'd just tell your animation to play. and fix any problems with the seperate authoring tool. thats basically how cutscene playback works ;) just keyframes to start animations (or end looping ones).
the problem we appear to be solving here is one of random access. and im going to assume that this is the desired access pattern over linear playback. which would have a different solution completely. (which i'd be happy to ramble on about if you want).
right. to optimise for random access, im going to go with doing this on a per frame basis, rather than on a node-timeline basis. the general idea is that you're optimising being able to go directly to frame N, over memory footprint, or overall linear playback. to keep things to a sane memory footprint. i'd recommend having a buffer of some arbitrary number of frames that you've pre-processed in the per frame approach. while keeping the actual datastructure the more traditional node-timeline based paradigm.
so lets say that we're going to have a buffer of 1024 frames that we can jump to at any point. each "frame" would contain an array of two 32bit values per node. one an ID for the animation that's playing, and the other would contain the frame (or duration as a float) of the playback position within that animation. the thinking behind having a contiguous sized array is that it may lead to slightly more predictable memory usage and cache usage, but i'd recommend profiling that and working out whether you can get away with only storing the information for the nodes that have animations on that frame, rather than storing all nodes per frame regardless of animation state.
its then up to your animation system to be able to "jump to" a particular animation / time slice when requested by this system, which is a slightly different concern. the system we're talking about here shouldn't really be handling the animations themselves, but slaving a separate system. a similar approach, but unpacking keyframe / node data may work except it'd require a hell of a lot more memory!. it really depends on exactly what you're trying to do, which isnt really clear.
when you have more than 1024 frames, you would need to use a sliding widow approach and "decompresss" from your original space optimised data structure to your memory unfriendly optimised structure. you'll need at least two buffers, one you're reading from, and one you're decompressing too. assuming you're playing back linearly. jumping back to a frame which is no longer "decompressed" would require decompression before you could jump to it. but you could easily keep as many buffers around as you need depending on overall memory requirements.
the major downsides to this is that, linear playback suddenly becomes a hell of a lot of work for absolutely no benefit. you're doing a hell of a lot of preprocessing that you simply dont need to do. if you've got a number of these systems running at the same time, you're going to thrash the hell out of cache. its really not an approach that i'd recommend other for solving the "random access" problem.
doing linear playback is far easier achieved by just storing animation start points, and kicking off animations at particular frames, and stopping them when required. leaving the delta time to keep the animation in sync with the overall timeline. a hell of a lot less effort ;)
whew. ok hopefully that was slightly more useful? and you're kinda getting what im talking about? does this actually solve the problem you're asking?
I you're actually just asking "how do i write a cutscene system". the answer is far far far easier than the above.