Next: The Report Query
Up: Algorithm Description
Previous: Window Queries
Consider a query over a specified window, where a search for the existence
of features f, f, ... or f has to be performed.
For each maximal block, searching starts from the Btree 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:
- the search is successful and the desired locational key (maximal block) has
been located,
- the search is unsuccessful, but searching continues for the ancestor or the
descendant of the desired locational key, since they correspond to larger or
smaller maximal blocks containing or contained in the desired maximal block.
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: The Report Query
Up: Algorithm Description
Previous: Window Queries
Eleni Tousidou
2000-01-03