Rogue Wave banner
Previous fileTop of DocumentContentsIndex pageNext file
Essential Tools Module User's Guide

11.4 RWBTreeOnDisk

Class RWBTreeOnDisk has been designed to manage a B-tree in a disk file. The class represents an ordered collection of associations of keys and values, where the ordering is determined internally by comparing keys. Given a key, a value can be retrieved. Duplicate keys are not allowed.

Keys are arrays of char. The key length is set by the constructor. The ordering in the B-tree is determined by comparing keys with an external function, which you can change.

The type of the values is:

The values typically represent an offset to a location in a file where an object is stored. Given a key, you can find where an object is stored and retrieve it. As far as class RWBTreeOnDisk is concerned, however, the value has no special meaning -- it is up to you to interpret it.

The class RWBTreeOnDisk uses class RWFileManager to manage the allocation and deallocation of space for the nodes of the B-tree. You can use the same RWFileManager to manage the space for the objects themselves if the B-tree and data are to be in the same file. Alternatively, you could use a different RWFileManager, managing a different file, to store the B-tree and data in separate files.

The member functions associated with class RWBTreeOnDisk are similar to those of the in-memory class RWBTreeDictionary, except that keys are arrays of char rather than RWCollectables. There are member functions to add a key-value pair, remove a pair, replace a value associated with a key, query for information associated with a key, operate on all key-value pairs in order, return the number of entries in the tree, and determine if a key is contained in the tree.

11.4.1 Construction

An RWBTreeOnDisk is always constructed from an RWFileManager. If the RWFileManager is managing a new file, then the RWBTreeOnDisk will initialize it with an empty root node. For example, the following code fragment constructs an RWFileManager for a new file called filename.dat and then constructs an RWBTreeOnDisk from it:

11.4.2 Example

In this example, key-value pairs of character strings and offsets to RWDates representing birthdays are stored. Given a name, you can retrieve a birthdate from disk.

Here is the line-by-line description:

//1 Construct a B-tree. The default constructor is used, resulting in a key length of 16 characters.
//2 Read the name from standard input. This loop exits when EOF is reached.
//3 Read the corresponding birthday.
//4 Allocate enough space from the RWFileManager to store the birthday. Function binaryStoreSize() is a member function in most Rogue Wave classes. It returns the number of bytes necessary to store an object in an RWFile. If you are storing an entire RWCollection, or using one of the methods recursiveSaveOn() or operator<<(RWFile&, RWCollectable), be sure to use recursiveStoreSize() instead.
//5 Seek to the location where the RWDate will be stored.
//6 Store the date at that location. Most Rogue Wave classes have an overloaded version of the streaming operators << and >>.
//7 Insert the key and offset to the object in the B-tree.

After you store the names and birthdates on a file, you can retrieve them like this:

Here is a description of the program:

//1 The program accepts names until encountering an EOF.
//2 The name is used as a key to RWBTreeOnDisk, which returns the associated value, an offset, into the file.
//3 Check to see whether the name was found.
//4 If the name is valid, use the value to seek to the spot where the associated birthdate is stored.
//5 Read the birthdate from the file.
//6 Print it out.

With a little effort, you can easily have more than one B-tree active in the same file. This allows you to maintain indexes on more than one key. Here's how you would create three B-trees in the same file:

And here is how you could open the three B-trees:

Previous fileTop of DocumentContentsIndex pageNext file

©2004 Copyright Quovadx, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Quovadx, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.