Lower bounds on batched query search

Question

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]

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.