next up previous
Next: The Report Query Up: Algorithm Description Previous: Window Queries

The Exist Query

Consider a query over a specified window, where a search for the existence of features f$_i$, f$_j$, ... or f$_k$ has to be performed. For each maximal block, searching starts from the B$^+$tree root. Before descending the tree levels, each entry's bitstring is examined. If at least one bit corresponding to one of the queried features is set to 1, only then the respective subtree is followed; otherwise we skip to the next entry of the node. The same procedure is followed at the remaining tree levels; searching stops only when the leaf level is reached. However, in case of the BSL-trees it should be emphasized that two possibilities may arise when the leaf level is reached:

In the latter case, one more disk access may be needed to retrieve the previous or the next page of the reached leaf, where the ancestor or the descendant of the desired locational key may be stored, respectively. In case of the BHL-tree, it is certain that the searched maximal block will be located since all quadrants are stored, and by looking at its bitstring the question can be answered immediately gaining one disk access.


next up previous
Next: The Report Query Up: Algorithm Description Previous: Window Queries
Eleni Tousidou
2000-01-03