Information Technology Reference
In-Depth Information
Fig. 10.2
Bulk-inserting the
tuples of S into leaf page p.
The least key y
0
in the next
page p
0
may be among the
next keys that must be
IX-locked for short duration
left-to-right order determined by the partition hierarchy. The locks are then acquired
in this order.
Next the sorted sequence of tuples to be inserted is scanned, with the tuple
variable .x;
v
/ denoting the first not-yet-inserted tuple in the sequence. The leaf
page p that covers key x is located and write-latched and as many tuples that
fit into page p are inserted into it, and the next keys of the inserted keys
that are not covered by the already locked fragments are IX-locked for short
duration, again using conditional locking. Then the tuple variable .x;
v
/ is advanced
to the tuple next to the last inserted tuple in the sequence of tuples to be
inserted.
Given a tuple .x;
v
/
2
s
XV
, the call
find-page-for-bulk-insert
.p;h;p
0
;x;
v
/
traverses the B-tree and determines the leaf page p that covers key x, the high-key
h of p, the page p
0
next to p (if any), write-latching p, and read-latching p
0
.The
call also arranges, with appropriate structure modifications, that page p has room at
least for the tuple .x;
v
/.Ifnonextpagep
0
exists (i.e., h
D1
), then p
0
D
p.The
algorithm for the call is similar to Algorithm
7.8
.
In the algorithm, S denotes the subsequence of the sorted sequence of tuples to be
inserted into page p. The keys in
keys
.p/ are next keys to be locked that immediately
follow some key in
keys
.S / in the merged sequence of tuples from page p and set S .
Also, the least key y
0
in the next page p
0
is a next key to be locked if the last tuple in
the merged sequence is a tuple from S (Fig.
10.2
). Moreover,
1
is a next key if no
next page p
0
exists. The call
insert-bulk-into-page
.T;p;S/(Algorithm
10.4
)isused
to insert the tuples in S into page p and to log the insertions with the redo-undo log
records (
3.9
).
