B+ Tree versus Ternary Search Tree

Discussion in 'Java' started by Ramkumar Menon, Aug 16, 2005.

  1. Hi All,

    Was looking out for some benchmarking for B+ Trees vis-a-vis Ternary
    Search Trees.

    a) For structured search

    For instance, user needs to search for some entity. He does so by
    giving a set of name-value pairs.

    e.g. the search key would be something like propertyName1=value1 or
    propertyName2=value2 or propertyName=value3 .....

    The "or" can be replaced by "and" too.
    The values could be wildcard characters.


    b) For unstructured search

    User gives only a value. The search implementation figures out the
    entity based on the value specified.
    For instance, user might give a customerId, or a displayName, or a
    owningEntity that may or may not be unique across all entities. In that
    case, all matching entities/any one of the matching entities cd be
    returned.

    In both these cases, which one should I choose to use ?
    Ramkumar Menon, Aug 16, 2005
    #1
    1. Advertising

  2. Ramkumar Menon

    Roedy Green Guest

    On 16 Aug 2005 01:53:01 -0700, "Ramkumar Menon"
    <> wrote or quoted :

    >a) For structured search
    >
    >For instance, user needs to search for some entity. He does so by
    >giving a set of name-value pairs.
    >
    >e.g. the search key would be something like propertyName1=value1 or
    >propertyName2=value2 or propertyName=value3 .....
    >
    >The "or" can be replaced by "and" too.
    >The values could be wildcard characters.


    I take it the thing you are looking for has a name, and a variable
    number of propertyName=value pairs.

    You want to index each node multiple times, once for each
    property/value pair.

    You could do that with a TreeMap if you always look things up by exact
    property/values. To deal with wildcards, you need additional indexes
    to deal with the various flavours of wildcard to let you linearly
    search.

    When you searched, you would get a list of nodes that matched each
    propertyName/value key pair. They would be conveniently sorted by
    node. You would have to do the and/or logic yourself on the result
    lists, or generate the merged list as you went.

    There is only one built in TreeMap implementation. I would not
    consider replacing it until the project were complete and it were
    proved the TreeMap truly were a bottleneck. You likely won't do much
    better. Sun would have picked a good general implementation and would
    have had better than average programmers code it.
    Roedy Green, Aug 16, 2005
    #2
    1. Advertising

  3. Ramkumar Menon

    Roedy Green Guest

    On 16 Aug 2005 01:53:01 -0700, "Ramkumar Menon"
    <> wrote or quoted :

    >In both these cases, which one should I choose to use ?


    The best way to answer that is to measure. You can only measure once
    you have got your surrounding implementation ready and some realistic
    data. The nice thing about Java is you can postpone such a decision
    until very late in the game.
    Roedy Green, Aug 16, 2005
    #3
    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. Matthew Louden
    Replies:
    1
    Views:
    6,906
    Scott M.
    Oct 11, 2003
  2. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    0
    Views:
    435
    Ramkumar Menon
    Aug 16, 2005
  3. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    1
    Views:
    453
    Andrew Thompson
    Aug 16, 2005
  4. rasmus ekman

    ternary tree (ann)

    rasmus ekman, Feb 14, 2006, in forum: C++
    Replies:
    0
    Views:
    734
    rasmus ekman
    Feb 14, 2006
  5. Paul Butcher
    Replies:
    12
    Views:
    705
    Gary Wright
    Nov 28, 2007
Loading...

Share This Page