Information Technology Reference
In-Depth Information
10.6
To save in the number of accesses to the log manager, it might be tempting to
log the insertion of a set S of tuples into B-tree leaf page p with a single redo-undo
log record of the form
h
T; I; p; S; n
0
i
and the deletion of a set S of tuples from
p with a single redo-undo log record
h
T; D; p; S; n
0
i
. But this would cause major
difficulties with our logging protocol. Explain.
10.7
Assume that a transaction scans a key range Œy;
z
by performing first the read
action RŒx
1
;
y;
v
1
and then repeatedly the read action RŒx
iC1
;> x
i
;
v
iC1
for
i
D
1;2;::: until x
iC1
exceeds
z
or reaches
1
,usingthe
read
calls of Sect.
6.7
.
Show that in the absence of concurrent updating transactions, the total number of
page latchings performed in all the
read
calls is
O.K
C
log N/;
where K is the number of tuples with keys in the scanned key range Œy;
z
and N is
the number of all tuples in the database.
10.8
A
partitioned B-tree
is an ordinary B-tree with an artificial leading key
attribute added. More specifically, if X is the key of the relation to be indexed,
the partitioned B-tree uses the key .P; X /, where the leading key attribute P takes
partition numbers
as values. Partition 0 is the regular partition in which most of the
tuples usually reside.
When a new bulk of tuples is to be inserted, a new partition number i>0is
reserved and the tuples .x;
v
/ from the bulk are inserted into the B-tree as tuples
.i; x;
v
/. This insertion is executed as part of the inserting user transaction. Later
when the transaction has committed, tuples in partitions i>0may gradually be
migrated to partition 0, using system transactions (redo-only structure modifica-
tions). Conversely, when a bulk of tuples is to be deleted, system transactions may
first be run to migrate the tuples to a new partition, which is then deleted as part of
a normal user transaction.
What are the obvious advantages and disadvantages of the partitioned B-tree for
bulk actions and single-tuple actions? Give a multi-granular locking protocol for
bulk-read, bulk-insert, and bulk-delete actions on the partitioned B-tree.
Bibliographical Notes
Several authors have developed algorithms for bulk operations on B-trees and
designed index structures specially tailored for bulk operations. Pollari-Malmi
et al. [
1996
] present an optimal bulk-insertion algorithm on B-tree indexes with
concurrency control and discuss its applications to full-text indexing. Mohan [
2002
]
presents a method for performing bulk deletes and updates in key-range scans on an
index, with additional predicates restricting the set of qualifying tuples; the method
minimizes the number of lock-table accesses needed when tuple-level key-range
locking is employed.
