Information Technology Reference
In-Depth Information
algorithm. In the
ARIES/KVL
and
ARIES/IM
algorithms [Mohan,
1990a
,
1996a
,
Mohan and Levine,
1992
], structure modifications are performed bottom-up, with
the help of a saved path and other clever techniques that avoid both deadlocks and
simultaneous write-latching of all the pages on the modification path. The “free-
at-empty” policy [Gray and Reuter,
1993
, Johnson and Shasha,
1993
] is applied,
allowing pages to become empty until they are detached from the B-tree and
deallocated.
In the
ARIES/KVL
and
ARIES/IM
algorithms, a structure modification interrupted
by a process failure or a system crash may have to be rolled back; the problem
associated with this and discussed in Sect.
8.6
was first observed by Mohan [
1990a
]
and Mohan and Levine [
1992
], who present a preventive approach (tree latch) as
a solution. Lomet [
1998
] also discusses the problem and presents an alternative
solution (two-phase undo pass) [Lomet,
1992
]. The interaction of search-tree
structure modifications and transactional access is also discussed by Sippu and
Soisalon-Soininen [
2001
].
The idea of performing structure modifications top-down appears in the B-tree
algorithms by Mond and Raz [
1985
]: using lock-coupling along the search path,
a traversal for an insert action splits in advance all full pages encountered, and
a traversal for a delete action merges or redistributes in advance all about-to-
underflow pages encountered. However, with these algorithms pages may be split
or merged unnecessarily even with fixed-length keys, unlike with our traversal
algorithms that use the saved path so as to shorten the search path and to avoid
unnecessary structure modifications in most cases. Moreover, the algorithms of
Mond and Raz [
1985
] do not include key-range locking or recovery.
TheB-linktree(Sect.
8.7
) was originally presented by Lehman and Yao [
1981
].
A generalization called the ǘ -tree was defined by Lomet and Salzberg [
1992
,
1997
].
The original motivation for the B-link tree was the claim that no latch-coupling
(actually lock-coupling) would be needed, so the tree could be traversed while
holding only a single page latched at a time. However, this imposes restrictions on
how pages emptied by delete actions can be detached and deallocated. Symmetric
treatment of insert and delete actions needs latch-coupling (or lock-coupling)
[Lanin and Shasha,
1986
]. A better motivation for the B-link tree is that structure
modifications can be defined as small redo-only operations that modify pages at a
single level only, thus both increasing concurrency and making recovery easier. This
property is shared by the Foster B-tree of Graefe et al. [
2012
].
The balance conditions of the tree are relaxed in the B-link tree algorithms of
Lehman and Yao [
1981
], Lanin and Shasha [
1986
], Lomet and Salzberg [
1992
,
1997
], and Lomet [
2004
], as well as in the Foster-B-tree algorithms of Graefe et al.
[
2012
], so that logarithmic search-path length is not guaranteed to be maintained
under all circumstances. Jaluta [
2002
] and Jaluta et al. [
2005
] present B-link-
tree algorithms in which deletions are handled uniformly with insertions, structure
modifications are redo-only, and the tree is kept in balance under process failures
and system crashes. These algorithms use no saved path; instead, latches of three
modes (read, write, update) are utilized. For ordinary B-trees, similar algorithms
