RS-Tree: A Dynamic Index Structure

R-tree and its variants didn´t consider the relation between index records included in leaf nodes and storage locations in which index records are stored. Because of this reason, an index structure was designated as RS-tree in this paper. In RS-tree the index records of sequential storage locations in database files are distributed to the same leaf node or sequential leaf nodes, and the sequence of nodes of non-leaf layer is kept the same as the one of nodes of their children´s layer, which leads to the reduction of consuming time effectively that the database system spends in searching records during query. We have taken a series of experiments on a data set which consisted of 2219803 records. The experimental results show that during querying successively more than 1000 records test RS-tree´s speed is nearly 500 times faster than R-tree´s.