Indexing 101 1/3

 BBS: Inland Empire Archive
Date: 06-18-92 (06:18)             Number: 807
From: RICHARD VANNOY               Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: Indexing 101 1/3               Conf: (2) Quik_Bas

INDEXING 101, Page 1 of 3

Copyright 1992, Richard Vannoy
Reproduction authorized only if reproduced in full with the
copyright notice as above and no editorial changes.

So here's the basics of file indexing.  I'll use the file
extensions .DBF to indicate a normal RANDOM data file and
.NDX to show an index file.  We'll start with a data file:

TYPE EmployeeData
   lastname AS STRING * 15
   firstname AS STRING * 10
   employeeNumber AS INTEGER
   SSN AS STRING * 11
   salary AS SINGLE
   hireDate AS STRING * 8
   'Many more fields could (and usually do) go here for a
   'typical company data base.  Imafine that there are
   'perhaps 60 to 80 fields using maybe 400 to 600 bytes
   'each. It's important to remember, as we go along, that
   'ALL of this data for all the employees is much too
   'massive to fit in the memory of most machines.
END TYPE
DIM EMPL AS EmployeeData

Now let's suppose the personnel department wants us to
design the data base so they can quickly retrieve an
employee's information, and they want to be able to enter
EITHER the first and last name OR the employee number.  As
you could guess, if you were sitting at a terminal all day,
you would quickly find out that if you can enter just the
employee number instead of the full name, that data entry
will be much faster and more efficient.  So if we are
dealing with documents that have the employee number (as
most work type documents do), then that would be quicker.
But we also have to allow for the case where the employee
number is not known.  So, we must also allow the employee's
name to be entered also.

So we decide to index the data base in two ways; first by
employee number:

We need a small data structure to contain just two things:
the employee number (what we're indexing on), and the record
number where that employee's information can be found.  So..

TYPE EmpNumberIndex
   EmpNumber AS SINGLE
   RecordNumber AS SINGLE
END TYPE
DIM NUMB AS EmpNumberIndex

Then we need a small data structure for the first name/Last
name information:

TYPE EmpNameIndex
   BothNames AS STRING * 26
   RecordNumber AS SINGLE
END TYPE
DIM ENAM AS EmpNameIndex

Note that the BothNames field is big enough to hold the
first name, a space, and then the last name.  Also note that
both EmpNumberIndex and EmpNameIndex have the RecordNumber
for where that employee is stored, since we don't need ALL
the employee info, just a pointer to where we can find it.

We're going to open three files...

OPEN "EMPLOYEE.DBF" FOR RANDOM AS #1 LEN = LEN(EMPL)
OPEN "EMPNUMBR.NDX" FOR RANDOM AS #2 LEN = LEN(NUMB)
OPEN "EMPLNAME.NDX" FOR RANDOM AS #3 LEN = LEN(ENAM)

Let's start with three employees.
EMPLOYEE.DBF will have:
RECLast Name  First Name  Employee Numb.  AND all the------>
-- ---------  ----------  --------------  rest of the------>
 1 Vannoy     Richard         46          fields for------->
 2 Que        Suzie           32          for several------>
 3 McGee      Bobbie          23          hundred bytes---->

EMPNUMBR.NDX will have:
Employee Numb.  REC
___-----------  ---
      46         1
      32         2
      23         3

EMPLNAME.NDX will have:
BothNames      REC
___------      ---
Vannoy Richard  1
Que Suzie       2
McGee Bobbie    3
<continued next message>
___
> MegaMail 2.1b #0:You're really hard up if you steal this tagline!
~~
--- Maximus 2.00
 * Origin: D.J.M.BBS (1:202/307)