Information Technology Reference
In-Depth Information
write onto a new disk location, readily contributes to a feasible implementation on a
flash-memory-based
SSD
. Although some updates still remain to be in-place, so that
an updated page goes into its old logical page address and hence must be mapped
by the
FTL
to its new physical address, it is expected that the
FTL
remains moderate
in size, so that a page-level mapping can be used. Naturally, garbage collection of
relocated pages whose logical page identifiers change remains as the responsibility
of the database system software.
Similar arguments of suitability for implementation on flash memory can be
stated about the other structures discussed in this chapter. In a merge tree of
Fig.
15.1
, the merge process that merges the B-trees C
i
and C
iC1
to produce the
B-tree C
0
iC1
uses sequential reads to scan C
i
and C
iC1
and sequential writes to
create C
0
iC1
. In a log-structured database, the log part of the database fits perfectly
to flash-memory implementation.
Problems
15.1
Modify the B-tree loading algorithm suggested in Sect.
8.8
so as to apply
sequential writes. Recall that the group of pages to be written sequentially must
reside at consecutive addresses.
15.2
Consider the structure modifications on the B-tree of Fig.
7.1
needed to
accommodate an insertion, resulting in the B-tree of Fig.
8.8
, or a deletion, resulting
in the B-tree of Fig.
8.9
. Assume that the B-tree is maintained as a write-optimized
B-tree. Assuming that all parent links are correct initially (which is rare in practice),
which of the parent links turn incorrect due to the structure modifications and which
are updated to correct values?
15.3
In the original design of the write-optimized B-tree, the parent links are
only maintained as main-memory addresses between the buffer-control blocks of
buffered B-tree pages. Work out the maintenance of such linking.
15.4
Explain how read actions RŒx; >
z
;
v
, insert actions IŒx;
v
, delete actions
DŒx;
v
, undo-insert actions I
1
Œx;
v
, and undo-delete actions D
1
Œx;
v
are per-
formed on a relation r.X;V/implemented as a merge tree, when key-range locking
is applied.
15.5
Elaborate the algorithm that merges disk-resident components C
i
and C
iC1
(i>0) and creates the component C
0
iC1
using the method of Problem
15.1
.
15.6
Explain how a read action RŒx; >
z
;
v
is performed on a committed version
of a transaction-time log-structured database. Also explain how the update actions
IŒx;
v
and DŒx;
v
and their undo actions I
1
Œx;
v
and D
1
Œx;
v
are performed,
under snapshot isolation.
15.7
Assume a database that consists of several relations, some of which have a
log-structured organization, possibly with a main-memory index, and the others
