|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
B-trees support member queries and updates using log_B N/M disk accesses (or I/Os) for each operation. A well-known lower bound states that for comparison based index structures, queries cannot be done with fewer I/Os in the worst case. The question we study here is to what extent the number of I/Os for updates can be improved, possibly at the cost of slower queries. More specifically, we study trade-offs between the update time and the query time for comparison based external memory dictionaries. Our main results are two lower bound trade-offs between the number of I/Os for member queries and insertions. In detail, the lower bounds are: If N>M insertions perform at most δ*N/B I/Os, then (1) there exists a query requiring N/(M*(M/B)O(δ)) I/Os, and (2) there exists a query requiring Ω(log(N/M)/log(δ log2N) I/Os when delta is O(B/log3N) and N is at least M2. For both lower bounds, we also present data structures with matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges. Among the data structures is a variant of B-trees where for any e>0, the number of I/Os for updates can be improved by a factor of B1-e (compared to standard B-trees), while the number of I/Os for queries is a factor 1/e worse (compared to standard B-trees). A value such as e=1/4 could be a practically interesting choice. This is joint work with Gerth Stølting Brodal.
SDU HOME | IMADA HOME | Previous Page Last modified: May 10, 2004. Joan Boyar (joan@imada.sdu.dk) |