Existing approaches for multi-dimensional frequent patterns mining rely on the construction of data cube. Since the space of a data cube grows explosively as dimensionality or cardinality grows, it is too costly to materialize a full data cube, esp. when dimensionality or cardinality is large. In this paper, an efficient method is proposed to mine multi-dimensional frequent patterns without data cube construction. The main contributions include: (1) formally proposing the concept of multi-dimensional frequent pattern and its pruning strategy based on Extended Apriori Property, (2) proposing a novel structure called Multi-dimensional Index Tree (MDIT) and a MDIT-based multi-dimensional frequent patterns mining method (MDIT-Mining), and (3) conducting extensive experiments which show that the space consuming of MDIT is more than 4 orders of multitudes smaller than that of data cube along with the increasing of dimensionality or cardinality at most cases.