Most efficient data structure?

Posted on 2000-03-27
Last Modified: 2010-04-16
First - I'm "cross-posting" this ques. under Pascal and Java - someone may want to flame me for doing so - but I can't find the "rules" on "cross-posting" for this site.

Anyway, regarding different data structures and the time it takes to search, insert, deleting, etc. - what is the most efficient structure and why?  I'm working on a project where I'm using a B-tree, but I'm just wondering if there is something better.  I have to be able to do both types of functions - retrieve data and manipulate data - search, and add/dele, etc.

Any ideas?  And can you explain your reasoning?

Also - if you take the time and give a thoughtful answer, please let me know what number of points should be awarded.  I'm still getting used to how everyone weighs their questions - I haven't found any logic.  I think it may be an easy answer for someone - I myself find it more difficult, otherwise I wouldn't be asking the question.  So if you can help me out, I'm willing to give you whatever points are really deserved.  

If you need more explanation as for the program/project let me know, but I'm really looking for what is the most efficient data structure.

Thanks - Dawn D.
Question by:jrddcd
  • 2

Expert Comment

by:Jan Louwerens
ID: 2662628
Usually, for cross-posting, you would just ask the question in one topic area, and then in other topic areas, just ask a 0 point question with a URL to the original question, and an explanation.

About your question, the most efficient data structure fully depends on what you intend to do with it. There is no best general data structure, otherwise that would be the only one ever used. You would have to describe what you want to do in order to get an acceptable answer.

Expert Comment

ID: 2662651
Dawn - Unfortunately, given the generic nature of your question, there is no simple, one size fits all answer.

You need to consider the trade offs between "time" and "space".  While you may optimize the "time" of an algorithm (and the accompanying data strucutures required to implement the algorithm), this often negatively impacts the "space" used by the data structures.  And of course, the converse is true - optimizing for space, usually hurts performance.  And  still, both of these impact other users on multi-user systems, and other programs on your single-user PCs. If you use too much space, you end up thrashing a system in terms of memory.  And if you use too much of the CPU optimzing for time, you hog the CPU from other apps/users (although this is controlled somewhat in multi-user OSs such as Unix).

The first question that needs to be answered is what are you trying to optimize - time or space?  And then, which operations are the most crritical - add, delete, sort...?

Each algorithm and accompanying data-structure has its own time/space characteristics.  These are referred to as by the term O  (pronounced ohhh), and then followed by the time/space required relative to the unit; for example, a sort algorithm may be O(n^2) (pronounced: ohhh of n squared) time and O(n) space, indicating that it takes n-squared visits to each element on the average, and n units of space to maintain each element to sort the entire population of n elements.

B-Trees are excellent, as are AVL trees.  But certainly they are overkill or inefficient for very small datasets.  If the data set is very large, these algorithms make more sense.  So, you can also see that the size of your anticipated dataset must also be considered.

An additional consideration is how the data will be stored - is this data only going to be used in core (in RAM), or will the data be written out to the disk?  And if written out, how often?  Each operation?  During startup/shutdown of the program?

The Macintosh Filesystem for example is implemented using a B-Tree - it is very fast, but requires a large B-Tree database to be written to disk, which becomes corrupted at times, and needs to be rebuilt.

A basic Data Structures and Algorithms book will give you the O values for various algorithms and their operations (add, delete, sort, etc.).

Does this help?

Accepted Solution

MikeCappella earned 50 total points
ID: 2665153
Comment changed to answer

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now