Information Technology Reference
In-Depth Information
redistributes in all, are performed in the worst case. When the merge path goes along
the rightmost side of the tree, performing a merge on the youngest sibling requires
that first the youngest sibling is unlatched (so as to avoid deadlocks), then the next
elder sibling is latched, and then the youngest sibling is latched again, thus adding
the count of latches by h
1.
t
Theorem 8.11
The time complexity of performing a read action
RŒx;
z
;
v
,an
insert action
IŒx;
v
, a delete action
DŒx;
v
, an undo-insert action
I
1
Œx;
v
,
or an undo-delete action by the procedures read
.T;x;
z
;
v
/
,inser
.T; x;
v
/
,
delete
.T; x;
v
/
, undo-insert
.n;T;p;x;n
0
/
, and undo-delete
.n;T;p;x;
v
;n
0
/
,using
the B-tree algorithms above, is
O.log N/
,where
N
is the total number of tuples
in a database indexed by a consistent and balanced B-tree, provided that (1) no
update action or structure modification triggered by any transaction other than
T
is in progress at the same time and that (2) the locks requested for the action are
granted immediately without wait.
Proof
The theorem follows from Lemmas
7.3
,
7.6
,
7.8
,
7.10
,
7.12
,and
8.10
.
Provisions (1) and (2) together exclude the possibility of repeated traversals for
page splits or merges or for locating the target page for the action and the keys to be
locked.
t
Theorem 8.12
Let
b
be a consistent and balanced B-tree and let
H
be any history
of forward-rolling, backward-rolling, committed, and rolled-back transactions that
can be executed on
b
using the above algorithms. Then
H
is possible under the
key-range locking protocol, and the execution results in a consistent and balanced
B-tree
b
0
with
db
.b
0
/
D
H.
db
.b//;
that is, the logical database indexed by
b
0
is the database produced by running
H
on the database indexed by
b
.
Proof
That H is possible under the key-range locking protocol follows from the
facts that the read, insert, and delete algorithms in Sect.
6.7
follow the rules of the
key-range locking protocol and that the traversal algorithms in Chap.
7
correctly
locate the data page covering the key to be read, inserted, or deleted and the data
page holding the key next to the key to be inserted or deleted. The consistency
and balance of the B-tree b
0
follows from Lemma
8.5
. Finally, the fact that the
logical database indexed by b
0
is the database produced by H on the database
indexed by the initial B-tree b follows from the correctness of insert and delete
algorithms in Sect.
6.7
, the undo-insert and undo-delete algorithms in Sect.
4.3
,the
traversal algorithms in Chap.
7
, and the structure-modification algorithms in this
chapter.
t
