loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Third International Workshop on Real-Time Computing Systems Application (RTCSA'96)
T*-tree: a main memory database index structure for real time applications
Seoul, Korea
October 30-November 01
ISBN: 0-8186-7626-4
Kong-Rim Choi, Dept. of Comput. Sci., Hong Ik Univ., Seoul, South Korea
Kyung-Chang Kim, Dept. of Comput. Sci., Hong Ik Univ., Seoul, South Korea
In this paper, we propose an indexing structure, called T*-tree, for efficient processing of real time applications under main memory database management systems (MMDBMS). T*-tree is an index structure for rapid data access and saves memory space under MMDBMS. T-tree is well known to be one of the best index structures for ordered data in MMDB. Existing T-tree is a balanced tree that evolved from AVL and B-trees, and a binary tree with many elements in a node. T-tree retains the intrinsic binary search nature, and is also good in memory use. However T-tree has major disadvantage; the tree traversal for range queries and the movement of overflow/underflow data due to data insertion/deletion on internal nodes. We propose T*-tree as a alternative structure, which is an improvement from T-tree for better use of query operations, including range queries and which contains all other good features of T-tree. We also show the pseudo-algorithms of search, update, delete, and rebalancing operations for T*-tree, with performance test results. The results indicate that T*-tree provides better performance for range queries compared to T-tree.
Index Terms:
database management systems; T*-tree; main memory database index structure; real time applications; indexing structure; rapid data access; binary tree; intrinsic binary search nature; pseudo-algorithms; rebalancing operations; performance test
Citation:
Kong-Rim Choi, Kyung-Chang Kim, "T*-tree: a main memory database index structure for real time applications," rtcsa, pp.81, Third International Workshop on Real-Time Computing Systems Application (RTCSA'96), 1996
Usage of this product signifies your acceptance of the Terms of Use.