Information Technology Reference
In-Depth Information
There exist more efficient index structures for versioned data than the basic B-
tree organization discussed here. One of the more sophisticated index structures,
called the
multiversion B-tree
, can be considered optimal in that a bulk-read action
as in Theorem
12.13
can be performed for any database version asymptotically
as efficiently as with a B-tree that contains only the tuples of version .Here ,the
version to be read, can be any version equal to or earlier than the start time of the
transaction.
12.8
Update Transactions on Versioned B-Trees
In this section we discuss the implementation of read, insert, and delete actions in
update transactions running at transaction-level read consistency, when the physical
structure of the database is a versioned B-tree. As explained in Sect.
12.3
, commit-
duration locks are used to protect these actions. The locking protocol used is an
adaption of key-range locking to a transaction-time database.
In executing a read action RŒx;
z
;
v
in an update transaction T , we scan keys
x in ascending order starting at the least key x with x
z
. First, the procedure call
find-pages-for-read
.P;
z
/ is used to locate and read-latch the set P of leaf pages
that contain the versioned tuples with the least key x with x
z
. The commit-time
table is read-latched, the set of records for the transactions that created the versioned
tuples with key x is retrieved from the commit-time table, and the table is unlatched.
Among the committed versioned tuples .x; T
0
;
v
0
/, if such tuples exist, the one with
the greatest commit time is determined. Also the tuple .x; T
00
;
v
00
/ created by some
active transaction, if one exists, is determined. Note that because of X-locking, at
most one such tuple .x; T
00
;
v
00
/ may exist at a time. Here T
00
may be T or some
other update transaction.
We have to consider the following cases:
1. .x; T
00
;
v
00
/ exists and T
00
6D
T .Thenkeyx is currently X-locked by T
00
.All
latches are released, x is unconditionally S-locked, and the search for the correct
key is restarted when the lock is granted.
2. .x; T
00
;
v
00
/ exists and T
00
D
T and
v
00
6D?
.ThenT itself holds an X lock on x;
the tuple .x;
v
00
/ is returned.
3. .x; T
00
;
v
00
/ exists and T
00
D
T and
v
00
D?
.ThenT itself has deleted x;we
release all latches and move to the key next to x.
4. .x; T
00
;
v
00
/ does not exist but .x; T
0
;
v
0
/ with
v
0
6D?
exists. If T holds a lock on
x, then the tuple .x;
v
0
/ is returned. Otherwise, key x is conditionally S-locked;
if the lock is granted, the tuple .x;
v
0
/ is returned—otherwise, all latches are
released, x is unconditionally S-locked, and the search for the correct key is
restarted when the lock is granted.
5. .x; T
00
;
v
00
/ does not exist but .x; T
0
;
v
0
/ with
v
0
D?
exists. Then the current
version of the tuple with key x is committed and deleted. If T holds a lock on
x, we release all latches and move to the key next to x; otherwise, all latches are
