Database Reference
In-Depth Information
Fig. 8.7
A set of nodes and keys arranged on the 32 node identifier space, and examples of the
finger tables. “Pre” is an abbreviation for “predecessor”
key is found. Let N and
x
be the objects in the object-oriented programing, which
respectively represent the current node and the next node. The node
x
is closer
to the predecessor node of the key than node N. The lookup operation contains
three functions as shown in Fig.
8.8
. At the current node, N, the “find closest
predecessor” function finds the closest predecessor of the key by searching N's
finger table. Searching uses the for-loop lookup table starting from the
m
-th row
down to 1. Once the closest predecessor is found, the next node,
x
is set to the
closest predecessor (i.e.,
x
). The “find predecessor” function checks if
the key is in between this node and its successor (i.e., key
=
finger
[
i
]
). If this
is true,
x
is the predecessor of the key. Otherwise, the procedure jumps back to the
first function to search for the closest predecessor again in the finger table of
x
(the
current node). Finally, the “find successor” function will take the predecessor ID
from the previous function and obtain the ID of the successor node of the key (i.e.,
x
∈
(
x
,
x
.
finger
[
1
])
).
An example of the lookup procedure is as follows. Assume that the current
node is N10 in Fig.
8.7
, and needs to find the responsible node for k = 22. Node
N10 searches its finger table, and the “find closest predecessor” function returns
N12. However, N12 is not the predecessor of k22 since k22
.
finger
[
1
]
.The
system then sets N12 as the current node to find the closest predecessor of k22.
This time the “find closest predecessor” function returns N20. Node N20 is in fact
the predecessor of k22 since k22
∈
(
N12
,
N20
]
. The “find predecessor” function
passes this information to the “find successor” function. The system then returns the
finger[1] of N20, which is N25, the successor of k22.
∈
(
N20
,
N25
]
Search WWH ::
Custom Search