Information Technology Reference
In-Depth Information
Theorem 8.13
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 run on the database db
.b/
under the key-range locking protocol. Then the
history
H
can be executed in time
O.
j
H
j
log N/
by a set of concurrent process threads, with one thread for each transaction,
resulting in a consistent and balanced B-tree
b
0
with
db
.b
0
/
D
H.
db
.b//;
where
j
H
j
denotes the length of
H
and
N
is the greatest number of tuples in any
database
H
0
.
db
.b//
,where
H
0
is a prefix of
H
.
Proof
In one such execution for the sequence of actions in history H , only one
action is in execution at a time, so that at any time, only the process thread is
active whose action is currently being executed, while the other process threads
are not executing any action, and hence are not holding any latches, meaning that
all the latches requested are granted immediately. Because history H is assumed to
be possible under the key-range locking protocol, then, by definition, all the locks
requested conditionally or unconditionally are granted immediately. The complexity
bound for the execution follows from Theorem
8.11
.
t
8.5
Redoing B-Tree Structure Modifications
In Sect.
4.11
we defined the concept of “selective redoing” and gave a generic
algorithm (Algorithm
4.18
) for redoing the effect of a structure modification
selectively on any of the pages involved in the modification. Now we can specialize
the generic redo algorithm for our five redo-only structure modifications defined
above.
The redo algorithm for page splits is given as Algorithm
8.10
. Observe here how
selective redoing works: to redo the effect of the split onto one of the pages involved,
only that page is latched, and the information therein plus the information contained
in the log record are used in the redoing. The other four redo algorithms are very
similar and are left to the exercises.
