Information Technology Reference
In-Depth Information
using redo-only structure modifications are presented by Jaluta et al. [
2003
] (without
saved paths) and by Jaluta et al. [
2006
] (for page-server systems, with saved paths).
Jaluta and Majumda [
2006
] present a technique for implementing B-tree page
allocations and deallocations as redo-undo modifications separate from redo-only
page-splits and page-merges in such a way that every page that remains allocated
after recovery from a failure is guaranteed to be part of the B-tree, even though the
failure occurred between page allocation and page split or between page merge and
page deallocation. The technique thus enhances concurrency while eliminating the
need for garbage collection for pages that are allocated but not part of the B-tree (cf.
Problem
8.5
).
Compression techniques for B-trees, such as prefix truncation (see Problem
8.3
),
and their effect on B-tree algorithms are discussed by Bayer and Unterauer [
1977
],
Lomet [
2001
], and Graefe [
2011
], among others. Recovery and concurrency-
control algorithms for multidimensional index structures have been presented by
Evangelidis et al. [
1997
] (for hB
ǘ
-trees), Kornacker et al. [
1997
] (for generalized
search trees), and Haapasalo et al. [
2013
] (for ordinary R-trees), among others.
Recovery techniques for B-trees are surveyed by Graefe [
2012
].
