home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / CONTRIB / MBASE / MBASE51.TAR / mbase51 / tech / chapter.3 < prev    next >
Encoding:
Text File  |  1993-09-04  |  5.4 KB  |  116 lines
  1. Tech Chapter 3 - Delayed indexing                                 MetalBase 5.1
  2. -------------------------------------------------------------------------------
  3.  
  4. If you take a look at the chapter on MetalBase's binary tree algorithms, you'll
  5.    notice that the operation within mb_add() which links a new record into
  6.    all a relation's indices is a complete, distinct routine.  Without this
  7.    routine, a record would exist in the physical heap, but would not be
  8.    accessed by following any indices in any direction.
  9.  
  10. Sounds awful, doesn't it?
  11.  
  12. It's not all that bad.  as of MetalBase 5.1, functions have been added which
  13.    allow you to deal with records which have not been linked into the indices.
  14.    The primary benefit of this is that add operations are nearly instantaneous;
  15.    for example, if you were importing 5,000 records into a 10,000-record
  16.    relation, mb_add_q() would be infinitely faster than using mb_add().  The
  17.    downside is that these records can't be queried as well as others; to make
  18.    them do that, there are two ways to get them into the primary heap:
  19.  
  20.    1st- the routine mb_xfer() will take the first unindexed record that
  21.         it finds and index it.  In essence, calling mb_add_q() followed
  22.         by mb_xfer() is identical to just calling mb_add().  The advantage
  23.         here is that you can index records when your computer is free.
  24.  
  25.    2nd- the utility MBDIAG, when it rebuilds indices, will take into account
  26.         -all- records, including those not previously indexed.  In this
  27.         way, the 5000 records mentioned above can be indexed in a much,
  28.         much shorter amount of time. 
  29.  
  30.  
  31. To make this as fast as possible, records which haven't been indexed are
  32.    kept in a contiguous chunk at the end of the .REL file:
  33.  
  34.           [ relation header ]
  35.           [ idx1 ][ idx2 ][ idx3 ][ record 0 ] #0
  36.           [ idx1 ][ idx2 ][ idx3 ][ record 1 ] #1
  37.           [ idx1 ][ idx2 ][ idx3 ][ record 2 ] #2
  38.           [ idx1 ][ idx2 ][ idx3 ][ record 3 ] #3
  39.           [    0 ][    0 ][    0 ][ record 4 ] #4
  40.           [    0 ][    0 ][    0 ][ record 5 ] #5
  41.           [    0 ][    0 ][    0 ][ record 6 ] #6
  42.  
  43.    In the example above, records 4-6 have not been indexed.  If mb_xfer were
  44.    called at this point, record 4 would be indexed, and 5 and 6 would be left
  45.    in this unindexed-record heap.
  46.  
  47.  
  48. MB_ADD() ----------------------------------------------------------------------
  49.  
  50. However, this leads to the problem of keeping all those records in a chunk
  51.    when you've used mb_add(), or mb_del()'ed a record which is indexed.  First
  52.    off, mb_add()... in the case below, "record 7" has been added with mb_add()
  53.    (so it had to be -before- the secondary heap, into position #4):
  54.  
  55.           [ relation header ]
  56.           [ idx1 ][ idx2 ][ idx3 ][ record 0 ] #0
  57.           [ idx1 ][ idx2 ][ idx3 ][ record 1 ] #1
  58.           [ idx1 ][ idx2 ][ idx3 ][ record 2 ] #2
  59.           [ idx1 ][ idx2 ][ idx3 ][ record 3 ] #3
  60.           [ idx1 ][ idx2 ][ idx3 ][ record 7 ] #4
  61.           [    0 ][    0 ][    0 ][ record 5 ] #5
  62.           [    0 ][    0 ][    0 ][ record 6 ] #6
  63.           [    0 ][    0 ][    0 ][ record 4 ] #7
  64.  
  65.    So "record 4" was rolled to the end of the secondary heap, leaving a block
  66.    of space for "record 7" to be inserted.  Simple, eh?
  67.  
  68. Note that the normal _check_dup() function uses _search() to find duplicates,
  69.    which only knows about the primary (indexed) heap.  So, before mb_add(),
  70.    mb_add_q() and mb_upd() can accept a record, it has to do a second check
  71.    throughout the entire secondary heap to ensure no nodups index will be
  72.    violated by the addition.
  73.  
  74.  
  75. MB_DEL() ----------------------------------------------------------------------
  76.  
  77. Now what about mb_del()?  Using the above chart--if you deleted "record 5",
  78.    "record 4" would replace it and that's that--no indices to fix, because
  79.    it isn't indexed.  It's not that easy if you delete, say, "record 2".  In
  80.    that case, the chart would end up looking like this:
  81.  
  82.           [ relation header ]
  83.           [ idx1 ][ idx2 ][ idx3 ][ record 0 ] #0
  84.           [ idx1 ][ idx2 ][ idx3 ][ record 1 ] #1
  85.           [ idx1 ][ idx2 ][ idx3 ][ record 7 ] #2
  86.           [ idx1 ][ idx2 ][ idx3 ][ record 3 ] #3
  87.           [    0 ][    0 ][    0 ][ record 4 ] #4
  88.           [    0 ][    0 ][    0 ][ record 5 ] #5
  89.           [    0 ][    0 ][    0 ][ record 6 ] #6
  90.  
  91.    So how did it get there?  Well, first, it unlinked "record 2" from all
  92.    relevant indices.  Then it found the last record in the primary heap,
  93.    "record 7", and wrote it over "record 2"'s slot... and corrected all the
  94.    indices to point to slot #2 instead of slot #4, where "record 7" was
  95.    before it moved.  That left a hole at slot #4, so "record 4", in the
  96.    last slot in the secondary heap, was rolled backward over that slot.
  97.    Simple.
  98.  
  99.  
  100. MB_SEL() ----------------------------------------------------------------------
  101.  
  102. This one was really, really simple... basically because LTEQ, LTHAN, EQUAL,
  103.    GTHAN and GTEQ aren't supported on unindexed records.  FIRST, NEXT, LAST
  104.    and PREVIOUS are, however, so there's a separate routine in mb_misc.c
  105.    called _find_queue(), which simply moves rel->pos and reads in the
  106.    appropriate record.
  107.  
  108.  
  109. MB_UPD() ----------------------------------------------------------------------
  110.  
  111. This one was even more simple than the others; basically, if updating an
  112.    indexed record, the routine is the same as always.  If updating an unindexed
  113.    record, we just overwrite the record data with the new data, and that's
  114.    it.
  115.  
  116.