A low overhead index structure for dynamic main memory database managementsystems

In this paper, an effective index structure for dynamic main memory databas e systems, which we call the T-2- tree, is presented. A notion of a thread pointer is introduced to overcome some of the limitations of the T-tree and the T*-tree. There are several advantages to this structure. First, the T- 2- tree reduces the number of rotate operations and the overhead required f or balancing the tree by restraining new node creation and deletion. Second , the T-2-tree shows good performance for sequential search of range querie s as these requests can be effectively handled using the successor pointer. Finally, the T-2-tree allows for higher space utilization amplicating the aforementioned benefits. These advantages are obtained with minimal changes to the existing T-tree structure. Experimental studies showing evidence of the benefits of the T-2-tree are also presented.