The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Skip-list, avl tress where do you use them in a web application

Hello guys

I have repeatedly seen people like Yahoo groups founder Mark Fletcher and a few others... have repeatedly pushed for using skiplists.. in your web application...

I use Tsearch2 to do searching in postgresql which internally used Search inverted index.

So i m not so sure of where to use them?
Mark Send private email
Tuesday, February 06, 2007
You are comparing different things: data structures (avl, skip-list) vs. search algorithm (tsearch2).  And you are comparing different technology domains: programming vs. database.

It makes sense to use a database when you need the features it offers (ACID), and typically many clients needing to share the data.  If you do not need the features then it just unnecessary overhead.  Say you are writing an application that accepts input from the user, if said input is transient then you probably do not want to store in a database to operate on it.

The two data structures are probably highlighted because they perform better than traditional lists and unbalanced search trees.  Look up their performance profiles to see where.

Hope that helps?

Allan Wind Send private email
Wednesday, February 07, 2007
Nobody ever wants a skip list, an AVL tree, or a hash table.

What they want is an efficient name-value pair mapping. The Abstract Data Type "Dictionary" can be implemented using any of the above data structures.

If you're rolling your own, skip lists have the advantage of being easy to implement and having a good constant time coefficient. However, these days there's not a lot of reason to roll your on in the presence of lots of good libraries.
Chris Tavares Send private email
Thursday, February 08, 2007

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz