B+ Tree versus Ternary Search Tree

[Ramkumar Menon]

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 ?

 

[Roedy Green]

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]

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.