For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Low Overhead Index Structure for Dynamic Main Memory Database Management Systems
Heung Seok JEON Tae Jin KIM Sam Hyuk NOH Jaeho LEE Hae Chull LIM
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/09/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
T2-tree, main memory database systems, index structure,
Full Text: PDF>>
In this paper, an effective index structure for dynamic main memory database systems, which we call the T2-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 T2-tree reduces the number of rotate operations and the overhead required for balancing the tree by restraining new node creation and deletion. Second, the T2-tree shows good performance for sequential search of range queries as these requests can be effectively handled using the successor pointer. Finally, the T2-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 T2-tree are also presented.