Re: Tree ADT vs Database

djcredo@xxxxxxxxx wrote:
Hi all,

I have an application that currently works with two very large n-ary
trees. A lot of time is spent doing depth-first searches on these
trees.

I'm thinking of moving away from using trees to using a database
backend, and using SQL to query the database. Would I get any
performance improvement this way? What sort of datastructure does a
database use? What sort of Big-Oh times would I be likely to get?

Thanks in advance!
Matt

Matt,

As many of the posters have told you, whether a database using SQL is faster (or better) is dependent on how you plan to use and access that data. I have written memory based trees for speed and used SQL for longer term storage, etc.

Remember, that in order to "talk" to a database the db library has to transfer and parse/unparse SQL back and forth. In addition, there may be IPC, network and/or i/o latencies in communicating with a relational database like BD2 or MySQL. The extra overhead involved in doing SQL may be more time consuming than direct memory accesses involved in your own tree.

How many nodes are you keeping in memory? How big is a node? Is it read much more often than it is updated? Does it need to be persistant? How many nodes per second does your application access?

From my own personal experience, a relational database is slower than even a slow memory based tree. Also, normalization helps to compress the data. In accessing the data, the time required to de-normalize the data may require more time.

-Misk




.

Relevant Pages

  • Re: UUIDs (Was: Software implementing Gentech Genealogical Data Model)
    ... suggest is that an identifier based on some concatenation of data elements ... Now, the only time such a uuid would have any significance, or so it seems ... IDs are to be key for our database. ... trees can all be given UUIDs by combining the ID number of the tree ...
    (soc.genealogy.computing)
  • Re: New FamilySearch - are the gains worth the losses?
    ... If the member submissions on IGI are any guide to the trees I wouldn't want to download them! ... Because the new database doesn't support the one function ...
    (soc.genealogy.computing)
  • Re: Tree ADT vs Database
    ... trees. ... I'm thinking of moving away from using trees to using a database ... and using SQL to query the database. ... relational database data being stored as rows in tables; ...
    (comp.lang.java.programmer)
  • Re: Call for discussion...
    ... I would not put separate trees in a single file. ... If you're using some kind of database, the situation is a bit different ... Essentially you are saying safety first protects one's data. ...
    (soc.genealogy.computing)
  • Re: Update a field which has a running total
    ... Don't Print - Save trees ... Gordon wrote: ... <johnDOTsmithATbromleyhospitalsDOTnhsDOTuk> ... database until you have saved the record, this is the point when AfterUpdate ...
    (microsoft.public.access.formscoding)