Information Technology Reference
In-Depth Information
Algorithm 1.
process region query
Input:
Q
1:
level
= 0 // root level
2: Set the cursor of an entry chain of the root level as the first entry of the root level
entry chain.
3:
while
(1)
do
4:
if
generate next sub sequenceset(
Q, level, start entry, end entry
) returns null
then
5: break
6:
else
7: process below subsequenceset(
Q, level
+1
,startentry, end entry
)
8:
end if
9:
end while
Algorithm 2.
generate next sub sequenceset
Input:
Q, level
Output:
start entry, end entry
1: Find the first entry that intersects with
Q
from the current entry cursor position
of the level to the next entries of the entry chain
,
and set the entry as
start entry
.
2:
if
there exists no such entry in the entry chain
then
3: return null
4:
end if
5: Find the entry that does not intersect with
Q
and set
last entry
as the entry
previous to this entry
,
and set the current entry cursor position of
level
as the
entry next to this entry.
6: return
Algorithm 3.
process below subsequenceset
Input:
Q, level, s entry, e entry
1:
if
the level is a leaf directory
level
+1
then
// data page level
2: Read the data page pointed by
s entry
and check the objects in the page whether
they satisfy the query and do the same thing for the data pages pointed by the
chain to the
e entry
3:
end if
4: Read the directory page pointed by
s entry
.
5: Set the first entry of this directory page as the current cursor position of
level
.
6:
while
(1)
do
7: Find the first entry that intersects with
Q
from the current entry cursor position
of level and following the entry chain
,
and set the entry as
start entry
.
8:
if
there exists no such an entry in the entry chain
then
9: return
10:
end if
11: Find the entry that does not intersect with
Q
and set
last entry
as the entry
previous to this entry
,
and set the current entry cursor position as the entry next
to this entry.
12: process below subsequence set(
Q, level
+1
,startentry, end entry
)
13:
end while
Search WWH ::
Custom Search