Information Technology Reference
In-Depth Information
Object-oriented indexing is normally implemented via a multi-level tree. We can
classify the possible implementation techniques into two general schemes: single-
class indexing and hierarchical indexing
[15]
. In the single-class scheme, multiple
multi-level trees are constructed, each representing one class. In this case, the leaf
nodes of each tree point to objects belonging only to the class indexed by that tree.
A query requesting all objects with a certain
id
has to navigate all these trees. On
the other hand, the hierarchical-based scheme constructs one multi-level tree repre-
senting an index for all classes. The same query has to only navigate the common
tree.
6 . 1
I n d e x i n g o n S i n g l e B r o a d c a s t C h a n n e l
Similar to a disk medium, an “
air-channel page
” can be assumed as the storage
granule on the air channel. Due to the sequential nature of the air channel, the allo-
cation of the nodes of a multi-level tree has to follow the navigational path used to
traverse the tree, starting at the root. Therefore, an ordering scheme should be used
to sequentially map the nodes on the air channel. Similarly, data objects are allocated
onto air channel pages following their index. Note that in either case, it is possible
to interleave and distribute the index pages and associated data pages in a variety of
methods (e.g., 1-
m
-or
distributed
indexing as suggested in
[38]
for a file indexed by
a B-tree).
6.1.1
Hierarchical Method
In this scheme, whether the domain of the query covers one class or all classes
along the hierarchy, the same index structure has to be traversed. Any request has
to probe the channel first, read one page, and get an offset to the first page of the
index. The modules of the mobile unit can then go into doze mode. Once the in-
dex is reached, the modules are brought back into active mode. A number of index
pages are read and offsets to the required objects are obtained. The offsets are fol-
lowed and the required objects are retrieved. In the interim between the retrieval
of objects, the modules are brought into doze mode. The protocol is shown be-
low.
Hierarchical Protocol
1) Probe onto channel and get offset to the next index
active
2) Reach the index
doze
3) Retrieve the required index pages
active
4) Reach the required data pages
doze
5) Retrieve required data pages
active
