Information Technology Reference
In-Depth Information
The partition-based key-range locking protocol of Sect.
10.2
is from Lilja et al.
[
2007
], who use it to protect bulk-delete actions on B-trees. They also present a
bulk-delete algorithm that avoids visiting leaf pages of subtrees whose tuples are all
deleted and instead detaches such subtrees from the B-tree. The partitioned B-tree
structure with an artificial leading key considered in Problem
10.8
is from Graefe
[
2003a
,
b
]. Logging and recovery techniques for partitioned B-trees are discussed by
Graefe [
2012
].
The complexity result of searching for a sorted set of keys as stated in
Lemma
10.13
is from Brown and Tarjan [
1980
]; Lemma
10.11
used in proving the
result is from Knuth [
1973
].
