Most efficient data structure?

Posted on 2000-03-27
Medium Priority
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 150 total points
ID: 2665153
Comment changed to answer

Featured Post

7 new features that'll make your work life better

It’s our mission to create a product that solves the huge challenges you face at work every day. In case you missed it, here are 7 delightful things we've added recently to monday to make it even more awesome.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
Why WooCommerce is one of the majorly favored choices when it comes to having an eCommerce store. This article will acquaint you with some reasons that I believe make it one of the best eCommerce platforms available.
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…
Simple Linear Regression

607 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