An efficient and effective parallel/distributed adaptive finite-difference (AFD) implementation must use a parallelization, decomposition, and distribution scheme that complements the problem itself. Correspondingly, the implementation of the identified data structures must complement the dynamic and hierarchical nature of adaptive grid hierarchy. The fundamental requirement in realizing such a class of dynamic, distributed data structures is the generation of an extendable, global index space. A class of dimension changing mapping called space filling curves can be used to provide such an index space. 

Space filling curves are a class of locality preserving mappings from d­dimensional space to 1-dimensional space , i.e. N^d --» N¹, such that each point in N^d is mapped to a unique point or index in N¹. The mapping can thus be though of as laying out a string within the d-dimensional space so that it completely fills the space. The 1-dimensional mapping generated by the space-filling curve serves as an ordered indexing into multi­dimensional space. Mapping functions used to generate the space-filling index corresponding to a point in multi­dimensional space typically consist of interleaving operations and logical manipulations of the coordinates of the point, and are computational inexpensive. Two such mappings, the Morton order and the Peano-Hilbert order, are shown in the figure below. Two properties of space filling curves, viz. digital causality and self-similarity, make them particularly suited as a means of generating the required adaptive and hierarchical index-space.

Digital Causality: Digital causality implies that points that are close together in the d-dimensional space will be mapped to points that are close together in the 1­dimensional space, i.e. locality is preserved by the mapping. 

Self-Similarity: Self-similarity property implies that, as a d-dimensional region is refined into smaller sub-regions, the refined sub-regions can be recursively filled by curves that have the same structure as the curve used to fill the original (unrefined) region but possibly different orientations. The figure above illustrates this property for a 2­dimensional regions with refinements by factors of 2 and 3.

In addition to providing a linear ordered index space that is hierarchical and extendable, each index generated by the space­filling mapping has information about the original multi­dimensional space embedded in it. As result, given a key, it is possible to obtains its position in the original multi­dimensional space.