I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a distinct key. We are looking for the value of each key (that is, $v(q _i)$. Noticing that, a set of keys $Q' \subset Q$ may have the same corresponding value [that is, for each $q _i, q _j \in Q' \subset Q, v(q _i) = v (q _j)$].

What is the minimum time complexity to search for the values of all keys in $Q$?

Can it be less then searching individually and sequentially for each $q \in Q$?

N.B: I noticed most research in this field considered sequential files. But what would the answer be if the files was indexed using hash table or B+-tree ?

Example: the database D can be a Domain Name Server .. the queries may be any number of url's ? url's are the keys and the value are the IP addresses .. Some URL's may have the same value ... for instance, google.com and goolgle.com returns the same IP ... [hypothetically]


1 Answer 1


It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values).

On the other hand, if we use a tree based data structure, we may be able to improve the run-time from the $k \cdot Q(n)$ time to perform $k$ queries that each individually take $Q(n)$ time. For example, if the keys are clustered closely together, and we use a finger-search tree. (See e.g. Brodal's chapter on finger search trees).

If you are dealing with sequential files, then Expressions for Batched Searching of Sequential and Hierarchical Files is a relevant reference.

If you are concerned with the I/O cost of accessing an external database, then perhaps the buffer tree is a more relevant reference.

  • $\begingroup$ That s very interesting Joe ! thanks ! - [the buffer tree reference is especially nice] $\endgroup$
    – AJed
    Mar 27, 2012 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.