This paper proposes a newand efficient data structure for storing large database to support Incremental Association Mining. Incremental algorithms are used to modify the results of earlier mining to derive the results for the incremented database. Various business databases are incremental in nature and knowledge is required from the updated database to infer some decisions and predictions. At times it is needed to ignore the previous knowledge obtained from the old database. Thus incremental algorithm should be able to manipulate the inferred rules when some part of the present database is deleted. To implement algorithms for incremental mining, first of all, an efficient data structure to store the data is needed. An easiest and most understandable way of storing the data is in the relational form. But in case of incremental implementation relational form of the data will incur high complexity. Literature reveals that number of tree based data structures are proposed by different researchers in [1,2,3]. A critical analysis on the existing data structures has been performed and observed that most of the earlier data structures were not efficient. Considering the efficiency issue in the storage and handling of large data for incremental association mining, present paper introduces a novel tree-based data structure.