What are some examples of good data structures to store particle systems in that would allow for acceptable performance?
I would think of something similar we used in bounding volume hierarchy structure for storing particles. KD tree is an example of spatial acceleration data structure. When we want to find some particle, we can traverse the tree to find nearest particles to some point.
For data structures, I would highly recommend exploring OpenVDB here, an industry-used standard for volumetric data: https://www.openvdb.org