                      FIXED-ORDER B-TREE SOURCE CODE V1.1
                                by Bryan Flamig

                                  README FILE
                                September 27, 1993

                      Copyright(c) 1993 Azarona Software
                             All rights reserved.

      *****************************************************************
       NOTE: THIS IS V1.1, (FTREE.ZIP) which is the original version 
       (BLFBTR.ZIP) modified to remove all the template code, due to 
       too many problems with too many compilers. The previous version 
       had no version number, so consider it as Version 1.0. Also, V1.1 
       fixes a couple of minor or not-so-minor bugs.
      *****************************************************************


INTRODUCTION
============

This is source code in C++ for implementing disk-based B-trees, based on
Chapter 14 of the book "Practical Data Structures in C++", by Bryan 
Flamig, (John Wiley & Sons, ISBN 0-471-55863-X). 

B-trees are multi-way search trees that are the quintessential method
of choice for creating indexes for databases. Not only does the code
given here show you how to implement B-trees, it also shows you many
advanced C++ techniques, such as:

    1. File-based objects
    2. Smart pointers to file-based objects
    3. Reference counted objects
    4. Construction of objects anywhere in memory using an
       overloaded new operator
    5. Construction of objects residing on disk (!) using an
       overloaded new operator
    6. Multiple inheritance
    7. Templates (THIS HAS BEEN REMOVED DUE TO TOO MANY 
       COMPILER PROBLEMS)

There are tricks in this code that, as far as I know, have 
not been published anywhere else, such as a clean and elegant 
way of implementing pointers to objects stored on files as
though they were in memory.

If you like what you see, you may be interested in picking up a
copy of the "Practical Data Structures in C++" book, since it is
chock-full of examples like this. 

Also, later on in this readme file, there is an order form where you 
can order source code to a more sophisticated B-tree implementation
-- one that implements variable-order nodes with variable-length 
keys, and allows iterative navigation through the tree.


COPYRIGHTED SOFTWARE
====================

The source code is copyrighted by Azarona Software, but I'm
providing it to you free of charge. You are free to experiment
with the code, include it in your own applications, personal
or commercial. HOWEVER, YOU MAY NOT DISTRIBUTE THE SOURCE CODE
FOR A PROFIT OR FEE OF ANY KIND WITHOUT THE EXPRESS WRITTEN 
PERMISSION OF AZARONA SOFTWARE.

You are granted permission to give away the source code to
friends, upload the files to a BBS, etc., AS LONG AS NO FEE 
IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE 
DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES, 
THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT. 
You may "zip" the files into a single-file archive, if you wish.


SOURCE CODE PROVIDED AS-IS
==========================

Azarona Software provides this source code as-is. USE THE
SOFTWARE AT YOUR OWN RISK. While the software has been tested
extensively, we make no representations about its suitability 
or robustness, and do not take any liability for the use of
the software.


FEATURES OF THIS SOURCE CODE
============================

The source code as provided implements three major tools that are
useful for working with objects stored on disk:

   1. A file-manager class called Fmgr. The Fmgr class manages
      data in files, and provides heap-like facilities for allocating
      and freeing data on disk, as well as low-level facilities
      for fetching and storing data.

   2. A Least-Recently-Used (LRU) caching mechanism that buffers
      objects stored on disk temporarily in memory. Unique to this
      design is a form of smart pointer called Cached-Object Pointers
      (Coptrs) invented by the author. Coptrs allow you to work with
      file-based objects using (almost) normal pointer syntax. You
      can even cause an object to be allocated in a file, and then
      construct it, using an overloaded new operator!

   3. Finally, the B-tree class, which allows you to create search
      trees stored on disk. As you might expect, this class uses
      the other two tools as part of its implementation.


WHAT COMPILERS YOU MAY USE
==========================

The code was developed using BC++ 3.1, and was tested with the
latest Cfront compiler in Unix as well. The code uses many 
sophisticated C++ features, all of which are legal C++
as defined in the C++ Annotated Reference Manual, (the "ARM", 
currently the de facto standard reference for C++). Unfortunately,
some current compilers won't be able to handle what's given
here. Most of the problems are due to the template code. (I use
templates in some "strange" ways, that many compilers complain
about.) This will become less of a problem as time goes on, and
the compilers "catch up" to the standard.

BUT BECAUSE OF THE TEMPLATE PROBLEMS, WE'VE TAKEN OUT THE TEMPLATE
SYNTAX ALTOGETHER, FOR V1.1.


BUG FIXES
=========

The main difference between V1.0 and V1.1 is the removal of the
template syntax. Also, there are three bug fixes to the btree.cpp
source file. Two of these fixes are due to BC++ 3.1 compiler bugs,
when inline functions are turned on. The other bug is of my own
doing, in the Insert() routine. This bug prevented btree's of
order less than 4 from working correctly. To see these bug fixes, 
search the btree.cpp source file for the string "BUG FIX".

Also, I changed the way Coptr's are passed to insert and delete
routines, passing them by reference rather than by value. This
will lead to a more efficient implementation, bypassing some
Coptr constructor calls. I don't recall why I had passed these
by value, I probably had a reason once. It seems to work fine
when the Coptr's are passed by reference. If you encounter
problems, try going back to pass-by-value. If that corrects
the problem, please contact Azarona Software about this.

ALSO: Some of the low-level files, coptrb.cpp, cacheb.cpp, fmgr.cpp,
etc. have been slightly altered from what is in the book. The 
functionality is the same, I just tweaked them a little. Also, these
files are now the same versions as are supplied in the VTREE
Toolkit. When in doubt, use the versions given in the VTREE Toolkit.


DESIGN OF THE B-TREE CLASS
==========================

The Btree class implements B-trees of fixed order, that is, each
node has a maximum fixed number of entries. Each entry has a
a null-terminated key and a 32-bit field for data, (usually this 
is an offset to the actual data stored elsewhere, perhaps in a 
separate file).

Obviously, you may want different types of keys, and you may want
to store the data right in the entry itself. It wouldn't take too
much to modify the Btree class and associated data structures to
do this, but as given, we've "hard-coded" the Btree class to use
the aforementioned entry structure. (This means any changes you
make the Mnode will force a recompile, and the Btree class only
supports one type of Mnode at a time.)

The order of the tree and the maximum key length are defined as
constants. To change the order or maximum key length, you must
change the constants and recompile. Obviously, a more general
purpose way of specifying these attributes without recompiling
would be nice. The variable-order B-tree class which you may
purchase has this ability. But what's given here is enough to
allow you to learn the basics of B-trees.


SOURCE CODE DOCUMENTATION
=========================

The source code as given is fully described in the "Practical Data
Structures in C++" book. Here we provide documentation only in the
form of comments in the code. (The code is heavily commented, 
though.)


SAMPLE TEST PROGRAM
===================

The sample test program, btreet1.cpp, provides an example of
creating and accessing a filed-based B-tree. The program shows
the basic operation such as creating a B-tree file, adding keys,
searching for keys, and deleting keys. The program provides a
"testing harness" for the B-tree design by employing a "regression
test", that is, it inserts random keys into a Btree and then
deletes and searches for random keys. You can control the seed
to the random number generator to repeat the exact same test, and
you can control how many keys will be added.

You can also control how much the program prints out, via the
two flags verbose and auto. verbose = 1 (default) prints out
a lot of info as the test proceeds, verbose = 0 prints only
minimal information. With auto = 1, (the default), the test 
proceeds w/o any pauses, with auto=0, the program pauses
between each major step and asks you to continue.

There are some command-line options to help out:

Usage: btreet1 -n nnn -p -q sssss

   -n nnn   Specifies how many keys to add during testing.
            Maximum is 1000, default is 512

   -p       Sets "pause" mode, (auto = 0) where the user
            is prompted between each major pass. Default is 
            auto = 1

   -q       Sets quiet mode, (verbose = 0), where little
            information is printed out. Default is verbose = 1.

   sssss    Seed to use for random number generator. Default
            seed is based on clock. You can set the seed to
            a specific number to run exactly the same test
            as was run before, perhaps where an error was
            detected. NOTE: No '-' precedes this option,
            just list the number.


THE VARIABLE-ORDER BTREE (VTREE) TOOLKIT
========================================

For $20, you may purchase an extended version of the B-tree class
given here, defined in a class called Vtree. The Vtree class allows
entries to have variable-length keys, with as many as possible packed
into a node, (and thus, the nodes are variable-order.) You can specify
the maximum size of a key, and the size of the B-tree nodes, at runtime, 
when constructing the B-tree object. In contrast, the Btree class
requires you to specify these at compile-time, and you must recompile
all the code when a change is made to either parameter.

In addition, rather than using recursive routines for searching,
inserting, and deleting, an explicit stack is used. Special 
"iterator" style functions are provided to go backwards and forwards
through the entries in a B-tree, in sorted order.

In short, the Vtree class is closer to what you might actually use
in applications such as phone lists, customer lists, etc.

Complete source is provided in the toolkit, as well as an on-line,
hypertext-based manual that explains the "public" interface to the
Vtree class, as well as gives design notes and tips. A utility is
provided to print this hypertext manual to a printer.


ORDERING THE VTREE TOOLKIT
==========================

You may order the VTREE toolkit by printing the order.frm file
given in this distribution, filling it out, and sending it to
Azarona Software.


PACKING LIST
============

This distribution (V1.1) should contain the following files:

BTREE.CPP          Btree class implementation file
BTREE.H            Btree class header file
BTREET1.CPP        Test program for the Btree class
BTREET1.MAK        Make file (BC++ 3.1) for the test program
BTREET1.PRJ        Project file (BC++ 3.1) for the test program
BUCKETB.H          Header file for the Bucketb base class
CACHEB.CPP         Implementation file for the Cacheb base class
CACHEB.H           Header file for the Cacheb base class
COPTRB.CPP         Implementation file for the Coptrb base class
COPTRB.H           Header file for the Coptrb base class
COUNTOBJ.H         Header file for the CountedObject class
EXCHDLR.CPP        Implementation file for the exception handler class
EXCHDLR.H          Header file for the exception handler class
FMGR.CPP           Implementation file for the Fmgr (file manager) class
FMGR.H             Header file for the Fmgr (file manager) class
FMGRPTR.H          Header file for the Fmgr Smart Pointer class
MNODE.CPP          Implementation file for the Mnode (multi-way node) class
MNODE.H            Header file for the Mnode (multi-way node) class
MNODEPTR.H         Header file for the Mnode smart pointer, bucket, 
                   cache, and Coptr classes.
ORDER.FRM          Order form for ordering the Vtree Toolkit
PLACENEW.H         Header file for the placement new operator
README             This readme file


ABOUT THE PRACTICAL DATA STRUCTURES BOOK
========================================

Practical Data Structures in C++
       by Bryan Flamig
      John Wiley & Sons
      ISBN 0-471-55863-X

If you're looking for an eminently readable data structures book
written for C++, you've come to the right place. The book covers
data structures from a practical point of view, with clearly
explained examples and segments of usable code. For the topics
covered, there are no mysteries left to the reader to unravel:
you won't have to spend days trying to figure out how to accomplish
something described in this book. For example, some books talk about
red-black trees, splay trees, and B-trees, but neglect to show you how
to delete entries from these trees! In this book, each operation of
these data structures is fully explained and laid out. And since 
complete code is provided on the accompanying disk, you can put the
code to work immediately. This book:

  * Presents high-quality code, very carefully designed and
    crafted specifically for C++, with efficiency and elegance
    a top priority.

  * Makes extensive use of C++ templates, the first book of its
    kind to do so.

  * Covers concrete data types, abstract data types, resizable
    arrays, smart pointers, strings, vectors, matrices, linked
    lists, stacks, queues, binary trees, red-black trees, splay
    trees, file-based objects, caching and B-trees.

  * Includes several techniques never before published, such as
    template-based vector pointers and cached-object pointers, 
    and in-place construction of array elements.

The programming techniques shown in this book were crafted spec-
ifically for C++, and the code given is not simply a rewrite of
code written in C, Pascal, or some other language. Each data
structure discussed in the text and demonstrated on disk has
been designed to take advantage of the special features of C++.

If C++ is you language of choice, Practical Data Structures in C++
will show you the most effective and practical ways to store data.


ABOUT THE AUTHOR
================

Bryan Flamig is a software developer and consultant specializing in
C++ programming. He is the author of numerous books, including the 
popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented
Programming with Turbo C++", and of course, the author of "Practical
Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training 
seminars focusing on C++. You may reach Bryan at:

Azarona Software
P.O. Box 768
Conifer, CO  80433

(303) 697-1728 Fax
73057,3172     CompuServe
bflamig        bix
