fileorganization.txt

国外的数据结构与算法分析用书

                    File Organization

The main class of this cluster is BtreeFileUos. This class is a 
PKeyedBasicDictUos and so has the standard features of the basic 
dictionary class; namely, isEmpty(), insert(), delete(), has(), 
and obtain(). In addition, its main features include the 
following:
 - BtreeFileUos(int d, String  dataFileName, String nodeFileName, 
                int blockSize, int nodeSize): a constructor 
    with arguments to supply the key attributes for the file.  
    The arguments for this call are
        - d : the order of the B-tree associated with the file
        - dataFileName: the name/path of the data file
        - nodeFileName: the name/path of the node file
        - blockSize: the maximum number of bytes that will ever
          be needed for the storage of a block in the data file.
          A value of about 250 is needed when both the key and
          item have type int.  For types that require more
          bytes, larger values will be needed.
        - nodeSize): the maximum number of bytes that will ever
          be needed for the storage of an interior node in the
          data file.  A value of about 1250 is needed when the
          tree order is 1, and both the key and item have type
          int.  For a larger order and/or types that require
          more bytes, a larger value will be needed.

 - BtreeFileUos(String dataFileName): a creation procedure with 
    one argument to supply the name of an existing data file.  
    The other key attributes for the file are stored as the first 
    record of the data file.  This record is read in order to 
    obtain the attributes for the class.

 - closeFile(): a procedure to close the file.  It actually closes
    both the data file and the node file.

 - sequentialOut(): print out the values in the file in sequential 
    order, i.e., in increasing order by key.

 - serialOut(): print out the values in the file in the order that
    they are stored on disk.

 - order: the order of the B-tree associated with the file.


Associated with this class are two actual files, called the data
file and the node file.  The types for these files are classes
BtreeBlockFileUos and BtreeNodeFileUos, both of which extend class
ObjectFileUos. 

Now consider the contents of the data file, class 
BtreeBlockFileUos. As has already been stated, the first record 
of the data file is a header record which contains the main 
attributes of the file. This header record is an instance of the 
class BtreeFileHeaderUos.  After this header record, the data 
file consists of a sequence of blocks, i.e., instances of 
BtreeBlockUos.  Each block is an array of instances of the class 
BtreeRecordUos.  Each record consists of a Comparable key Object, 
and an item Object.  The size of the array is blockingFactor, 
where for this particular implementation, blockingFactor is the 
constant 3.

Associated with a B-tree file, there must be a B-tree.  The nodes 
for this tree are stored in the node file, class 
BtreeNodeFileUos.  Thus, the contents of this file is a sequence 
of objects of type BtreeInteriorUos. Each interior node has two 
arrays, a keys array of type Comparable and a childFileAddress 
array of type long. The keys array has size 2*order, and stores 
the keys of the interior node.  The childFileAddress array has 
size 2*order+1.  If the children of the node are not leaves, 
i.e., they are interior nodes, then each address of the address 
array is the address of the associated child node in the node 
file.  When the child node is needed for further processing, the 
data for the child node is read from the node file to form the 
interior node.  When the children of the node are leaves, then 
each address is the address of a block in the data file.  
Whenever the leaf node is needed, the information is read and the 
leaf node object is built.


 Possible exercises:

 1. Modify the classes so that the blocking factor can be varied.
 In particular, the blocking factor should be another argument
 when a file is create via the make instruction.

 2. The BtreeFileUos class is presently a basic dictionary.
 Extend the class so that it is a full dictionary, i.e., it inherits
 from PKeyedDictUos.  The key part of this assignment is
 the addition of the linear iterator capabilities to traverse the
 items in the data file in key order.

 3. An extension of B-trees is B+trees.  In a B+tree, each block
 has a reference to the next block in key order.  Thus, a
 sequential scan of the blocks in the data file can be done
 without using the B+tree or the node file.  Develop a descendant
 system that does this.  Use the B+ links in order to implement
 sequentialOut().  Optional, add an inheritance of the linear
 iterator and use the B+ links to iterate through the items in
 key order without using the node file.  Is it possible to update
 the item associated with a key, insert a new key-item pair, or 
 delete an item during such a traversal?