Information Technology Reference
In-Depth Information
overhead of maintaining references within the index structure, such as parent-to-
child links pointing to relocated child pages in a B-tree.
A straightforward solution to the problem of maintaining references to relocated
pages is to use logical page identifiers that do not change in page relocation. A
logical page-id can be regarded as identifying a logical page on a virtual device.
A logical page that is currently in use (i.e., as a part of some physical database
structure) is mapped to a physical page on a concrete device, that is, a database
disk. Relocating a page then involves an update on this logical-to-physical page
mapping, but the page references within a database structure need not be changed.
Naturally, the logical-to-physical page mapping must be part of the permanent
database, and hence reads and updates on it must be protected by latching. When a
set of modified pages is to be flushed from the buffer onto disk, the pages are fixed
and write-latched, the pages covering the relevant parts of the logical-to-physical
page mapping are fixed and write-latched, a consecutive area on disk is allocated,
the modified pages are taken to that area, and the page mapping is updated so as to
reflect the new locations of the flushed pages.
The previous disk versions of the relocated pages remain in their locations, but
they can no longer be located through the current logical-to-physical page mapping.
Those pages are called shadow pages of the now current pages; together with
appropriate checkpointing, the shadow pages can be used to recover an earlier
version of the database, and, if at least logical log records have been written for
updates on the data tuples, the current version of the logical database that existed
at about the time of the crash can be reconstructed. Indeed, some early database
management systems relied heavily on shadow paging, rather than write-ahead
logging, in implementing restart recovery. The logical-to-physical mapping is an
essential part of log-structured file systems , which improve write performance by
replacing a set of small writes by a single large write.
Logical-to-physical mappings are also part of some modern devices such as
solid-state drives or SSD s, which are based on flash memory . Flash memory does not
tolerate in-place updates on pages. The space occupied by a page on flash memory
can be rewritten only after an entire block of many pages containing that page is first
erased, involving an expensive operation. Thus, modified pages are always flushed
onto free page addresses in previously erased blocks, and only when no such address
is available, an erase operation is invoked to free a block of previously written pages
that are no longer used (i.e., are not among the currently mapped physical pages).
The logical-to-physical mapping is maintained as part of a structure called the flash-
translation layer or FTL .
15.3
Write-Optimized B-Trees
In this section we consider a B-tree variant called the write-optimized B-tree ,which
incorporates online page relocation without the overhead of maintaining a logical-
to-physical page mapping. When a modified B-tree page is to be flushed from the
Search WWH ::




Custom Search