Re: Splay tree vs Bin tree vs none of the above??

Steve Ollis writes:
> Which of these 3 should I be choosing from ?
>
> What are the impact of one against the other...

long search (was none of the above) - searches through the list of acl's
        from top to bottom, looking for the matching entry
Bin tree: this is a binary tree - fast for almost all searches (much faster
        than a sequential search above)
Splay tree: This is also a tree, but it dynamically re-adjusts the tree so
        that the "often-used" entries are searched first... this is useful
        if you have a lot of acl's (like we do - one for each of our
        routes). It is useful in cases where one of the acl's almost
        always matches and the rest aren't often used - only some of
        our customers use the cache, so it's useless if they are at the
        end of the list and we have to search the whole tree every
        time they connect... this moves the acl's that are never used
        so they are searched last.

hope that the info is all correct - I think the preference should
be "bin-tree" "splay-tree" "sequential" (unless you have lots of
acl's - a good few hundred - the splay tree won't help much, and
as far as I know it will slow down the lookups slightly.

(I am not a comp-sci person so I don't know how splay trees slow things
down vs bin-trees in cases where the data set searched is small)

Oskar
Received on Thu Jul 03 1997 - 02:45:57 MDT