Java Reference
In-Depth Information
number of records that can be stored in the file if a linear index of size
2MB 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 4096 bytes
(i.e., 1024 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.3 Modify the function
binary
of Section 3.5 so as to support variable-length
records with fixed-length keys indexed by a simple linear index as illustrated
by Figure 10.1.
10.4 Assume that a database stores records consisting of a 2-byte integer key and
a variable-length data field consisting of a string. Show the linear index (as
illustrated by Figure 10.1) for the following collection of records:
397
Hello world!
82
XYZ
1038
This string is rather long
1037
This is shorter
42
ABC
2222
Hello new world!
10.5 Each of the following series of records consists of a four-digit primary key
(with no duplicates) and a four-character secondary key (with many dupli-
cates).
3456 DEER
2398 DEER
2926 DUCK
9737 DEER
7739 GOAT
9279 DUCK
1111 FROG
8133 DEER
7183 DUCK
7186 FROG
(a) Show the inverted list (as illustrated by Figure 10.4) for this collection
of records.
(b) Show the improved inverted list (as illustrated by Figure 10.5) for this
collection of records.
10.6 Under what conditions will ISAM be more efficient than a B
+
-tree imple-
mentation?
