The data structure representing a mesh and the operators to create and query such a database play a crucial role in the performance of mesh generation and FE analysis applications. The design of such a database must balance the conflicting requirements of compactness and computational efficiency. Ten different mesh representations are reviewed for linear tetrahedral and hexahedral meshes. A methodology for calculating the storage and computational costs of mesh representations is presented and the 10 data structures are analysed. Also, a system for ranking different data structures based on their computational and storage costs is devised and the various mesh representations are ranked according to this measure.