Structured and semi-structured (a.k.a. swept or extruded) hexahedral meshes are used in many types of engineering analysis. In finite element analysis, regions of structured and semi-structured mesh are often connected in an unstructured manner, preventing the use of a globally consistent parametric space to represent these meshes. This paper describes a method for mapping between the parametric spaces of such regions, and methods for representing these regions and interfaces between them. Using these methods, a 57% reduction in mesh storage cost is demonstrated, without loss of any information. These methods have been implemented in the MOAB mesh database component, which provides access to these meshes from both structured and unstructured functions. The total cost for representing structured mesh in MOAB is less than 25 MB per million elements using double-precision vertex coordinates; this is only slightly larger than the space required to store vertex coordinates alone.