RevMedia

One of the most efficient forms of indexed access to a file is via BTREES (Balanced Trees). This is a form of indexing where searching is performed using a binary chop technique to retrieve the required keys in the minimum possible time. It would seem reasonable to assume that all readers of this journal are familiar (at least in theory) with the mechanisms of BTREE (Balanced Tree) indexes. If not, a very good introductory text is "Algorithms" by Sedgewick. The AREV indexing is a little non-standard in structure and quite unorthodox in implementation. Within the AREV Btree nodes, lateral links exist in fields 2 and 3 to permit rapid traversing of the index. This is an improvement to the standard structure. The implementation seeks to address the problems encountered with speed when rebalancing a Btree in real time.

When a record is filed and changes need to be made to an index, rebalancing the index there and then can have a very adverse affect upon system performance. To avoid this problem, AREV does not attempt to balance an index when it saves a record, but rather writes a record to the transaction file (!INDEXING) indicating which record in which file on which volume has been changed and which changes are necessary to which indexes. These transaction records (sequentially numbered with record 0 containing the number of the highest transaction record used thus far) remain in the !INDEXING file until an explicit "update indexes" command is issued OR a workstation is left idle (and the "Updating Indexes" message appears).

When this happens the system takes the index transaction records one at a time and creates new transaction records in the appropriate !datafiles. These new transaction records are index specific and are keyed on the index name followed by an * followed by the transaction record number (EG SURNAME*2 - SURNAME* would contain the number of the next transaction record to use). Once all !INDEXING records are distributed to the !datafiles, they are applied to the indexes and the trees balanced.

Records in a !datafile thus have three classes of structure, control records, transaction records and data records. The control records describe the individual index characteristics. When indexes are added to or deleted from a file, these records are modified accordingly. (Hence the "Updating Index Control Records" visible when adding an index to a dictionary item - the system is creating the appropriate records in the bang file). When the file is accessed for the first time after these modifications have been made, SI.MFS detects this fact and using these control records compiles the index transaction code in !. (Should you be working on a low memory system, "Out of String Space" can frequently occur at this point. To minimise memory overhead, try using ED (v16 - REVMEDIA passim) to edit a record. Before editing can proceed the index will be recompiled and as ED takes so little memory there will be more chance of success.)

General Notes

The structures described in the following records seem to contain significant amounts of redundancy, some of which may be necessary, others of which may simply be historical artefacts. The notes following set out the structure of the remaining control records.

!

The bang record contains the compiled code called by SI.MFS as it performs write operations to the file. Note that this code is processed by RTP5 as a dictionary item and thus has similar structure. (For details on modifying this record and subsequent recompilation see the 1.1 Addendum or the Version 2 manuals).

!!

The bang bang record does not normally exist in the file, however if you add it using the editor (EDIT !filename !! then F9), the next time index code is recompiled, the source code will be placed into this item. If the index has already been compiled the easiest way to recompile it is to add a BTREE index to any field (don't update it), EDIT the file (this will cause a recompilation of the ! logic), remove the BTREE index and again EDIT the file. The index will now have been compiled as per the original index specification. This enables you to study the way in which the code works and make any necessary modifications. This should only be undertaken as a last resort. The optimum use for this is to identify how various system routines such as INDEX.OPEN are used.

*INDEXES

The *INDEXES record consists of a single multivalued field. Each value in the record describes an index maintained on this file. Note that it will not contain values relating to relational indexes TO this file, only FROM this file. The values are actually record keys of other records in the bang file and will thus have one of three forms

     Field Name                                     Btree Index
     Field Name.XREF                                XREF index
     File related to*Field related to*Sort Order    Relational index

Field Name/Field Name.XREF

This record (EG CUSTOMER_NAME) has four fields. The field are structured as follows

  Field Number    Contents
     <1>          Sort Order
     <2>          Field Name - Name of field being indexed
     <3>          Always seems to contain same as 2
     <4>          If set to 1 then Uppercase Conversion has been set to No.

File_related_to*Field_Related_to*Sort_order

This record (EG CUSTOMERS*INVOICES*AR) has seven field. The fields are structured as follows

  Field Number    Contents
     <1>          Index Type - Always contains REL for relational
     <2>          Field Name - Name of field being indexed
     <3>          Always seems to contain same as 2
     <4>          If set to 1 then Uppercase Conversion has been set to No.
     <5>          File*Account *Volume_Name of destination file. Note that
                  file and account  are not enough to ensure uniqueness,
                  volume name must also be used.
     <6>          Field number in foreign file to be updated
     <7>          Sort Order

!Filename

This record (EG !CUSTOMERS) has only one field. It is broken down into subvalues with there being three more subvalues that there are indexes on the file. The first three subvalues follow the same structure but the following subvalues are non-homogenous with a different structure for Btree/Xref/Relational Index From/Relational Index To. these records are text mark delimited. The first three subvalues are structured as follows

  Field Number    Contents
  <0,0,1>         File*Account *Volume_Name identifier for data file with
                  which index file is normally associated.
  <0,0,2>         Contains either * or null. This field will only contain *
                  when there are indexes which need to be checked when a
                  record is written to disk, i.e. btree/xref/relational to.
                  However if the only indexes on this file are relational
                  from (i.e. this file is used to store a relational index
                  from another file) this field will be null. This is
                  probably used by SI.MFS to ascertain whether the rest of
                  the subvalues in the record need to be checked.
  <0,0,3>         Null
  <0,0,4>+        Individual index records.

The following subvalues are structured as follows

     BTREE Index
     This subvalue has four text values

       Field Number   Contents
       <0,0,0,1>      Field Name
       <0,0,0,2>      If set to 1 then No Uppercase Conversion
       <0,0,0,3>      0 (identifies it as BTREE)
       <0,0,0,4>      Field number being indexed on.

     XREF Index
     This subvalue has four text values

       Field Number   Contents
       <0,0,0,1>      Field Name
       <0,0,0,2>      If set to 1 then No Uppercase Conversion
       <0,0,0,3>      2 (identifies it as XREF)
       <0,0,0,4>      4 (seems to be always set to 4).

     Relational Index To
     This subvalue identifies a field in the current record that should be
     used to update a field in another file (EG this would be on the
     customer number in an invoices file). This record has seven text
     values.

       Field Number   Contents
       <0,0,0,1>      Index identifier - File*Field*Sort_Order
       <0,0,0,2>      If set to 1 then No Uppercase Conversion
       <0,0,0,3>      3 (identifies it as Relational Index To)
       <0,0,0,4>      Field name to index on.
       <0,0,0,5>      File_Name*Account_Name*Volume_Name of foreign file to
                      index to.
       <0,0,0,6>      Field number to index to in the foreign file.
       <0,0,0,7>      Sort order of index

     Relational Index From
     This subvalue identifies a field in the current record that is updated
     by a relational index in another file. (EG this would be on the invoice
     numbers in a customer file). This record has four text values.

       Field Number   Contents
       <0,0,0,1>      Index identifier - of format P$field_name_indexed_to.
                      The preceding P$ enables easy identification of the
                      index as not being updated by normal record writes .
       <0,0,0,2>      Null
       <0,0,0,3>      5 (identifies it as Relational Index From)
       <0,0,0,4>      Field number indexed to.