# B-tree Example Program

Topics
Overview | Compiling

Overview

The B-tree test program is a console-based program used to build a dictionary of 34,472 words using the B-tree class. This program is presented to demonstrate the speed of tree insertion and search operations using the balanced disk-based tree class. NOTE: A similar example is presented using an unbalanced disk-based tree class in the "dtree" directory. The D-tree example is so slow that it may take days to build the dictionary as opposed to the B-tree example which takes up to one minute or more to build. The following is a list of some build times on various machine architectures. Each benchmark is listed by the number of seconds it took to build the entire dictionary. Benchmarks vary according to the processor speed, the number of processors, and the type of hard drive used (IDE, fast SCSI, fast-wide SCSI, etc.)

- Intel 486 DX75 (single processor, IDE): 265 seconds
- Intel Pentium 200 (single processor, IDE): 53 seconds
- Sparc 20 server (dual 75mhz RISC processors, fast SCSI): 21 seconds
- HP 800 server (dual 100mhz PA-RISC processors, fast-wide SCSI): 16 seconds.

When the test program is executed for the first time, it will build the dictionary using a text file named "amerdict.txt" located in the "diction" directory. A B-tree index file named "amerdict.btx" will be created. WARNING: The "amerdict.btx" uses 5,500,368 bytes of disk space. If necessary, press Control-C to interrupt the build process after the test program is executed.

After creating the dictionary file, the test program will display a menu and give you a ">" prompt. At the prompt, enter the letter of an operation you wish to perform.

    (A) Add a word to the dictionary
    (F) Find a word in the dictionary
    (L) List the entire contents of the dictionary
    (H) Help (prints this menu)
    (P) Print the tree node by node
    (R) Remove a word from the dictionary
    (T) Display Btree stats
    (V) Display VBD file stats
    (Q) Quit
    (X) Dump the entire dictionary

Enter "H" to display this menu again, after the program processes your selection.

Compiling the Test Programs

Four makefiles are provided in the "console" directory to compile the source code on one of four different compilers.

    "msvc40.mak"  - Makefile for Microsoft visual C/C++ 4.2
    "djgpp.mak"   - Makefile for DJGPP gcc 2.7.2.1
    "gnu_gcc.mak" - Makefile for GNU g++ 2.7.2.1
    "hpux10.mak"  - Makefile for HPUX C++ A.10.24

Building the Executable:

To compile use the "make -f" option followed by the makefile name. To compile using MSVC use the "nmake -f" option. The resulting executable will be named after the name set by the PROJECT macro in the makefile. By default the test program will be named "testprog" under UNIX or "testprog.exe" under Windows 95/DOS.

Removing the Object Files, the Executable, and the Index File:

To remove the object files, the executable, and the dictionary file use the "make -f" option followed by the makefile name, followed by "clean": make -f hpux10.mak clean

Under MSVC use the "nmake -f" option followed by the makefile name, followed by "clean": nmake -f msvc40.mak clean

End Of Document