A New Multidimensional Point Access Method for Efficient Sequential Processing of Region Queries - Advances in Computational Science and Engineering - page 216

D D E E

entry A: 00,00, PTR7
entry B: 00,01, PTR8
entry C: 01,0, PTR9

entry A: 00,00, PTR7
entry B: 00,01, PTR8
entry C: 01,0, PTR9

G G

entry x: 0,0, PTR1
entry y: 0,1, PTR2
entry z: 1, - , PTR3

entry x: 0,0, PTR1
entry y: 0,1, PTR2
entry z: 1, - , PTR3

entry D: 00,1, PTR5
entry E: 01,1, PTR6

entry D: 00,1, PTR5
entry E: 01,1, PTR6

B B C C

F F

entry F: 1,0, PTR10
Entry G: 1,1, PTR11

entry F: 1,0, PTR10
entry G: 1,1, PTR11

A A

(b)

(a)

Fig. 7. An example of the MLGF-Plus

an additional field) and by some means of knowing the position of L in the page
containing L . For the former, we use a new additional filed, next neighbor page ID
field . For the latter, since the entry L has an entry having the smallest MGSFC
order value in the page containing the entry L ,theentry L is the first entry of
the page. So, no additional field is needed. This information must be maintained
always with dynamic changes of the MLGF-Plus. Figure 7(a) represents the MG
Z-order for the Figure 5(b) and Figure 7(b) shows its MLGF-Plus structure that
extends the original MLGF structure.
Our proposed algorithm of region query processing for the MLGF-Plus recur-
sively processes with all the entries in an SSS for each level, while the algorithm
for the MLGF [7,8,10,11,13] recursively processes with an entry for each level.
The former considers the adjacency relation of the entries, but the latter does
not. So the former has advantage of reducing the access number of directory
pages accessed for middle levels since all directory pages for the lowest level
pointed by an SSS can be processed at once. This is the advantage of the B + -
tree over the B-tree. But, our algorithm handles multiple SSSs for a given query
region rather than handling an SSS as the B + -tree.
If directory pages for an SSS are stored in a sector or adjacent sectors of the
disk, we can reduce the moving time of the disk head. Also, if all leaf pages
pointed by entries of a directory page corresponding to an SSS have similar
conditions, we have same effects.
If data pages storing objects pointed by the leaf pages that are pointed by
an SSS(i.e., multiple leaf directory pages) is physically adjacent(i.e., it means
the leaf pages are clustered by the MGSFC order value), we can have greater
advantages 3 . If objects are clustered with the MGSFC order value, we can process
region queries with similar time for any rectangle style of a query region since the

3 This method may be considered as an extension of the bulk loading method for
the MLGF [12] with using the Z-order in static environments. We can enhance the
performance of region query processing by using the MGSFC rather than considering
the Z-order. The fixed positioned object storing system, usually used in most DBMSs,
uses the concept of near object [8,9]. It tries to make the adjacent objects stored in the
same page in disk. If the MGSFC order values are used as a parameter of adjacency,
the performance of query processing can be enhanced.