home *** CD-ROM | disk | FTP | other *** search
/ Shareware Overload / ShartewareOverload.cdr / database / db_dbug2.zip / DB3_HDR.DOC < prev    next >
Text File  |  1987-03-09  |  4KB  |  87 lines
  1.                      .DBF and .NDX Header Definitions
  2.  
  3. Compiled by Curtis H. Hoffmann, 02/20/87.   
  4.  
  5.  
  6.    .DBF Primary Header
  7.    -------------------
  8. Address     Contents       Description
  9. -------     --------       -----------
  10.     0       1 byte         Database type: 03 if data; 83 if there is an
  11.                            associated memo file
  12.   1-3       3 ASCII char.  Date last updated, in YY,MM,DD format
  13.   4-7       32 bit #       Number of records in file
  14.   8-9       16 bit #       Starting location of data
  15.  10-11      16 bit #       Length of records (total field size +1)
  16.  12-31      20 bytes       (Reserved)
  17.  32-n       32 bytes ea.   Field descripter array
  18.   n+1       1 byte         0D hex terminator
  19.  
  20.    .DBF Field Descripter Array
  21.    ---------------------------
  22.      0      1 byte         Deletion marker; 2A if marked else 20 hex
  23.   1-10      10 bytes       Field name in ASCII (0 as terminator)
  24.     11      1 byte         Field type in ASCII
  25.  12-15      32 bit #       Field data address (internal use)
  26.     16      1 byte         Field length in binary
  27.     17      1 byte         Field decimal count in binary
  28.  18-31      14 bytes       (reserved)
  29.  
  30. =======================================================================
  31.  
  32.    .NDX Anchor Node Heading
  33.    ------------------------
  34. Address   Contents    Description
  35. -------   --------    -----------
  36.   0-1     2 bytes     (Reserved)
  37.   4-5     16 bit #    Node number of root node
  38.   8-9     16 bit #    Node number of next available node
  39.    12     1 byte      Length of key in binary
  40.    14     1 byte      Maximum number of keys per 512 byte node
  41.    16     1 byte      Index key type; 0 if character key, else 01
  42.    18     1 byte      length of key records in binary (includes address
  43.                       to .DBF file)
  44.  24-279   256 bytes   Key expression in ASCII (00 hex as terminator)
  45. 280-511   232 bytes   (Unused)
  46.  
  47.    .NDX Array (all other nodes)
  48.    ----------------------------
  49.  
  50.      0     1 byte          Number of records in this node
  51.    4-7     32 bit #        Identifies type of node; 0 if a leaf else the node 
  52.                            number of the next branch of the tree
  53.    8-11    32 bit #        If not a branch then this is the address to the
  54.                            corresponding .DBF record
  55.   12-n     mod 8 bytes     Key expression
  56.   n+1-511  record length   Repeating addresses and key expressions until the
  57.                            end of the node
  58.    
  59.    Every node is 512 bytes long, treated as part of a B+ tree.  If the node
  60. is a branch, then compare the match pattern with the key expression.  If the
  61. pattern <= the key, then go to the appropriate lower level node, otherwise 
  62. go to the next key in that node.  Do this only for the number of keys in this
  63. node.
  64.  
  65.  
  66. Algorithm for finding a given record:
  67. -------------------------------------
  68.  
  69. A)  Read starting node # (SN), length of key (LOK), length of key 
  70.     record (LOKR), and total number of nodes (TON).
  71. B)  Goto starting node (SN*512).  Check to see if the node is a leaf or a
  72.     branch (addresses 4 through 7 = 0 if leaf).  Current node (CN) = SN
  73. C)  Get number of records for this node (NOR).  Zero pointer.  <--
  74. D)  While current node < TON and desired record not found, do:   |
  75.        While pointer <= NOR and record not found, do:            |
  76.           piece key expression together.                         |
  77.           cs=512*CN+12+(pointer-1)*LOKR.                         |
  78.           if match pattern <= key expression, do:                |
  79.              if branch then CN=contents at cs+4.  Repeat ---------
  80.              if not branch and match pattern=key then, do:       |
  81.                 data field record at cs+8.                       |
  82.                 ** Done **                                       |
  83.           else increment pointer                                 |
  84.        If end of node and match not made, do:                    |
  85.           If branch, current node = contents of cs+4.  Repeat ----
  86.           If not branch, then record not in index.  ** Done **
  87.