Java Reference
In-Depth Information
at most two disk fetches (internal nodes at level two and leaves at level three) are
required to reach the pointer to any given record.
A buffer pool could be used to manage nodes of the B-tree. Several nodes of
the tree would typically be in main memory at one time. The most straightforward
approach is to use a standard method such as LRU to do node replacement. How-
ever, sometimes it might be desirable to “lock” certain nodes such as the root into
the buffer pool. In general, if the buffer pool is even of modest size (say at least
twice the depth of the tree), no special techniques for node replacement will be
required because the upper-level nodes will naturally be accessed frequently.
10.6
Further Reading
For an expanded discussion of the issues touched on in this chapter, see a gen-
eral file processing text such as File Structures: A Conceptual Toolkit by Folk and
Zoellick [FZ98]. In particular, Folk and Zoellick provide a good discussion of
the relationship between primary and secondary indices. The most thorough dis-
cussion on various implementations for the B-tree is the survey article by Comer
[Com79]. Also see [Sal88] for further details on implementing B-trees. See Shaf-
fer and Brown [SB93] for a discussion of buffer pool management strategies for
B
+
-tree-like data structures.
10.7
Exercises
10.1 Assume that a computer system has disk blocks of 1024 bytes, and that you
are storing records that have 4-byte keys and 4-byte data fields. The records
are sorted and packed sequentially into the disk file.
(a) Assume that a linear index uses 4 bytes to store the key and 4 bytes
to store the block ID for the associated records. What is the greatest
number of records that can be stored in the file if a linear index of size
256KB is used?
(b) What is the greatest number of records that can be stored in the file if
the linear index is also stored on disk (and thus its size is limited only
by the second-level index) when using a second-level index of 1024
bytes (i.e., 256 key values) as illustrated by Figure 10.2? Each element
of the second-level index references the smallest key value for a disk
block of the linear index.
10.2 Assume that a computer system has disk blocks of 4096 bytes, and that you
are storing records that have 4-byte keys and 64-byte data fields. The records
are sorted and packed sequentially into the disk file.
(a) Assume that a linear index uses 4 bytes to store the key and 4 bytes
to store the block ID for the associated records. What is the greatest
