Java Reference
In-Depth Information
10.2 Implement the 2-3
+
tree, that is, a 2-3 tree where the internal nodes act only
as placeholders. Your 2-3
+
tree should implement the dictionary interface of
Section 4.4.
10.3 Implement the dictionary ADT of Section 4.4 for a large file stored on disk
by means of the B
+
-tree of Section 10.5. Assume that disk blocks are
1024 bytes, and thus both leaf nodes and internal nodes are also 1024 bytes.
Records should store a 4-byte (
int
) key value and a 60-byte data field. Inter-
nal nodes should store key value/pointer pairs where the “pointer” is actually
the block number on disk for the child node. Both internal nodes and leaf
nodes will need room to store various information such as a count of the
records stored on that node, and a pointer to the next node on that level.
Thus, leaf nodes will store 15 records, and internal nodes will have room to
store about 120 to 125 children depending on how you implement them. Use
a buffer pool (Section 8.3) to manage access to the nodes stored on disk.
