home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / basic / library / qb_pds / database / btree / indexing.doc next >
Encoding:
Text File  |  1987-01-22  |  10.9 KB  |  331 lines
  1.                       Binary Tree Indexing for QuickBASIC
  2.  
  3.  
  4.  
  5.                                   Introduction
  6.  
  7.         One  of the problems with using hashing functions in indexing  is 
  8.         the  inability  to step through the index in sequence,  find  the 
  9.         previous  and  next keys,  and find keys with  the  smallest  and 
  10.         largest values. Whilst this is not the only problem, it makes any 
  11.         solution to this attractive.
  12.  
  13.         With QuickBASIC,  separate libraries of code that could be viewed 
  14.         as  'black  boxes' became a reality.  The code for  this  library 
  15.         (containing  separately  compiled sub-programs) is in  QuickBASIC 
  16.         version  2.00,  although there doesn't seem to be any reason  why 
  17.         they couldn't be translated to run under BASICA , or even another 
  18.         version of BASIC.
  19.  
  20.         The rest of the document is a description of these routines. 
  21.  
  22.         An  example program (NAMES.EXE & NAMES.BAS) contains calls  to  a 
  23.         number  of  sub-programs  besides  the  indexing  functions,  but 
  24.         examination of NAMES.BAS should adequately explain their purpose. 
  25.         If you wish to get a copy of these routines (source) ,  and other 
  26.         routines  demonstrated in NAMES then write to me (with some  sort 
  27.         of donation):
  28.  
  29.                                    Roy Barrow
  30.                               3J 222 Church Street
  31.                                   Philadelphia
  32.                                     PA 19107
  33.  
  34.                                  (215) 922 2557
  35.  
  36.  
  37.         Many  thanks  extended  to  Thomas Hanlin  III  for  placing  his 
  38.         excellent  package of assembler routines (ADVBAS27) in the public 
  39.         domain. This Library makes QuickBASIC really PERFORM!
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.         (c) Copyright   Roy Barrow         -1-       11-January-1986
  62.  
  63.  
  64.  
  65.  
  66.  
  67.                       Binary Tree Indexing for QuickBASIC
  68.  
  69.  
  70.                                   Limitations.
  71.  
  72.         The  index  key size may only be between 4 &  255  characters  in 
  73.         length.  There  may  be a maximum of 32766 keys in the index  (by 
  74.         amending  the  pointer system so that it uses  SHORT  numbers  in 
  75.         place  of integers,  this could theoretically be increased to  16 
  76.         million or so).
  77.  
  78.                        Structure  &  Naming  conventions.  
  79.  
  80.         The  sub-routines  are stored separately in  files.  These  files 
  81.         begin  with AE.  This is the abbreviation for a package  of  sub-
  82.         routines  that I have put together (of which binary indexing is a 
  83.         small part). The next three characters are BIT (BInary Tree). The 
  84.         last  three characters indicate the purpose of  the  sub-routine. 
  85.         The routines themselves all begin with BIT. I've placed them in a 
  86.         library  (AEBITIDX.LIB)  that  can be used  during  linkage.  The 
  87.         routines are as follows:
  88.  
  89.         A brief description of each routine follows.
  90.  
  91.         BIT.CLOSE       Close an index file
  92.         BIT.CREAT       Create an index. Prompts user for input.
  93.         BIT.CREATQ      Create an index, 'quiet' - parameters passed.
  94.         BIT.FIND        Find an key in an index.
  95.         BIT.INS         Insert a key into an index.
  96.         BIT.KILL        Delete a key from an index.
  97.         BIT.LEFT        Find the smallest key in the index.
  98.         BIT.NEXT        Find the next key in sequence.
  99.         BIT.OPEN        Open an index file.
  100.         BIT.PREV        Find the previous key in sequence.
  101.         BIT.RIGHT       Find the largest key in sequence.
  102.  
  103.  
  104.  
  105.                           Using the indexing routines.
  106.  
  107.         Initially, the index(es) need to be created with either BIT.CREAT 
  108.         or BIT.CREAQ.  From then on,  each usage of the routines must  be 
  109.         preceded by a call to BIT.OPEN.  To write away the header details 
  110.         of the index, a call to BIT.CLOSE is needed.
  111.  
  112.         Note,  the  files AESHARED & AECOMMON need to be included in  the 
  113.         sub-routines & the application programs respectively.
  114.  
  115.         Maintaining  the  files that the indexes will reference is up  to 
  116.         your  application.  In the example program that I have  included, 
  117.         calls  are  made to various 'higher level'  disk  accessing  sub-
  118.         routines.  These  calls  would  have  to  be  simulated  in  your 
  119.         programs.  Again  - source  for these is  available,  we're  just 
  120.         covering  the indexing right now.  To place an item in the index, 
  121.         you need to pass it's relative record number to BIT.INSERT.  When 
  122.         searching for a record, BIT.FIND will return this relative record 
  123.         number.
  124.  
  125.  
  126.  
  127.         (c) Copyright   Roy Barrow         -2-       11-January-1986
  128.  
  129.  
  130.  
  131.  
  132.  
  133.                       Binary Tree Indexing for QuickBASIC
  134.  
  135.  
  136.                              Structure of the Index.
  137.  
  138.         Each index has two files,  one is a header file, and the other is 
  139.         the  index  proper.  (.HDR and .IDX).  The header  file  contains 
  140.         information  regarding  the structure of  the  index  proper.  On 
  141.         opening  the  index,   the  header  file  is  read  into  control 
  142.         variables,  the  header  is  closed,  and then the  actual  index 
  143.         opened. 
  144.  
  145.         The reverse is accomplished when the index is closed:  The  index 
  146.         closed, the header opened, and the new updated info is written to 
  147.         the header file.
  148.  
  149.         Most  of  the  values associated with the index are  in  declared 
  150.         COMMON blocks (AECOMMON & AESHARED).  The other values needed  in 
  151.         these routines are discussed for each CALL (below).
  152.  
  153.  
  154.                                   The routines.
  155.  
  156.         Two   variables,   AESB.FATAL%   and  AESB.WARNING%  are   active 
  157.         throughout the whole system of my AE subroutine package.  Suffice 
  158.         it  to say that if the value of AE.FATAL% is NON ZERO  on  return 
  159.         from a routine,  then the program should probably abort. It means 
  160.         that  not only did the routine fail,  it was a failure caused  by 
  161.         buggy code.
  162.  
  163.         On the other hand, if AE.WARNING% is NON ZERO, then it means that 
  164.         the  routine failed due to other circumstances.  For example,  if 
  165.         you  called  BIT.KILL  without  a  proper  BIT.FIND  first,  then 
  166.         AE.WARNING% would return an error.  That's not a routine problem, 
  167.         thats a logic fault!
  168.  
  169.  
  170.  
  171.         bit.close      Close an index file
  172.         example:       call bit.close(fl%)
  173.         parameters:    fl% is the number of the file to close
  174.         returns:       none
  175.  
  176.  
  177.         bit.creat      Verbose creation of an index file.
  178.         example:       call bit.creat
  179.         parameters:    none
  180.         returns:       none
  181.  
  182.  
  183.         bit.creatq     Quiet creation of an index file.
  184.         example:       call bit.creatq(fl%,flnm$,key.length%)
  185.         parameters:    fl%            Index file number
  186.                        flnm$          Index name (no extension)
  187.                        key.length%    Length of key
  188.         returns:       none
  189.  
  190.  
  191.  
  192.  
  193.         (c) Copyright   Roy Barrow         -3-       11-January-1986
  194.  
  195.  
  196.  
  197.  
  198.  
  199.                       Binary Tree Indexing for QuickBASIC
  200.  
  201.  
  202.         bit.find       Find a key in an index
  203.         example:       call bit.find(fl%,kvalue$,rrec%,success%)
  204.         parameters:    fl%            Index file number
  205.                        kvalue$        Key value to find
  206.         returns:       rrec%          Pointer to indexed file
  207.                        success%       Set to 1 if successful
  208.  
  209.  
  210.         bit.ins        Insert a key into the index
  211.         example:       call bit.ins(fl%,kvalue$,rrec%,success%)
  212.         parameters:    fl%            Index file number
  213.                        kvalue$        Key value to insert
  214.                        rrec%          Pointer to indexed file
  215.         returns:       success%       Set to 1 if successful
  216.  
  217.  
  218.         bit.kill       delete a key from the index.
  219.         example:       call bit.kill(fl%,kvalue$,rrec%,success%)
  220.         parameters:    fl%            Index file number
  221.                        kvalue$        Key value to delete
  222.                        rrec%          Pointer to indexed file
  223.                                       (unchanged from a call to FIND)
  224.                        success%       (unchanged from a call to FIND)
  225.         returns:       success%       Set to 1 if successful
  226.  
  227.  
  228.         bit.left       Finds the smallest key in the index
  229.         example:       call bit.left(fl%,kvalue$,rrec%,success%)
  230.         parameters:    fl%            Index file number
  231.         returns:       kvalue$        Key value in index
  232.                        rrec%          Pointer to indexed file
  233.                        success%       Set to non zero if successful
  234.  
  235.  
  236.         bit.next       Find next key in an index
  237.         example:       call bit.next(fl%,kvalue$,rrec%,success%)
  238.         parameters:    fl%            Index file number
  239.                        kvalue$        (unchanged from last FIND)
  240.                        rrec%          (unchanged from last FIND)
  241.                        success%       (unchanged from last FIND)
  242.         returns:       kvalue$        Key value in index
  243.                        rrec%          Pointer to indexed file
  244.                        success%       Set to non zero if successful
  245.  
  246.  
  247.  
  248.         bit.open       Open an index file
  249.         example:       call bit.open(fl%,idxnam$)
  250.         parameters:    fl%            Index file number
  251.                        idxnam$        Name of index header (no extension)
  252.         returns:       (check warning)
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.         (c) Copyright   Roy Barrow         -4-       11-January-1986
  260.  
  261.  
  262.  
  263.  
  264.  
  265.                       Binary Tree Indexing for QuickBASIC
  266.  
  267.  
  268.         bit.prev       Find previous key in an index
  269.         example:       call bit.next(fl%,kvalue$,rrec%,success%)
  270.         parameters:    fl%            Index file number
  271.                        kvalue$        (unchanged from last FIND)
  272.                        rrec%          (unchanged from last FIND)
  273.                        success%       (unchanged from last FIND)
  274.         returns:       kvalue$        Key value in index
  275.                        rrec%          Pointer to indexed file
  276.                        success%       Set to non zero if successful
  277.  
  278.  
  279.         bit.right      Finds the largest key in the index
  280.         example:       call bit.right(fl%,kvalue$,rrec%,success%)
  281.         parameters:    fl%            Index file number
  282.         returns:       kvalue$        Key value in index
  283.                        rrec%          Pointer to indexed file
  284.                        success%       Set to non zero if successful
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.         (c) Copyright   Roy Barrow         -5-       11-January-1986
  326.  
  327.  
  328.  
  329.  
  330.  
  331.