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

Discussion in 'Javascript' started by Harry Haller, Oct 30, 2006.

  1. Harry Haller

    Harry Haller Guest

    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.
    Harry Haller, Oct 30, 2006
    #1
    1. Advertising

  2. Harry Haller

    Guest

    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
    , Oct 30, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Arnold
    Replies:
    5
    Views:
    318
    Diez B. Roggisch
    Nov 2, 2004
  2. Replies:
    6
    Views:
    12,955
    yasso
    Apr 2, 2009
  3. Fulvio

    The fastest search

    Fulvio, Oct 21, 2006, in forum: Python
    Replies:
    4
    Views:
    261
    Fulvio
    Oct 21, 2006
  4. Abby Lee
    Replies:
    5
    Views:
    396
    Abby Lee
    Aug 2, 2004
  5. Derek Cannon

    Fastest Array Search?

    Derek Cannon, Mar 30, 2010, in forum: Ruby
    Replies:
    8
    Views:
    148
    Derek Cannon
    Mar 30, 2010
Loading...

Share This Page