What is the fastest way to search a (javascript) database?

[Harry Haller]

What is the fastest way to search a client-side database?

I have about 60-65 kb of data downloaded to the client which is
present in 3 dynamically created list boxes. The boxes are filled from
3 string arrays, which are just lists of people or companies in
alphabetic order. These names may have accented and umlauted
characters (which are present as the plain ASCII - not as the entity
&# character). The page is UTF-8 encoded.

e.g. strManager = "Adele Brown|Albert Meinstein|Alicia Perkins ..."

The first defect of the search is that it won't look for items
beginning with an umlaut etc.

The second defect is that it's far too slow.

The current page uses a regular expression search on the whole string
(it was taken from the O'Reilly regular expression book. Entering, for
instance, a 'b' in the search box results in the corresponding list
box showing ONLY those items beginning with a 'b' or 'B'. Likewise
entering 'Ba' narrows the search down even further. Unfortunately the
first letter search takes too much time.

What data structure is best used for holding the data for this search?

What is the best algorithm to use for such a search.

Should I construct a BST (binary-search-tree) on the server using the
IDs of the actual data items (with left and right pointers) - created
using Javascript arrays? With such a structure would a binary search
(BST) algorithm give me the fastest search?

OR, are BSTs normally constructed when data is being dynamically
added? All my data is static - the user only searches. In this case
do I simply need to order the data alphabetically and use a binary
chop to search it? PS: a typical search will need to select all items
beginning with a particular letter. Given that this will be the MAIN
search performed should I just create a second, 26 item, array
containing pointers to each first letter in my main array?

PS 1: For those, in news:alt.comp.programming, who don't know
Javascript has no pointers but supports arrays and associative arrays.

PS 2: in the server database all these names have IDs (but the
previous developer didn't download them to the client (to "save
space") - which explains the strManager above.

apologies to news:comp.lang.javascript for the duplicate post.

[scriptguru]

Harry Haller wrote:

What is the fastest way to search a client-side database?

I have about 60-65 kb of data downloaded to the client which is
present in 3 dynamically created list boxes. The boxes are filled from
3 string arrays, which are just lists of people or companies in
alphabetic order. These names may have accented and umlauted
characters (which are present as the plain ASCII - not as the entity
&# character). The page is UTF-8 encoded.

e.g. strManager = "Adele Brown|Albert Meinstein|Alicia Perkins ..."

The first defect of the search is that it won't look for items
beginning with an umlaut etc.

The second defect is that it's far too slow.

The current page uses a regular expression search on the whole string
(it was taken from the O'Reilly regular expression book. Entering, for
instance, a 'b' in the search box results in the corresponding list
box showing ONLY those items beginning with a 'b' or 'B'. Likewise
entering 'Ba' narrows the search down even further. Unfortunately the
first letter search takes too much time.

What data structure is best used for holding the data for this search?

What is the best algorithm to use for such a search.

Should I construct a BST (binary-search-tree) on the server using the
IDs of the actual data items (with left and right pointers) - created
using Javascript arrays? With such a structure would a binary search
(BST) algorithm give me the fastest search?

OR, are BSTs normally constructed when data is being dynamically
added? All my data is static - the user only searches. In this case
do I simply need to order the data alphabetically and use a binary
chop to search it? PS: a typical search will need to select all items
beginning with a particular letter. Given that this will be the MAIN
search performed should I just create a second, 26 item, array
containing pointers to each first letter in my main array?

PS 1: For those, in news:alt.comp.programming, who don't know
Javascript has no pointers but supports arrays and associative arrays.

PS 2: in the server database all these names have IDs (but the
previous developer didn't download them to the client (to "save
space") - which explains the strManager above.

apologies to news:comp.lang.javascript for the duplicate post.

Use hashes - they are very fast and handy. Much faster than search in
string and you can use umlauts etc. Ask me if you don't know how to use
hashes (and describe what kind of search users may perform).

Val Polyakh
http://trickyscripter.com