Information Technology Reference
In-Depth Information
The records-redistribute modification is performed by the procedure call
records-
redistribute
.p;q;x
0
;q
0
/, where the page-ids p, q,andq
0
are given as input
parameters (Algorithm
8.5
). The precondition for this modification is that the parent
page p and its child pages q and q
0
are write-latched, q
0
is the next younger sibling of
q, and there are enough records in q and q
0
so that they can be distributed between q
and q
0
such that neither page will be about to underflow. The modification is logged
with the redo-only log record
n
Wh
records-redistribute
;p;q;x
0
;q
0
;V;d
i
;
(8.5)
where V is the set of records that were moved, x
0
is the least key in page q
0
after
moving the records, and d is a bit that indicates the direction (q
!
q
0
or q
q
0
)
into which the records were moved. The
LSN
n of the log record is stamped in the
P
AGE
-LSN
fields of pages p, q,andq
0
. The pages p, q,andq
0
all remain write-
latched.
Algorithm 8.5
Procedure
records-redistribute
.p;q;x
0
;q
0
/
if
page q contains more records than its younger sibling page q
0
then
move some records from the upper half of page q to page q
0
else
move some records from the lower half of page q
0
to page q
end if
V the set of records moved
d the direction (q ! q
0
or q q
0
) into which the records were moved
x
0
the least key of the records in page q
0
change the key to x
0
in the index record for child page q
0
in the parent page p
log
.n;h
records-redistribute
;p;q;x
0
;q
0
;V;di/
P
AGE
-LSN.p/ P
AGE
-LSN.q/ P
AGE
-LSN.q
0
/ n
Lemma 8.5
Assume that a set of concurrent tree-height increases, page splits,
tree-height decreases, page merges and records redistributes (Algorithms
8.1
-
8.5
), inserts into and deletes from leaf pages (Algorithms
3.1
and
3.2
), and
undoings of inserts and deletes (Algorithms
4.8
and
4.10
) by different process
threads are executed. Assume further that such threads are run on an initially
consistent and balanced B-tree in such a way that for each operation the
pages involved are write-latched and the precondition for the operation is
satisfied at the start of the operation and the pages involved are unlatched
at
the
end
of
the
operation.
Then
the
resulting
B-tree
is
consistent
and
balanced.
Proof
From the algorithm for each operation mentioned in the lemma, it is seen
that if the precondition for the operation is satisfied at the time, the operation
