Pocket PC flat file database search engine

• Download demo project - 49.2 Kb

Introduction

One of my projects is to solve a problem of database searching speed. The first version of the application uses ADOCE. My client wants to convert flat text file from PC to Pocket PC database via ActiveSync. We kept getting calls from them complaining about the speed of conversion after the first version was released.

Then I did some testing on a 5000 records small database. It took around 20 minutes to do that. That was unacceptable. Therefore, I decided to use a flat text file as database container since our application uses it as read only.

The first thing we have to do is to sort our text file. The demo project includes a testing database (MyFile.txt). It is a pure flat text file. Each line has two columns separated by the “|” letter. (You can define your own separation letter.) The first column will be the searching index.

Click the Load button, the system will open MyFile.txt, sort it and load it into your system memory. I use Fast Quick Sort algorithm (see List1 and List 2) for sorting. The result is stored in a retarray variable, and uses binary searching algorithm to perform the searching function (see List3).

I was very much satisfied with the result. It only took 30 seconds to transfer the text file from PC to PPC and another 30 seconds to sort it. The binary searching algorithm is very efficient. The demo project will display the searching time and how many items searched during one search.

List1

Private Function QuickSort(l As Integer, r As Integer)
    Dim M, i, j, v
    M = 4
    If (r - l) > M Then
        i = (r + l) / 2
        If getkey(retarray(l)) > getkey(retarray(i)) Then
            swap l, i 'Tri-Median Methode!
        End If
        If getkey(retarray(l)) > getkey(retarray(r)) Then
            swap l, r
        End If
        If getkey(retarray(i)) > getkey(retarray(r)) Then
            swap i, r
        End If
        j = r - 1
        swap i, j
        i = l
        v = retarray(j)
        Do While (True)
            i = i + 1
            Do While (getkey(retarray(i)) < getkey(v))
                i = i + 1
            Loop
            j = j - 1
            Do While (getkey(retarray(j)) > getkey(v))
                j = j - 1
            Loop
            If (j < i) Then
                Exit Do
            End If
            swap i, j
        Loop
        swap i, r - 1
        QuickSort l, j
        QuickSort i + 1, r
    End If
End Function

List 2

Private Function InsertionSort(lo0 As Integer, hi0 As Integer)
    Dim i1, j1, v1
    For i1 = lo0 + 1 To hi0
        v1 = retarray(i1)
        j1 = i1
        Do While ((j1 > lo0))
            If (getkey(retarray(j1 - 1)) > getkey(v1)) Then
                retarray(j1) = retarray(j1 - 1)
                j1 = j1 - 1
            Else
                Exit Do
            End If
        Loop
        retarray(j1) = v1
    Next
End Function

List3

Function bisearch(Target As String, ByRef bk, _
                                 ByRef totalrec, ByRef searchcount)
    Dim midone, first, last, ret, temp
    Dim i
    ret = False
    first = 0
    last = UBound(retarray) - 1
    totalrec = last
    i = 0
    Do While (first <= last)
        midone = Round((first + last) / 2)
        'If Trim(oparray(midone)) <> "" Then
        temp = retarray(midone)
        temp2 = Split(temp, "|")
        If UCase(Trim(temp2(0))) = UCase(Trim(Target)) Then
            ret = True
            bk = temp
            Exit Do
        End If
        If UCase(Trim(temp2(0))) > UCase(Trim(Target)) Then
            last = midone - 1
        Else
            first = midone + 1
        End If
        i = i + 1
    Loop
    searchcount = i
    bisearch = ret
End Function