Copyright © T. H. Merrett
308-420A Secondary Storage Algorithms and Data Structures Week 5
Assignment 5
Write a Java program which searches the telephone book represented as a
B-tree ( /course/cs420/data/btree ) for the telephone numbers 2740594, 4896311,
5222222, and 9377196. Hand in your program and its output.
The B-tree is homogenous and its nodes,
private byte[] node = new byte[NODESIZE];
have ORDER-1 80-byte data records and ORDER 4-byte pointers, where we set the
constants
public static final int ORDER= 19; //19 // constant: fanout
public static final int DATASIZE= (ORDER-1)*80; // constant: node data size
public static final int NODESIZE= DATASIZE + ORDER*4; // constant: node size
Each node has the form of an array of ORDER-1 records followed by an array of
ORDER pointers. You will have to deal with the buffering yourself. You will
probably be able to use the methods in class
bytechars to help with this.
The B-tree has been created in telephone number order, with the data slots in
each node sorted by telephone number.
The structure of each 80-byte record in node[DATASIZE] is, as in tbook,
name[40], address[33], phone[7].
Empty slots in a node are indicated by "~~~~~~~" in the phone postion of each
record. You may take this to be the highest possible ascii value, and so higher
than any telephone number.
The first four bytes of the file are occupied by a integer giving the block
number of the root node. Thus, this is a special first block, and the data
blocks, 0, 1, 2, .., are found at position 4 + blockno*NODESIZE, where
NODESIZE is the size of node.
The pointers in node, above, are node numbers: they are, for instance, the
source of the value in blockno, above. Null pointers have the value -1.
Second Part
Derive formulas for the minimum and maximum number of accesses
required to search an inhomogenous B-tree for a single record. Assume
n data nodes and index fanout of f.
Optional: change your program to use internet sockets via HostClient, as you
did with Assignment 1. Compare the running times. Try this from home.
*Shared marks for shared work*: assignments should be your own work; marks
for joint assignments will be divided by the number of collaborators.
But please feel free to work in groups to learn or for extra work that
is not for marks.