Fuzzy object-oriented data model is a fuzzy logic-based extension to object-oriented database model, which permits uncertain data to be explicitly represented. One of the proposed fuzzy object-oriented database models based on similarity relations is the FOOD model. Several kinds of fuzziness are dealt with in the FOOD model, including fuzziness between object/class and class/superclass relations. The traditional index structures are inappropriate for the FOOD model for an efficient access to the objects with crisp or fuzzy values, since they are not efficient for processing both crisp and fuzzy queries. In this study we propose a new index structure (the FOOD Index) dealing with different kinds of fuzziness in FOOD databases and supports multi-dimensional indexing. We describe how the FOOD Index supports various types of flexible queries and evaluate performance results of crisp, range, and fuzzy queries using the FOOD index.