Quintary trees: A file structure for multidimensional datbase sytems

Abstract

In this paper we present a fide structure designed for a database system in which four types of retrieval requests (queries) are allowed: exact match, partial match, range, and partial range queries. For a file of N records, each of k keys, the worst-case running times of our search algorithms are bounded above, respectively, by O(k + log N), O(t + 3k-(s + log N)), O(t + (log N)k), and O(t + 3k-s(log N)) where s is the number of keys specified in a partial match (or range) query and t is the number of records retrieved by the query. The fde structure can be built in O(N(log N)k/(k - l)!) time and requires similar storage; by a slight modification, both of these requirements can be reduced to O(N(log N)k-/(k - l)!). We also sketch outlines for inserting and deleting records that require O(k + (log N)k) time, on the average. This structure achieves faster response time than previously known structures (for many of the queries) at the cost of extra storage. © 1980, ACM. All rights reserved.