BTREE Index algorithm

[Steven Pringels 3]

To All:

The following parts contains FUNCTIONS of a whole BTREE engine algorithm. I wrote this a long time ago and I was reluctant to
give this out because it's a direct competition towards Power-
Tree from PowerBasic and DVBTREE from Zap Solutions. I thought
long about releasing this and I don't want to cut into the
sales of both products for both companies. The source code is
far from optimized and currently I know that PowerTree is far better than this attempt (Patrice, I suppose your product is on the same benchmark as PowerTree, I can't make a judgement on that though.)

So, in short, there is a lot of room for optimization. Such as the use of pointers etc. Please feel free to contribute to this but I do hope you give back the sourcecode to the powerbasic community. I also hope there is a lot of feedback and a lot of willingness to enhance this.

Good luck.

[Steven Pringels 3]

The test that is executed in the PBMAIN function uses a file PTSAMPLE.DAT this ia a file that comes with PowerTree.

I will send the sourcecode together with that file to the support dept of powerbasic.

Another remark. An enhancement that would be nice is not to actually store the keydata in the index file but only a pointer (offset + length) in the index that points to the actual data file.



[This message has been edited by Steven Pringels 3 (edited June 07, 2000).]

[Steven Pringels 3]

'//===========================================================================
'// Btree Plus indexing method (C) copyright Steven Pringels. All rights
'// reserved.
'// RELEASED UNDER THE OPEN SOURCE LICENSE.

$DIM ALL
DEFINT A-Z

DECLARE FUNCTION BtreeBalans (BtreeFileHandle As Integer) As Integer
DECLARE FUNCTION BtreeFirst (BtreeFileHandle As integer) As Long
DECLARE FUNCTION BtreeIndex (BtreeFileHandle As Integer) As Integer
DECLARE FUNCTION BtreeInsert (BtreeFileHandle As Integer, _
                              KeyIndex        As integer, _
                              Duplicate       As Integer, _
                              RecordNumber    As Long) As Long
DECLARE FUNCTION BtreeLast (BtreeFileHandle As Integer) As Long
DECLARE FUNCTION BtreeOpen (BtreeFile As String, BtreeFileHandle As Integer) As Long
DECLARE FUNCTION BtreeClose (BtreeFileHandle As Integer) As Integer
DECLARE FUNCTION BtreeNext (BtreeFileHandle As integer, N As Long) As Integer
DECLARE FUNCTION BtreePrevious (BtreeFileHandle As Integer, N As Long) As Integer
DECLARE FUNCTION BtreeErase (BtreeFilehandle As Integer, DeleteRecNo As Long) As Integer
DECLARE FUNCTION BtreeSearch(BtreeFileHandle As Integer, _
                             KeyIndex        As integer, _
                             SearchKey       As String, _
                             Exact           As integer) As Long

TYPE BtreeType
  Indexes               As Integer
  Smaller               AS LONG                            'Required
  Bigger                AS LONG                            'Required
  Previous              AS LONG                            'Required
  DeleteKey             AS STRING * 1                      'Required
  IndexKey              AS STRING * 25                     'Required
  RecordNumber          As LONG                            'Required
END TYPE

TYPE PTSampleREC
  Title           AS STRING * 6
  Lastname        AS STRING * 25
  Firstname       AS STRING * 20
  Middleinitial   AS STRING * 1
  Address1        AS STRING * 30
  Address2        AS STRING * 30
  City            AS STRING * 25
  State           AS STRING * 2
  Zip             AS STRING * 9
  Comments        AS STRING * 60
END TYPE

GLOBAL Btree         As BtreeType
GLOBAL BtreeChanged  As Integer
GLOBAL BtreeFile     As String

------------------

[Steven Pringels 3]

'//---------------------------------------------------------------------------------------------------
'// BALANS THE BTREE INDEX
FUNCTION BtreeBalans(BtreeFileHandle As Integer) As Integer
 LOCAL FileHandle     As Integer
 LOCAL X              As Integer
 LOCAL BackUpFile     As String
 LOCAL RetVal         As long
 LOCAL First          As Long
 LOCAL RecNo          As Long
 LOCAL TempFile       As String
 LOCAL TotalRecs      As Long
 LOCAL N              As Long
 LOCAL Recs           As Long
 LOCAL Odd            As Long
 LOCAL Tabel          As String
 LOCAL Counter        As Long
 LOCAL UpperLimit     As Long
 LOCAL LowerLimit     As Long
 LOCAL Selection      As Long
 LOCAL Last           As Long
 RetVal = BtreeOpen (BtreeFile$, BtreeFileHandle)
 If RetVal < 0 Then
    BtreeBalans = -1
    Exit Function
 End if
 CALL BtreeIndex(BtreeFilehandle)
 CALL BtreeClose(BtreeFileHandle)
 FileHandle% = FREEFILE
 X% = INSTR (BtreeFile$, ".")
 IF X% > 0 THEN
   BackUpFile$ = LEFT$ (BtreeFile$, X% - 1)
 ELSE
   BackUpFile$ = BtreeFile$
 END IF
 BackUpFile$ = BackUpFile$ + ".BAK"
 OPEN BackUpFile$ FOR OUTPUT AS #FileHandle%
 CLOSE #FileHandle%
 KILL BackUpFile$
 NAME BtreeFile$ AS BackUpFile$
 TempFile$  = BtreeFile$
 BtreeFile$ = BackUpFile$
 CALL BtreeOpen(BtreeFile$, BtreeFileHandle)
 TotalRecs& = LOF (BtreeFileHandle%) \ LEN (Btree)
 RecNo& = 0
 First = BtreeFirst(BtreeFilehandle%)
 IF First& = 0 THEN
   GOTO StopBtreeBalance
 ELSE
   N& = First&
   DO
    RecNo& = RecNo& + 1
    CALL BtreeNext (BtreeFileHandle%, N&)
   LOOP UNTIL N& = 0
 END IF
 IF RecNo& < 10 THEN
   GOTO StopBtreeBalance
 END IF
 Recs& = RecNo& \ 2
 IF (Recs& + Recs&) < RecNo& THEN
   Odd& = -1
 END IF
 DIM Array1 (Recs&) As Long
 DIM Array2 (Recs&) As Long
 TotalRecs& = LOF (BtreeFileHandle%) \ LEN (Btree)
 RecNo& = 0
 First& = BtreeFirst (BtreefileHandle%)
 N& = First&
 DO
   RecNo& = RecNo& + 1
   IF RecNo& <= Recs& THEN
     Array1 (RecNo&) = N&
   ELSE
     Array2 (RecNo& - Recs&) = N&
   END IF
   IF RecNo& = Recs& + Recs& THEN
     EXIT DO
   ELSE
     CALL BtreeNext (BtreeFileHandle%, N&)
   END IF
 LOOP UNTIL N& = 0
 FileHandle% = FREEFILE
 OPEN TempFile$ FOR RANDOM AS #FileHandle% LEN = LEN (Btree)
 GET #BtreeFileHandle%, 1, Btree
 DIM TempBtree AS BtreeType
 GET #BtreeFileHandle%, Array1 (Recs&), TempBtree
 MID$(TempBtree.IndexKey, LEN (TempBtree.IndexKey), 1) = "!"
 Btree.IndexKey  = TempBtree.IndexKey
 Btree.Smaller   = 0
 Btree.Bigger    = 0
 Btree.Previous  = 0
 Btree.DeleteKey = "H"
 PUT #FileHandle%,, Btree
 Tabel$ = SPACE$ (Recs& + 1)
 MID$ (Tabel$, LEN (Tabel$), 1) = "2"
 Counter& = 0
 TotalRecs& = Recs&
 DO
   UpperLimit& = 0
   DO
    LowerLimit& = UpperLimit&
    UpperLimit& = INSTR (LowerLimit& + 1, Tabel$, "2")
    IF UpperLimit& - LowerLimit& > 1 THEN
      Selection& = (LowerLimit& + UpperLimit&) \ 2
      MID$ (Tabel$, Selection&, 1) = "1"
      GET #BtreeFileHandle%, Array1 (Selection&), Btree
      PUT #FileHandle%,, Btree
      Counter& = Counter& + 1
    END IF
   LOOP UNTIL UpperLimit& = (Recs& + 1)
   Selection& = INSTR (Tabel$, "1")
   WHILE Selection& > 0
    MID$ (Tabel$, Selection&, 1) = "2"
    GET #BtreeFileHandle%, Array2 (Selection&), Btree
    PUT #FileHandle%,, Btree
    Selection& = INSTR (Selection& + 1, Tabel$, "1")
  WEND
  RecNo& = Counter&
LOOP UNTIL Counter& = Recs&
IF Odd& THEN
  Last& = BtreeLast (BtreeFilehandle%)
  PUT #FileHandle%,, Btree
END IF
CLOSE #FileHandle%
CALL BtreeClose(BtreeFileHandle%)
BtreeFile$ = TempFile$
CALL BtreeOpen(BtreeFile$, BtreeFileHandle)
CALL BtreeIndex(BtreeFileHandle%)
CALL BtreeClose(BtreeFilehandle%)
BtreeChanged% = -1
EXIT FUNCTION
StopBtreeBalance:
CLOSE
NAME BackUpFile$ AS TempFile$
BtreeFile$ = TempFile$
EXIT FUNCTION
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// GET THE FIRST RECORD OF THE BTREE RECORD
FUNCTION BtreeFirst (BtreeFilehandle As Integer) As Long
LOCAL First     As Long
GET #BtreeFileHandle%, 1, Btree
IF Btree.Smaller > 0 THEN
  BtreeFirst = Btree.Smaller
ELSEIF Btree.Bigger > 0 THEN
  BtreeFirst = Btree.Bigger
ELSE
  BtreeFirst = 0
  EXIT FUNCTION
END IF
GET #BtreeFileHandle%, First&, Btree
WHILE Btree.Smaller > 0
  First& = Btree.Smaller
  GET #BtreeFileHandle%, First&, Btree
WEND
BtreeFirst = First&
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'//
FUNCTION BtreeIndex (BtreeFileHandle As Integer) As Integer
LOCAL TempBtree     As BtreeType
LOCAL BtreeReady    As Integer
LOCAL N             As Long
LOCAL RecNo         As Long
LOCAL TotalRecs     As Long
N& = 0
TotalRecs& = LOF (BtreeFileHandle%) \ LEN (Btree)
GET #BtreeFileHandle%, 1, TempBtree
TempBtree.Smaller   = 0
TempBtree.Bigger    = 0
TempBtree.Previous  = 0
TempBtree.DeleteKey = SPACE$ (1)
PUT #BtreeFileHandle%, 1, TempBtree
FOR RecNo& = 2 TO TotalRecs&
  GET #BtreeFileHandle%, RecNo&, TempBtree
  TempBtree.Smaller = 0
  TempBtree.Bigger = 0
  TempBtree.Previous = 0
  N& = 1
  IF TempBtree.DeleteKey = "*" THEN
    GET #BtreeFileHandle%, 1, Btree
    IF Btree.Previous = 0 THEN
      Btree.Previous = RecNo&
      PUT #BtreeFileHandle%, 1, Btree
      N& = 1
    ELSE
      N& = Btree.Previous
      GET #BtreeFileHandle%, N&, Btree
      WHILE Btree.Bigger > 0
        N& = Btree.Bigger
        GET #BtreeFileHandle%, N&, Btree
      WEND
      Btree.Bigger = RecNo&
      PUT #BtreeFileHandle%, N&, Btree
    END IF
    TempBtree.Previous = N&
    PUT #BtreeFileHandle%, RecNo&, TempBtree
  ELSE
    BtreeReady% = 0
    DO
      GET #BtreeFileHandle%, N&, Btree
      SELECT CASE TempBtree.IndexKey
      CASE < Btree.IndexKey
        SELECT CASE Btree.Smaller
        CASE 0
          Btree.Smaller = RecNo&
          Btree.DeleteKey = " "
          PUT #BtreeFileHandle%, N&, Btree
          TempBtree.Previous = N&
          TempBtree.DeleteKey = " "
          PUT #BtreeFileHandle%, RecNo&, TempBtree
          BtreeReady% = -1
        CASE ELSE
          N& = Btree.Smaller
        END SELECT
      CASE >= Btree.IndexKey
        SELECT CASE Btree.Bigger
        CASE 0
          Btree.Bigger = RecNo&
          Btree.DeleteKey = " "
          PUT #BtreeFileHandle%, N&, Btree
          TempBtree.Previous = N&
          TempBtree.DeleteKey = " "
          PUT #BtreeFileHandle%, RecNo&, TempBtree
          BtreeReady% = -1
        CASE ELSE
          N& = Btree.Bigger
        END SELECT
      END SELECT
    LOOP UNTIL BtreeReady%
  END IF
NEXT RecNo&
BtreeChanged% = -1
EXIT FUNCTION
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'//
FUNCTION BtreeInsert (BtreeFileHandle As Integer, _
                      KeyIndex        As Integer, _
                      Duplicate       As integer, _
                      RecordNumber    As Long) As Long
 LOCAL Temp        AS BtreeType
 LOCAL DeleteKey   AS BtreeType
 LOCAL N           As Long
 LOCAL TotalRecs   As Long
 LOCAL Place       As Long
 LOCAL PreviousDel As Long
 LOCAL FoundRec    As Integer
 LOCAL Present     As Long
 LOCAL DeleteUsage As Integer
 LOCAL WriteRecord As Integer
 BtreeChanged%    = 0
 Present&         = 0
 DeleteUsage%     = 0                             ' Flag
 TotalRecs& = LOF(BtreeFileHandle%) \ LEN (Btree)
 GET #BtreeFileHandle%, 1, DeleteKey
 IF DeleteKey.Previous > 0 THEN
   N& = DeleteKey.Previous
   GET #BtreeFileHandle%, DeleteKey.Previous, DeleteKey
   WHILE DeleteKey.Bigger > 0
    N& = DeleteKey.Bigger
    GET #BtreeFileHandle%, N&, DeleteKey
   WEND
   Place& = N&
   PreviousDel& = DeleteKey.Previous
   GET #BtreeFileHandle%, PreviousDel&, DeleteKey
   IF PreviousDel& = 1 THEN
      DeleteKey.Previous = 0
   ELSE
      DeleteKey.Bigger = 0
   END IF
   DeleteUsage% = -1
 ELSE
   Place& = TotalRecs& + 1
 END IF
 N& = 1
 WriteRecord% = -1
 FoundRec%      = 0
 DO
  GET #BtreeFileHandle%, N&, Temp
  SELECT CASE Btree.IndexKey
  CASE < Temp.IndexKey
    SELECT CASE Temp.Smaller
      CASE 0
      Temp.Smaller = Place&
      FoundRec% = -1
      CASE ELSE
      N& = Temp.Smaller
    END SELECT
  CASE > Temp.IndexKey
    SELECT CASE Temp.Bigger
      CASE 0
        Temp.Bigger = Place&
        FoundRec% = -1
      CASE ELSE
        N& = Temp.Bigger
    END SELECT
  CASE ELSE
    IF Duplicate% THEN
      SELECT CASE Temp.Bigger
      CASE 0
        Temp.Bigger = Place&
        FoundRec% = -1
      CASE ELSE
        N& = Temp.Bigger
      END SELECT
    ELSE
      Present&       = N&
      FoundRec%      = -1
      WriteRecord%   = 0
    END IF
  END SELECT
LOOP UNTIL FoundRec%
IF WriteRecord% THEN
  IF DeleteUsage% THEN
    IF PreviousDel& <> N& THEN
      PUT #BtreeFileHandle%, PreviousDel&, DeleteKey
    ELSE
      Temp.Previous = 0
    END IF
  END IF
  PUT #BtreeFileHandle%, N&, Temp
  Btree.Smaller      = 0
  Btree.Bigger       = 0
  Btree.Previous     = N&
  Btree.DeleteKey    = SPACE$ (1)
  Btree.RecordNumber = RecordNumber&
  PUT #BtreeFileHandle%, Place&, Btree
  BtreeChanged% = -1
Else
  BtreeInsert = Present&
END IF
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// GET THE LAST ELEMENT OF THE BTREE INDEX

FUNCTION BtreeLast (BtreeFilehandle As Integer) As Long
LOCAL Last    As Long
GET #BtreeFileHandle%, 1, Btree
IF Btree.Bigger > 0 THEN
  BtreeLast = Btree.Bigger
ELSEIF Btree.Smaller > 0 THEN
  BtreeLast = Btree.Smaller
ELSE
  BtreeLast = 0
  EXIT FUNCTION
END IF
GET #BtreeFileHandle%, Last&, Btree
WHILE Btree.Bigger > 0
  Last& = Btree.Bigger
  GET #BtreeFileHandle%, Last&, Btree
WEND
BtreeLast = Last&
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// OPEN THE BTREE INDEX
FUNCTION BtreeOpen(BtreeFile As String, BtreeFileHandle As Integer) As Long
LOCAL Filler    As String
LOCAL Counter   As Integer
LOCAL Recs      As Long
LOCAL Indexes   As integer
Indexes = Btree.Indexes
Filler = "!!!!!!!!!!!!!!!!!!!!!!!!!"
OPEN BtreeFile$ FOR RANDOM AS #BtreeFileHandle% LEN = LEN (Btree)
IF LOF (BtreeFileHandle%) = 0 THEN
  For Counter% = 0 To Indexes - 1
      Btree.IndexKey  = Filler
      Btree.Smaller   = 0
      Btree.Bigger    = 0
      Btree.Previous  = 0
      Btree.DeleteKey = "H"
  Next
  PUT #BtreeFileHandle%, 1, Btree
ELSE
  Recs& = LOF(BtreeFileHandle%) \ LEN (Btree)
  IF Recs& * CLNG (LEN (Btree)) <> LOF (BtreeFileHandle%) THEN
    BtreeOpen = -1
    CLOSE
    EXIT FUNCTION
  Else
    BtreeOpen = Recs&
  END IF
END IF
END FUNCTION

'//===========================================================================
'// CLOSE THE BTREE INDEX
FUNCTION BtreeClose(BtreeFileHandle As Integer) As Integer
CLOSE #BtreeFileHandle%
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// GET THE NEXT RECORD IN THE BTREE INDEX
FUNCTION BtreeNext (BtreeFileHandle As Integer, N As Long) As Integer
LOCAL OK        As Integer
LOCAL Niveau    As Long
IF Btree.Bigger > 0 THEN
  GOSUB BtreeZoekKleinste
ELSE
  IF N& > 1 THEN
    OK% = 0
    DO
      Niveau& = N&
      N& = Btree.Previous
      GET #BtreeFileHandle%, Btree.Previous, Btree
      IF Btree.Smaller = Niveau& THEN
        IF N& = 1 THEN
          GOSUB BtreeZoekKleinste
          OK% = -1
        ELSE
          OK% = -1
        END IF
      ELSE
        IF N& = 1 THEN
          N& = 0
          OK% = -1
        END IF
      END IF
    LOOP UNTIL OK%
  ELSE
    IF Btree.Bigger > 0 THEN
      GOSUB BtreeZoekKleinste
    ELSE
      N& = 0
    END IF
  END IF
END IF
EXIT FUNCTION
BtreeZoekKleinste:
N& = Btree.Bigger
IF N& > 0 THEN
  GET #BtreeFileHandle%, N&, Btree
  WHILE Btree.Smaller > 0
    N& = Btree.Smaller
    GET #BtreeFileHandle%, N&, Btree
  WEND
END IF
RETURN
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// ERASE THE RECORD IN THE BTREE INDEX
FUNCTION BtreeErase (BtreeFileHandle As Integer, DeleteRecNo As Long) As Integer
LOCAL BiggerLeaf  As BtreeType
LOCAL EraseBtree  As BtreeType
LOCAL SmallerLeaf As BtreeType
LOCAL N           As Long
GET #BtreeFileHandle%, DeleteRecNo&, EraseBtree
IF EraseBtree.Smaller > 0 THEN
  IF EraseBtree.Bigger > 0 THEN
    N& = EraseBtree.Bigger
    GET #BtreeFileHandle%, N&, BiggerLeaf
    BiggerLeaf.Previous = EraseBtree.Previous
    PUT #BtreeFileHandle%, N&, BiggerLeaf
    WHILE BiggerLeaf.Smaller > 0
      N& = BiggerLeaf.Smaller
      GET #BtreeFileHandle%, N&, BiggerLeaf
    WEND
    BiggerLeaf.Smaller = EraseBtree.Smaller
    PUT #BtreeFileHandle%, N&, BiggerLeaf
    GET #BtreeFileHandle%, EraseBtree.Smaller, SmallerLeaf
    SmallerLeaf.Previous = N&
    PUT #BtreeFileHandle%, EraseBtree.Smaller, SmallerLeaf
    GET #BtreeFileHandle%, EraseBtree.Previous, Btree
    IF Btree.Smaller = DeleteRecNo& THEN
      Btree.Smaller = EraseBtree.Bigger
    ELSEIF Btree.Bigger = DeleteRecNo& THEN
      Btree.Bigger = EraseBtree.Bigger
    END IF
    PUT #BtreeFileHandle%, EraseBtree.Previous, Btree
  ELSE
    GET #BtreeFileHandle%, EraseBtree.Smaller, Btree
        Btree.Previous = EraseBtree.Previous
    PUT #BtreeFileHandle%, EraseBtree.Smaller, Btree
    GET #BtreeFileHandle%, EraseBtree.Previous, Btree
    IF Btree.Smaller = DeleteRecNo& THEN
      Btree.Smaller = EraseBtree.Smaller
    ELSEIF Btree.Bigger = DeleteRecNo& THEN
      Btree.Bigger = EraseBtree.Smaller
    END IF
    PUT #BtreeFileHandle%, EraseBtree.Previous, Btree
  END IF
ELSE
  IF EraseBtree.Bigger > 0 THEN
    GET #BtreeFileHandle%, EraseBtree.Bigger, BiggerLeaf
    BiggerLeaf.Previous = EraseBtree.Previous
    PUT #BtreeFileHandle%, EraseBtree.Bigger, BiggerLeaf
    GET #BtreeFileHandle%, EraseBtree.Previous, Btree
    IF Btree.Smaller = DeleteRecNo& THEN
      Btree.Smaller = EraseBtree.Bigger
    ELSEIF Btree.Bigger = DeleteRecNo& THEN
      Btree.Bigger = EraseBtree.Bigger
    END IF
    PUT #BtreeFileHandle%, EraseBtree.Previous, Btree
  ELSE
    GET #BtreeFileHandle%, EraseBtree.Previous, Btree
    IF Btree.Smaller = DeleteRecNo& THEN
      Btree.Smaller = 0
    ELSEIF Btree.Bigger = DeleteRecNo& THEN
      Btree.Bigger = 0
    END IF
    PUT #BtreeFileHandle%, EraseBtree.Previous, Btree
  END IF
END IF
EraseBtree.Previous   = 0
EraseBtree.Smaller    = 0
EraseBtree.Bigger     = 0
EraseBtree.DeleteKey  = "*"
PUT #BtreeFileHandle%, DeleteRecNo&, EraseBtree
GET #BtreeFileHandle%, 1, Btree
IF Btree.Previous = 0 THEN
  Btree.Previous = DeleteRecNo&
  PUT #BtreeFileHandle%, 1, Btree
  N& = 1
ELSE
  N& = Btree.Previous
  GET #BtreeFileHandle%, N&, Btree
  WHILE Btree.Bigger > 0
    N& = Btree.Bigger
    GET #BtreeFileHandle%, N&, Btree
  WEND
  Btree.Bigger = DeleteRecNo&
  PUT #BtreeFileHandle%, N&, Btree
END IF
GET #BtreeFileHandle%, DeleteRecNo&, Btree
Btree.Previous = N&
PUT #BtreeFileHandle%, DeleteRecNo&, Btree
BtreeChanged% = -1
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'// SEARCH FOR A KEY IN THE BTREE INDEX
FUNCTION BtreeSearch(BtreeFileHandle As Integer, _
                     KeyIndex        As integer, _
                     SearchKey       As String, _
                     Exact           As integer) As Long
LOCAL N     As Long
LOCAL Ready As Integer
SearchKey$ = LEFT$ (SearchKey$ + SPACE$ (LEN (Btree.IndexKey)), LEN (Btree.IndexKey))
N& = 1
Ready% = 0
DO
  GET #BtreeFileHandle%, N&, Btree
  SELECT CASE SearchKey$
    CASE < Btree.IndexKey
      SELECT CASE Btree.Smaller
       CASE 0
        IF Exact% THEN
           N& = 0
        END IF
      Ready% = -1
    CASE ELSE
      N& = Btree.Smaller
    END SELECT
  CASE > Btree.IndexKey
    SELECT CASE Btree.Bigger
    CASE 0
      IF Exact% THEN
         N& = 0
      ELSE
        CALL BtreeNext (BtreeFilehandle%, N&)
      END IF
      Ready% = -1
    CASE ELSE
      N& = Btree.Bigger
    END SELECT
  CASE ELSE
    Ready% = -1
  END SELECT
LOOP UNTIL Ready%
BtreeSearch = Btree.RecordNumber
END FUNCTION

------------------

[Steven Pringels 3]

'//===========================================================================
'//
FUNCTION PBMAIN ()
  DIM Rec              As PtSampleRec
  DIM hFile            As Long
  DIM NrRecs           As Long
  DIM estart           As Long
  Dim tstart           As Long
  Dim GetRec           As Long
  DIM BtreeFilehandle  As Integer
  Dim Currec           As Long
  ON ERROR GOTO Foutje
  BtreeFile$ = "Btree.IDX"
  hFile& = FreeFile
  OPEN "PTSAMPLE.DAT" FOR RANDOM AS hFile& LEN = SIZEOF(rec)
  BtreeFileHandle% = FreeFile
  BtreeOpen BtreeFile$, BtreeFilehandle%
  nrrecs& = LOF(hFile&) \ SIZEOF(rec)
  print "indexing " & str$(nrrecs&) & " records...."
  tstart = Timer
  For currec& = 1 To nrrecs&
    GET hfile&, currec&, rec
    Btree.IndexKey = rec.Lastname
    Btreeinsert Btreefilehandle, 0, 1, Currec&
    Btree.IndexKey = rec.Firstname
    Btreeinsert Btreefilehandle, 1, 1, Currec&
  Next
  estart = timer
  print "Took " & Str$(estart- tstart) & " seconds."
  tstart = timer
  print "Searching for record on lastname..."
  GetRec = btreeSearch (BtreeFileHandle%, 0, "OLAYO", 1)
  print "took " & Str$(estart- tstart) & " seconds."
  Get hFile&, GetRec, Rec
  print rec.lastname, rec.firstname
  tstart = timer
  print "Searching for record on firstname..."
  GetRec = btreeSearch (BtreeFileHandle%, 1, "EDWARD", 1)
  print "took " & Str$(estart- tstart) & " seconds."
  Get hFile&, GetRec, Rec
  print rec.lastname, rec.firstname
  BtreeClose BtreeFileHandle%
CLOSE
StopProgramma:
EXIT FUNCTION
Foutje:
CLOSE
END FUNCTION

------------------