home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / cprog / btree.zip / BTREE.DOC < prev    next >
Text File  |  1992-02-16  |  40KB  |  1,092 lines
  1.  
  2.                  L.A. Walker & Co. B+Tree in C++
  3.  
  4.                    Copr. 1991 Larry A. Walker
  5.                      Larry A. Walker & Co. 
  6.                         736 Watford Ct. 
  7.                        Sterling Va. 22170
  8.                         15 February 1992
  9.  
  10. Email:
  11. Larry A. Walker, 71116,615
  12.  
  13.                         REFERENCE MANUAL
  14.  
  15.  
  16. Introduction
  17.  
  18.           Those of you who have fixed ideas about B+Trees and C++
  19. you may wish to skip directly to the License section of this
  20. document, and, deciding upon your agreement with the terms, get
  21. on with using or experimenting with the B+Tree that accompanies
  22. this text file.  If you are interested in a few historical notes
  23. and opinionated views, the introduction may offer some interest.
  24.  
  25.           What is a B+Tree and why use C++?
  26.  
  27.           Some years ago, while working at a small computer
  28. consulting firm in Northern Virginia it fell on me to create a
  29. full text retrieval system for the Department of the Army,
  30. specific to a single full text database.  I won't go into any
  31. particulars about this system accept to say that it eventually
  32. led to our own planned system for a text retrieval system. 
  33. Naturally, any full text system is entirely dependent on its
  34. indexing and is only as good as its indexes are good, no matter
  35. what other text searching algorithm it implements.
  36.  
  37.           Therein is where my study of B+Trees began.  I has soon
  38. learned that a Binary Tree, which we had used in the Army system,
  39. was insufficient for any but the most simple indexing
  40. requirements.  Only B-Trees and B+Trees seemed to have the power
  41. necessary to support the requirements of a system needing
  42. hundreds of thousands of keys.  The full text system project died
  43. when the company I worked for was bought by a larger company, but
  44. the lessons I learned did not, and have proven to be especially
  45. useful in other projects.
  46.  
  47.           One of the most unexpected lessons was that when
  48. purchasing a B-Tree from a vendor, the cost of the B-tree had
  49. little to do with how it performed.  After years of collecting
  50. and testing, I had found one that was one of the most expensive
  51. and commercially packaged didn't really work at all.  One  that
  52. cost a mere $35 outperformed all the rest.
  53.  
  54.           When much later I finally decided on a project for my
  55. own company to produce as a saleable program, each product
  56. defined naturally seemed to be based on a B-Tree.  The B-Trees
  57. which I had written were either the property of a company or
  58. their client and didn't match my specifications anyway.  B-Trees
  59. can be purchased, but even the best did not seem to live up to
  60. expectations of performance or requirements of licensing.  So,
  61. the first phase of product development was to produce a B-Tree.
  62. Since the development effort is far behind schedule, and for
  63. various other reasons, I have decided to release the index as its
  64. own product.   
  65.  
  66.           Exactly what is a B-Tree?  Definitions of B-Trees are
  67. about as consistent as the definitions for structured
  68. programming.  That allows me, like anyone else to supply my own
  69. definition which may also not be totally consistent with some
  70. other "expert".  For the purposes of this introduction I will
  71. define a binary tree, B-Tree, and B+Tree in the text that
  72. follows.  Specific types or modifications of each are not
  73. discussed as I view them as relatively unimportant in comparison
  74. with a basic definition.  I also depend on the reader to have at
  75. least a limited general understanding of the B-Tree concept.  The
  76. B+Tree supplied with this text is, after all, a tool for
  77. programmers who already recognize their need for an index and are
  78. interested in incorporating it into their program. 
  79.  
  80.           A binary tree is a collection of information into
  81. nodes, so that beginning at the "root node" if the information
  82. item or key can not be found in the current that node, one can
  83. branch to one of either two nodes.  One node who's keys are all
  84. of a lesser value than all of those items in the current node,
  85. and one who's keys are all of a greater value than all of those
  86. items in the current node.  In this way one can proceed from the
  87. root node in either of two directions, either encountering the
  88. key sought, or reaching a "leaf node" which has no more branches. 
  89. It is customary that a key be attached to a value that can be
  90. translated into an address pointing to the record which the key
  91. indexes.  The additional act of balancing a binary tree, keeping
  92. as many keys in each direction from a node, is difficult but in
  93. practical use necessary.  There are algorithms in both general
  94. use, and proprietary algorithms, which actually accomplish this
  95. balancing act to a lesser or greater extent.
  96.  
  97.           A B-Tree or Btree is similar to a binary tree in that
  98. it is also a hierarchial collection of keys in nodes beginning
  99. with a root node.  Each key of a B-Tree has its own pointer,
  100. pointing to another node containing the next order of keys of
  101. higher value than the pointing key.  The node itself then must
  102. contain an extra key, pointing to a node containing the order of
  103. keys of lesser value than the first key in the node.  Keys
  104. inserted from outside the tree are only inserted into leaf nodes. 
  105. If a leaf node is full at the time of an insert, the leaf is
  106. split, and the center key inserted upward into a parent.  If the
  107. parent does not exist the key becomes the key of a new root node. 
  108. In this way the tree is balanced, in that the number of nodes
  109. left and right are always equal.  
  110.  
  111.           A B+Tree is a special instance of the B-Tree in that
  112. left and right sibling nodes are combined during underflow
  113. yielding a more evenly distributed tree.  Borrowing from parents
  114. of the key positioned between the left and right siblings and
  115. propagating this forward to the root node creates a condition
  116. where the tree height is decreased as a root node is completely
  117. depleted with the combined node borrowing takes its place.  When
  118. I refer to B-Trees I usually am referring to B+Trees since almost
  119. all B-Trees are implemented as B+Trees.
  120.  
  121.           The following statements are sometimes given in
  122. reference to B-Trees and are incorrect.
  123.  
  124.           The B-Tree is a special instance of the binary tree. 
  125. Not true.  The indexing goal and the hierarchial ordering of
  126. nodes is the only commonality between binary trees and B-Trees. 
  127. At first glance, this could seem like a lot.  It's not.  The same
  128. commonality can be given about a lot of other things.  Binary
  129. trees and B-Trees are separate distinct indexing algorithms.  I
  130. wouldn't be surprised if some enterprising individual in the
  131. future develops another wholly new indexing idea based on this
  132. hierarchial concept, and is that is neither a B-Tree or a binary
  133. tree.
  134.  
  135.           B-Trees were designed to order fixed length keys.  The
  136. B-Tree definition has no bearing on the type or definition of the
  137. key itself.  The definition of the key including fixed or
  138. variable length is implementation independent.
  139.  
  140.           B+Trees require pointers to sibling nodes.  B+Trees
  141. should never have pointers to sibling nodes.  Some early
  142. implementations which may have used such pointers clearly
  143. couldn't see the forest through the trees.  
  144.  
  145.           Keys in B-tree branch nodes only have pointers to other
  146. nodes.  Only keys in leaf nodes contain data.  Incorrect.  This
  147. is one of those minor variations that prove to be uninteresting.
  148.  
  149.           So why C++?
  150.  
  151.           Well, some time ago one of AT&T's programmers visited
  152. on us his ideas of what an object oriented language extension to
  153. C should look like.  I can't really attack him for what he has
  154. done, because I don't believe he ever intended it to be what it
  155. has become.  What it looks like to me is more of a personal
  156. invention to solve his own personal programming problems, but,
  157. now it is here in its present form for all of us anyway.  I think
  158. that if he had thought it was being done with every programmer in
  159. mind it would be somewhat different.  But, for one reason or
  160. another, the idea has been latched on to and - you had better
  161. believe - has become a permanent part of our programming lives.  
  162.  
  163.           If you are a C programmer not using C++, you need to
  164. become a C++ programmer.  There really isn't all that much to it,
  165. and C++ has been around long enough that there are now some ok
  166. tutorials available.  My advice is to forget Stroustrump's own
  167. book.  It isn't worth the price and I never pick it up.
  168.  
  169.           Learn the entire C++ extension, but use only what you
  170. need.  For example, I don't mind if another programmer chooses to
  171. use the C++ streams class that Stroustrump provided as a example
  172. of class programming.  I rarely ever do myself, because it
  173. provides absolutely no increase in functionality or anything else
  174. beyond the standard C library functions and therefore is simply
  175. not needed.  Sometimes I calloc() sometimes I "new", that depends
  176. on what I am doing and how much control I need.  I cannot say
  177. that because C++ provides an alternative I dismiss everything
  178. else any more than I dismissed assembly language when C came
  179. along.
  180.  
  181.           Some things are effective when done in C++ vs. C.  A 
  182. B+Tree class has some advantages over a B-Tree in C.  See the
  183. example code to see how it works.  In a higher level requirement
  184. like windowing - especially with a GUI - C++ classes have
  185. tremendous advantages over any C only implementation I've seen. 
  186.  
  187.           So, here we have it now, on my word, that a B+Tree is a
  188. properly implemented as a class of C++.  Never-the-less, I am
  189. also making available a version of the same tree written in C,
  190. mostly based on the fact that C++ is not available everywhere the
  191. tree may be needed.
  192.   
  193.           One of the more readable books which include
  194. descriptions of how B-Trees are built is "Programs and Data
  195. Structures in C" by Leendert Ammerall, by John Wiley & Sons Ltd.
  196.  
  197.  
  198. Disclaimer:
  199.  
  200. The Larry A. Walker & Co. B+Tree software, utilities and manual
  201. is provided "as is" and is without express or limited warranty of
  202. any kind by either Larry A. Walker & Co. or anyone who has been
  203. involved in the creation, production, or distribution of the
  204. software, including, but not limited to the implied warranties of
  205. merchantability and fitness for a particular purpose.  The entire
  206. risk as the quality and performance of the software and user
  207. manual is with you.  Should the software and user manual prove
  208. defective, you assume the entire cost of all necessary servicing,
  209. repair or correction.  Use of the software constitutes agreement
  210. to these provisions.
  211.  
  212. Licensing:
  213.  
  214.  
  215.           Non-registered users are granted a limited license to
  216. use this product, and to copy the program for trial use by others
  217. subject to the following limitations:
  218.                Any copy is distributed unmodified form, complete
  219. with documentation.
  220.                No fee, charge or  other consideration is
  221. requested or accepted.
  222.                This product is not used in conjunction with and
  223. distributed as a part of any other product.
  224.  
  225.           If you want to license the source code for this product
  226. for personal use, you can do so by sending $45 to:
  227.  
  228.                Larry A. Walker & Co.
  229.                736 Watford Ct.
  230.                Sterling Va 22170
  231.  
  232.           You will receive a disk which contains the latest
  233. version of the product, manuals and source.  For an additional
  234. $10, you can receive a printed version of the manual.  The manual
  235. which accompanies the source contains the same information as
  236. contained in this distribution, makefiles, and additional
  237. information about other built in capabilities.  You cannot
  238. distribute or sell the source.  A personal use license is
  239. provided on a one person one license basis.  I don't care how
  240. many copies of the source you make, but it is for your personal
  241. use only.  If someone else wants it, tell them to order their own
  242. copy.
  243.  
  244.           If you intend to use the B+Tree in conjunction with a
  245. product you are distributing, you will need to obtain a
  246. developer's license.  A developers license is $450.  A developers
  247. license includes a diskette containing all the latest source, one
  248. printed copy of the manual, with any additional copies of the
  249. manual requested at $10 per copy.  A developers license allows
  250. you to use the source, modify the source, compile the source for
  251. inclusion with your programs, and distribute the compiled objects
  252. with your programs.  You cannot distribute the source code in
  253. either its original or modified versions.  Additionally, you will
  254. receive regular updates of any new version of the source made
  255. available for distribution to run on DOS for a period of two
  256. years.   You will receive a discount for purchase of any version
  257. developed for other operating environments (i.e. it is likely I
  258. will provide a version for Unix in both standard C and for AT&T
  259. cfront, since this is where I use it myself.  If you are
  260. interested in it now, write me a letter.). A developers license
  261. is provided as a one cpu one license basis.  For multiple
  262. developers copies purchased at the same time, the price is $50
  263. less for each subsequent copy, but no less than $300.
  264.  
  265.           If you have a product you are building and have
  266. specifications you wish a custom btree designed for, contact me
  267. for a cost estimate.
  268.  
  269.           Product support for Individual Licenses is provided by
  270. mail and email through my compuserve id.  You will be provided
  271. with my business number, but since my primary business is Unix
  272. consulting, it will of course take precedence over any telephone
  273. support which will be on an as available basis.
  274.  
  275.           Please note that the prices in this document are
  276. subject to change without notice.  If the date of this document
  277. is over 6 months old, ask for the current registration costs from
  278. me by email through my compuserve id.
  279.  
  280. Runtime System:
  281.  
  282.           The B-Tree runtime system consists of the Runtime Error
  283. Handler class, Block File Handler class and the Btree class. 
  284. Btree class is a derived class of Block File Handler class.  The
  285. Block File Handler class is a derived class of the Runtime Error
  286. Handler class.  The Runtime Error Handler provides the necessary
  287. reporting and report control mechanisms to control internal
  288. errors.  The block file handler provides the necessary block file
  289. io for the B+Tree file structure.
  290.  
  291. C++ RunError   Runtime Error Handler Class
  292.  
  293.           System header:
  294.                #include "dbfiles.hpp"
  295.           Class header:
  296.                #include "BFH.hpp"
  297.  
  298.           Class object file name (MSDOS)
  299.                runerr.obj
  300.  
  301. Public data:
  302.  
  303.           NONE
  304.  
  305. Member functions:
  306.  
  307.           RunError()
  308.  
  309.                Purpose:
  310.  
  311.                     Class Constructor
  312.  
  313.                Syntax:
  314.                     RunError <object_name>;
  315.  
  316.                Discussion:
  317.                     The RunError constructor provides
  318. initialization of the functionality.  The display destination is
  319. initially set to stdout and the switch for display of errors is
  320. turned off.
  321.  
  322.                Example:
  323.                     RunError error_handler;
  324.  
  325.           ~RunError()
  326.  
  327.                Purpose:
  328.                     Class Destructor
  329.  
  330.           set_display();
  331.  
  332.                Purpose:
  333.                     Turns the display of errors on and off, and
  334. stores a destination for the display of errors.
  335.  
  336.                Syntax:
  337.                     <object_name>.set_display( int onoff,
  338.                                         FILE* <destination>);
  339.  
  340.                Discussion:
  341.                     The destination of errors can be changed at
  342. any time and the display of general errors can be suppressed or
  343. switched on at any point in the program.  Note that this does not
  344. control errors which are marked as fatal.  The display of fatal
  345. errors cannot be suppressed, and is always to stderr.
  346.  
  347.                Return value:
  348.                     NONE.
  349.  
  350.                Example:
  351.                     error_handler.set_display(ON,stderr);
  352.  
  353.           set_log();
  354.  
  355.                Purpose:
  356.                     Turns the logging of errors on and off, and
  357. stores a destination for the logging of errors.
  358.  
  359.                Syntax:
  360.                     <object_name>.set_log( int onoff,
  361.                                         char* <destination>,
  362.                                         int append);
  363.  
  364.                Discussion:
  365.                     Logging of errors can be turned ON or OFF,
  366. with the calling program providing the destination file name and
  367. the switch designation for appending or truncating any log
  368. already at that name destination.  If a log is already open at
  369. the time a call to open an new log is made, the old log is
  370. closed.  The default for the append parameter is ON.
  371.  
  372.                Return value:
  373.                     NONE.
  374.  
  375.                Example:
  376.                     error_handler.set_display(ON,
  377.                                         "test.log",
  378.                                         ON );
  379.  
  380.           proc_error();
  381.  
  382.                Purpose:
  383.                     Process errors being reported to the error
  384. handler.
  385.  
  386.                Syntax:
  387.                     <object_name>.proc_error (int state, 
  388.                                         int line,
  389.                                         char * file,
  390.                                         char * string, 
  391.                                         int exit_code);
  392.  
  393.  
  394.                Discussion:
  395.                     The function processes the errors being
  396. logged into the error handler.  Depending on the switches which
  397. are in effect, the proc_error function may report the error to
  398. the display and/or to a log file.  If the level of the error is
  399. fatal, the error will be reported to stderr and exit will be
  400. called with the provided exit code.
  401.                     The parameters consist of the state which is
  402. at present either WARNING or FATAL.  The lin of the error is
  403. usually reported through the the preprossor __LINE__ mechanism. 
  404. The file is usually reported through the preprossor __FILE__
  405. mechanism.  The string is any statement you want attached to the
  406. error.  The exit code is required only if a fatal error is being
  407. called.
  408.                     A macro is included in bfh.hpp which is used
  409. internally for the btree reporting procedures.  You might want to
  410. procuce macros similar to warning() and fatal() which require
  411. only a message string and provide the remaining parameters. 
  412. Naturally your macro would require the addition of the instance
  413. name of the error handler class.
  414.  
  415.                Return value:
  416.                     NONE
  417.  
  418.                Example:
  419.                     error_handler.proc_error (WARNING,
  420.                                         __LINE__, 
  421.                                         __FILE__,
  422.                                         "Couldn't open file",
  423.                                         1);
  424.  
  425.  
  426. C++ BFHClass  Block File Handler Class
  427.  
  428.           System header:
  429.                #include "dbfiles.hpp"
  430.           Class header:
  431.                #include "BFH.hpp"
  432.  
  433.           Class object file name (MSDOS)
  434.                BFH.obj
  435.  
  436. Public data:
  437.  
  438.           NONE
  439.  
  440.  
  441. Member functions:
  442.  
  443.           BFHClass();
  444.  
  445.                Purpose:
  446.                     Class constructor.
  447.  
  448.                Syntax:
  449.                     BFHClass <object_name>;
  450.  
  451.                Discussion:
  452.                     The BFHClass constructor provides
  453. initialization functionality only.  File open and close is
  454. executed through separate functions in the class.
  455.  
  456.                Return value:
  457.                     NONE
  458.  
  459.                Example:
  460.                     BFHClass block_handler;
  461.  
  462.           ~BFHClass() 
  463.                Purpose:
  464.                     Class Distructor.
  465.  
  466.  
  467.           OpenBFH()
  468.  
  469.                Purpose:
  470.                     The OpenBFH function opens a file.  If the
  471. file already exists, it retrieves a structure of data that was
  472. stored there by derived class objects and retreives its own data
  473. structure containing the status information at the time of the
  474. last file close.  Given a creation key and the block size for a
  475. new file, it will create a new disk file. 
  476.  
  477.                Syntax:
  478.                     <object_name>.OpenBFH( char* <file name> ,
  479.                                            void* <info struct> ,
  480.                                            int <info size>,
  481.                                            int <create key>,
  482.                                            int <file block size>)
  483.  
  484.                Discussion:
  485.                     
  486.                Return value:
  487.                     Returns the defined value SUCCESS or aborts
  488. the program on failure.
  489.  
  490.                Example:
  491.                     int status;
  492.                     status = block_handler.OpenBFH(index_name,
  493.                                           (void *) &trunk,
  494.                                           sizeof(struct Trunk),
  495.                                           create,
  496.                                           TreeBlockSize ); 
  497.  
  498.  
  499.           int BFHClose();
  500.                Purpose:
  501.                     Close a file previously opened by BFHOpen().
  502.  
  503.                Syntax:
  504.                     <object name>.BFHClose();
  505.  
  506.                Discussion:
  507.                     BFHClose closes the file and truncates all
  508. empty blocks which fall at the end of the file.  The file must be
  509. manually closed.
  510.  
  511.                Return value:
  512.                     Returns the integer defines as SUCCESS.
  513.  
  514.                Example:
  515.                     int status;
  516.                     status = block_handler.BFHClose();       
  517.            
  518.           int WriteBlock();
  519.  
  520.                Purpose:
  521.                     Write data block to the file.
  522.  
  523.                Syntax:
  524.                     <object name>.WriteBlock( char *<data block>,
  525. long <file address>);
  526.  
  527.                Discussion:
  528.                     Function writes the block at the pointer to
  529. the file at the address.
  530.                     
  531.                Return value:
  532.                     Returns the defined values for SUCCESS or
  533. FAILURE.
  534.                Example: 
  535.                     int status;
  536.                     status = WriteBlock( ptr, blockaddr );
  537.  
  538.           int ReadBlock();
  539.  
  540.                Purpose:
  541.                     Retreive a data block from the file.
  542.  
  543.                Syntax:
  544.                     <obect name>.ReadBlock(char *<data block>,
  545. long<file address>);
  546.                Discussion:
  547.                     Function retreives the block at the address
  548. into the data area addressed by the pointer.
  549.  
  550.                Return value:
  551.                     Returns the defined values for SUCCESS or
  552. FAILURE.
  553.                Example:
  554.                     int status;
  555.                     status = ReadBlock( ptr, blockaddr);
  556.  
  557.           long NewBlock();
  558.  
  559.                Purpose:
  560.                     To acquire a new data block in the open file.
  561.  
  562.                Syntax:
  563.                     <object name>.NewBlock();
  564.  
  565.                Discussion:
  566.                     This function is used to acquire new space in
  567. the data file.  If a free block in the file exists, it will be
  568. removed from the free list, and its address returned.  If no free
  569. blocks are available, a new block will be added to the file.
  570.  
  571.                Return value:
  572.                     Address of the new block, or -1L on failure.
  573.  
  574.                Example:
  575.                     long address;
  576.                     address = NewBlock();
  577.  
  578.           int FreeBlock(long);
  579.  
  580.                Purpose:
  581.                     To release a block.
  582.  
  583.                Syntax:
  584.                     <object name>.FreeBlock( long <file
  585. address>);
  586.  
  587.                Discussion:
  588.                     Submitting the block address to FreeBlock
  589. releases the block to the free list.  During a close, if this
  590. block is found to be at the end of the file, it can be releases
  591. to the system.
  592.  
  593.                Return value:
  594.                     Returns the defined value for SUCCESS or
  595. FAIL.
  596.  
  597.                Example:
  598.                     int status;
  599.                     long block;
  600.                     block = release_block; // block address being
  601.                                            // released
  602.                     status = block_handler.FreeBlock( block );
  603.  
  604.           long AddrBlock();
  605.  
  606.                Purpose:
  607.                     To calculate the address of a block providing
  608. only the number of the block in the file.
  609.  
  610.                Syntax:
  611.                     <object name>.AddrBlock( long <block_number>
  612. );
  613.  
  614.                Discussion:
  615.                     This function can provide the address given
  616. the number of the block in the file.  Useful for stepping through
  617. the file sequentially.
  618.  
  619.                Return value:
  620.                     Returns the long value for the block in the
  621. file, or a -1L on failure.
  622.  
  623.                Example:
  624.                     long address;
  625.                     long block = 2L; // third block in file
  626.                     address = block_handler.AddrBlock( block );
  627.  
  628.           int FullBlock();
  629.  
  630.                Purpose:
  631.                     To determine if a designated block in the
  632. file is empty or full
  633.  
  634.                Syntax:
  635.                     <object_name>.FullBlock( long );
  636.  
  637.                Discussion:
  638.                     This function takes the block address and
  639. examines the block to determine if it is marked full or empty and
  640. returns the information.
  641.  
  642.                Return value:
  643.                     Returns 1 for full, 0 for empty.
  644.  
  645.                Example:
  646.                     block_handler.FullBlock( next_block );
  647.  
  648.           void get_info ();
  649.  
  650.                Purpose:
  651.                     Retreives a copy of the class information
  652. structure bfh_data, and places a copy of the structure at the
  653. address provided by the passed pointer
  654.  
  655.                Syntax:
  656.                     <object_name>.get_info(struct bfh_data *);
  657.  
  658.                Discussion:
  659.                     User access to the data
  660.  
  661.                Return value:
  662.                     None
  663.  
  664.                Example:
  665.                     struct bfh_info;
  666.                     block_handler.get_info( & bfh_info );  
  667.           int GetBFHSize();         
  668.  
  669.                Purpose:
  670.                     Allow program access to block size in use.
  671.  
  672.                Syntax:
  673.                     <object_name>.GetBFHSize();
  674.  
  675.                Discussion:
  676.                     Allows program access to block size defined
  677. when the block file was created.
  678.  
  679.                Return value:
  680.                     Integer value representing the block size.
  681.  
  682.                Example:
  683.                     block_size = block_handler.GetBFHSize();
  684.  
  685.           OpenState();
  686.  
  687.                Purpose:
  688.                     To determine the state of the file handled by
  689. the block file handler
  690.  
  691.                Syntax:
  692.                     OpenState();
  693.  
  694.                Discussion:
  695.                     Since the file is opened and can be closed
  696. before the destructor is called, the open state of the file could
  697. be in question.  OpenState provides outside access to determine
  698. of the class currently has a file open.
  699.  
  700.                Return value:
  701.                     Returns SUCCESS if the file is open and FAIL
  702. if the file is closed.
  703.  
  704.                Example: 
  705.                     int status;
  706.                     status = block_handler.OpenState();
  707.  
  708.  
  709. C++ BtreeClass      B+Tree Class
  710.  
  711.           System header:
  712.                #include "dbfiles.hpp"
  713.           Class header:
  714.                #include "Btree.hpp"
  715.  
  716.           Class object file name (MSDOS)
  717.                btree.obj
  718.  
  719. Public data:
  720.  
  721.           NONE
  722.  
  723. Parent Class:
  724.           BFHClass
  725.  
  726. Member functions:
  727.  
  728.           Btree();
  729.           
  730.                Purpose:
  731.                     Constructor.  Opens a block file and prepares
  732. a btree for access.
  733.  
  734.                Syntax:
  735.                     Btree( char * name, int create, int
  736. type_of_key, int duplicates_allowed, int
  737. size_of_fixed_length_keys )
  738.                
  739.                Discussion:
  740.                     This constructor creates an instance of the
  741. Btree class.  The name passed is the name of the index file.  The
  742. standard application of this constructor is to provide only the
  743. name of the index for already established trees, or all
  744. parameters for new trees.  If parameters beyond name are provided
  745. and the tree exists, the create parameter must be passed as 0 or 
  746. the class will fail and abort the program.  If the program is
  747. uncertain about the existance of the tree, the program is
  748. responsible to verify the existance of the index file before this
  749. consctuctor can be called.  
  750.                     The default for create is 0.  CREATE is
  751. defined as 1.
  752.                     The default for type of key is UNDEF_KEY. 
  753. Types of keys are VAR_LNG_KEY, LONG_KEY, DOUBLE_KEY, or
  754. FIX_LNG_KEY.
  755.                     The default for duplicates allowed is 0.  To
  756. allow duplicates set duplicates allowed to 1.
  757.                     The default for size of a fixed length key is
  758. 0.  When a fixed length key tree is being created, this value
  759. must be set to the length of the key.
  760.                     There is a different key compare routine made
  761. available for each type of key definition.  The source code
  762. manual contains additional information for programming compare
  763. routines for any type of key - for example database combination
  764. keys.
  765.                     The installed compare routines compare
  766. (long)1 as less than (long)2, (double)1.1 as less than
  767. (double)1.2, a fixed length key "abcdef" as less than a fixed
  768. length key "bcdefg", a variable length key "abcdef" as less than
  769. a variable length key "bcdefg", a variable length key "abcdef" as
  770. greater than a variable length key "bcdef".  It can be assumed
  771. that long and double keys will compare according to rules
  772. established by the compiler, fixed length keys will compare as
  773. runs of binary data, and variable length keys will compare as
  774. strings of characters with presidence placed on string length
  775. over value.
  776.  
  777.  
  778.                Examples:
  779.                     
  780.                     char * old_tree = "old.idx";
  781.                     char * new_tree = "new.idx";
  782.                     
  783.                     Btree tree(old_tree);
  784.                          or
  785.                     Btree tree(new_tree, CREATE, VAR_LNG_KEY, 1,
  786. 0 );
  787.  
  788.           ~Btree();
  789.                Purpose:
  790.                     Class destructor.
  791.  
  792.           int close();
  793.                Purpose:
  794.                     Close the open btree.
  795.  
  796.                Syntax:
  797.                     Close();
  798.  
  799.                Discussion:
  800.                     This function allows the external program to
  801. force a close of the open btree file descriptor before the end of
  802. the scope where the destructor would automatically call the Close
  803. routine.  The use of this capability is to allow the program to
  804. reduce open files.
  805.  
  806.                Return value:
  807.                     Returns the integer value defined as SUCCESS.
  808.  
  809.           Installcompare();
  810.  
  811.                Purpose:
  812.                     Installs a new compare routine for use by the
  813. btree.
  814.  
  815.                Syntax:
  816.                     int status;
  817.                     status = InstallCompare ( int(*) (union Key*
  818. key, struct KeyGroup * kg, int fixed_length ) );
  819.  
  820.                Discussion:
  821.                     The InstallCompare function installs the
  822. address of a new comparision function into the btree.  The
  823. comparison function compares a first parameter key with a second
  824. parameter key imbedded in a KeyGroup.  Internally, that would
  825. normally be a search Key and the current active KeyGroup. 
  826. Comparison of fix length keys requires a length parameter.  The
  827. extended manual accompanying the source code contains additional
  828. information for writing an installable compare routine.
  829.  
  830.                Return Value:
  831.                     Returns 0 if keys are equal, 1 if the key is
  832. greater than the imbedded key, and -1 if the key is less than the
  833. imbedded key.  Note that the standard library string functions do
  834. not meet the requirements of this specification.
  835.  
  836.           operator +=()
  837.  
  838.                Purpose:
  839.                     Insert a key into the tree.
  840.  
  841.                Syntax:
  842.                     int status;
  843.                     status = tree+=( struct KeyGroup * new_key);
  844.  
  845.                Discussion:
  846.                     The overloaded operator += inserts a new
  847. KeyGroup into the tree.
  848.  
  849.                Return Value:
  850.                     Returns the defined value for SUCCESS or
  851. FAIL.
  852.  
  853.           operator -=();
  854.  
  855.                Purpose:
  856.                     Delete a key from the tree.
  857.  
  858.                Syntax:
  859.                     int status;
  860.                     status = tree-=(union Key * remove_key);
  861.  
  862.                Discussion:
  863.                     The overloaded operator -= deletes a KeyGroup
  864. associated with the passed Key *.  If there are multiple keys
  865. associated with the passed Key *, then the first encountered is
  866. deleted from the tree.
  867.  
  868.                Return Value:
  869.                     Returns the defined value for SUCCESS or
  870. FAIL.
  871.  
  872.           Locate();
  873.  
  874.                Purpose:
  875.                     Locate a key in the tree.
  876.  
  877.                Syntax:
  878.                     int status;
  879.                     status = tree.Locate(union Key * locate_key);
  880.  
  881.                Discussion:
  882.                     This function locates the first exact match
  883. in the tree to the passed Key *.  If no match if found the
  884. function returns FAIL.
  885.  
  886.                Return value:
  887.                     Returns the defined value for SUCCESS or
  888. FAIL.
  889.  
  890.           operator++();
  891.  
  892.                Purpose:
  893.                     Increment the current position in the tree to
  894. the next sequential key.
  895.  
  896.                Syntax:
  897.                     struct KeyGroup * kgp;
  898.                     kgp = tree++();
  899.  
  900.                Discussion:
  901.                     This overload operator increments to the next
  902. key in the tree and returns a pointer to a copy of the key.
  903.   
  904.                Return value:
  905.                     struct KeyGroup * to copy of the next key, or
  906. NULL on failure.
  907.  
  908.           operator--();
  909.  
  910.                Purpose:
  911.                     Decrement the current position in te tree to
  912. the previous sequential key.
  913.  
  914.                Syntax:
  915.                     struct KeyGroup * kgp;
  916.                     kgp = tree--();
  917.  
  918.                Discussion:
  919.                     This operload operator decrements to the next
  920. key in the tree and returns a pointer to a copy of the key.
  921.  
  922.                Return value:
  923.                     struct KeyGroup * to copy of the previous
  924. key, or NULL on failure.
  925.  
  926.          
  927.           First();
  928.  
  929.                Purpose:
  930.                     Reinitialize the current pointer into the
  931. tree to point to the first key in the tree.
  932.  
  933.                Syntax:
  934.                     struct KeyGroup * kgp;
  935.                     kgp = First();
  936.  
  937.                Discussion:
  938.                     Sets active key to the first key in the tree.
  939.  
  940.                Return value:
  941.                     struct KeyGroup * to copy of the first key in
  942. the tree.
  943.           
  944.           Last()();
  945.                Purpose:
  946.                     Reinitialize the current pointer into the
  947. tree to point to the last key in the tree.
  948.  
  949.                Syntax:
  950.                     sruct KeyGroup * kgp;
  951.                     kgp = Last();
  952.  
  953.                Discussion:
  954.                     Sets active key to the last key in the tree.
  955.  
  956.                Return value:
  957.                     struct KeyGroup * to copy of the last key in
  958. the tree.
  959.           
  960.           CurrentKey();
  961.                Purpose:
  962.                     Retreive the current key.
  963.                
  964.                Syntax:
  965.                     struct KeyGroup * kgp;
  966.                     kgp = tree.CurrentKey();
  967.  
  968.                Discussion:
  969.                     Called at any time to retreive a pointer to a
  970. copy of the current key.
  971.  
  972.                Return value:
  973.                     struct KeyGroup * to copy of the current key
  974. in the tree.
  975.  
  976.           ReportState();
  977.                Purpose:
  978.                     Return state information from the tree.
  979.  
  980.                Syntax:
  981.                     long value;
  982.                     int request;
  983.                     value = tree.ReportState(request);
  984.  
  985.                Discussion:
  986.                     Certain items of information are required
  987. from the tree.  These items can be retreived from this function
  988. by passing specified requests.  The values are returned as longs
  989. even where integer values might be expected.  The following are
  990. valid requests.  
  991.                     SEARCH_LEVELS 
  992.                     DUPLICATES 
  993.                     TYPE_OF_KEY 
  994.                     KEY_LENGTH 
  995.                     NUMBER_OF_KEYS 
  996.                     LAST_ACCESS 
  997.                     ACTIVE_LEVEL
  998.  
  999.           Other functionality:
  1000.  
  1001.                     Source code documentation discusses other
  1002. public functions which allow debugging, header displays, key
  1003. displays, node dumps, and checks of the current hierarchy, and
  1004. access to address information relative to the the current node.
  1005.  
  1006.  
  1007. Appendix A
  1008.  
  1009.                     Order Blank and Registration:
  1010.  
  1011. Register to:
  1012.  
  1013. Name:    ______________________________________________
  1014. Address: ______________________________________________
  1015.          ______________________________________________
  1016. City:    _____________________State_________Zip________
  1017. Telephone: _______/________-____________
  1018.  
  1019. Ship to: (if different than above)
  1020.  
  1021. Name:    ______________________________________________
  1022. Address: ______________________________________________
  1023.          ______________________________________________
  1024. City:    _____________________State_________Zip________
  1025. Telephone: _______/________-____________
  1026.  
  1027.  
  1028. Remit to:  Larry A. Walker & Co.
  1029.            736 Watford Ct.
  1030.            Sterling Va 22170
  1031.  
  1032.  
  1033.          
  1034. ============================================================
  1035.           Date:                          PO #:
  1036.          
  1037. ============================================================
  1038. Quantity       Description                  Unit    Extended
  1039.          
  1040. ------------------------------------------------------------
  1041.            | Individual License           | $45.00 | $
  1042.            | Development License 1st      | 450.00 |
  1043.            | Development License 2nd      | 400.00 |
  1044.            | Development License 3rd      | 350.00 |
  1045.            | Development License 4th +    | 300.00 |
  1046.            | Printed Manual               |  10.00 |
  1047. ------------------------------------------------------------
  1048.                                                     Subtotal: $
  1049.           (VA Residents please add 4.5% sales tax)       Tax: $
  1050.                                                        Total: $
  1051.  
  1052.  
  1053. Appendix B
  1054.  
  1055.           Files:
  1056.  
  1057. Btree.man
  1058.           The B+Tree manual.
  1059. Btree.hpp
  1060.           Header file which defines the B+Tree class.
  1061. dbfiles.hpp
  1062.           Common header file.
  1063. BFH.hpp
  1064.           Header file which defines the block file handler class.
  1065. runerr.hpp
  1066.           Header file which defines the runtime error handler
  1067.           class.
  1068. Btree.obj
  1069.           Borland Compiled B+Tree class object.
  1070. BFH.obj
  1071.           Borland Compiled block file handler class object.
  1072. runerr.obj
  1073.           Borland Compiled runtime error handler class object.
  1074. Btree1.obj
  1075.           Zortech Compiled B+Tree class object.
  1076. BFH1.obj
  1077.           Zortech Compiled block file handler class object.
  1078. runerr1.obj
  1079.           Zortech Compiled runtime error handler class object.
  1080. exercise.cpp
  1081.           Example program which can be used to manipulate a
  1082.           B+Tree.  Almost all the functionality available in the 
  1083.           B+Tree is exhibited in the exercise program example.
  1084.  
  1085. Example Compile Lines:
  1086.  
  1087.           Borland:
  1088. tcc exercise.cpp btree.obj bfh.obj runerr.obj
  1089.  
  1090.           Zortech:
  1091. ztc exercise.cpp btree1.obj bfh1.obj runerr1.obj -DZORTECH
  1092.