What is the most efficient (yet sufficiently flexible) way to store multi-dimensional variable-length data?
===

I would like to know what the best practice for efficiently storing (and subsequently accessing) sets of multi-dimensional data arrays with variable length. The focus is on performance, but I also need to be able to handle changing the length of an individual data set during runtime without too much overhead.

Note: I know this is a somewhat lengthy question, but I have looked around quite a lot and could not find a solution or example which describes the problem at hand with sufficient accuracy.


**Background**

The context is a computational fluid dynamics (CFD) code that is based on the discontinuous Galerkin spectral element method (DGSEM) (cf. Kopriva (2009), *Implementing Spectral Methods for Partial Differential Equations*). For the sake of simplicity, let us assume a 2D data layout (it is in fact in three dimensions, but the extension from 2D to 3D should be straightforward).

I have a grid that consists of `K` square elements `k` (`k = 0,...,K-1`) that can be of different (physical) sizes. Within each grid element (or "cell") `k`, I have `N_k^2` data points. `N_k` is the number of data points in each dimension, and can vary between different grid cells.

At each data point `n_k,i` (where `i = 0,...,N_k^2-1`) I have to store an array of solution values, which has the same length `nVars` in the whole domain (i.e. everywhere), and which does not change during runtime.

**Dimensions and changes**

The number of grid cells `K` is of `O(10^5)` to `O(10^6)` and **can** change during runtime.  
The number of data points `N_k` in each grid cell is between `2` and `8` and **can** change during runtime (and may be different for different cells).  
The number of variables `nVars` stored at each grid point is around `5` to `10` and **cannot** change during runtime (it is also the same for every grid cell).

**Requirements**

Performance is the key issue here. I need to be able to regularly iterate in an ordered fashion over all grid points of all cells in an efficient manner (i.e. without too many cache misses). Generally, `K` and `N_k` do not change very often during the simulation, so for example a large contiguous block of memory for all cells and data points could be an option.

However, I do need to be able to refine or coarsen the grid (i.e. delete cells and create new ones, the new ones may be appended to the end) during runtime. I also need to be able to change the approximation order `N_k`, so the number of data points I store for each cell can change during runtime as well.

**Conclusion**

Any input is appreciated. If you have experience yourself, or just know a few good resources that I could look at, please let me know. However, while the solution will be crucial to the performance of the final program, it is just one of many problems, so the solution needs to be of an applied nature and not purely academic.

Should this be the wrong venue to ask this question, please let me know what a more suitable place would be.