Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've asked this question before and I got a few answers/idea but I'm not sure how to implement them.

I'm building a telecom messaging solution, currently I'm using Database to save my transaction/messages for the network stack I've built, and as you know it's slower than using data structure (hash, linkedlist, etc...), my problem is that the data can be really huge and it won't fit in the memory.

I was thinking of saving the records in a file and the a key and line number in a hash, then if I want to access some record then I can get the line number from the hash and get it from the file. I don't know how efficient is this, I think the DB is doing way better job than this on my behalf.

Please share whatever you have in mind.

share|improve this question
    
You can probably get a large speedup by making smarter use of the database, but you didn't provide enough details for anybody to help you figure that out. Typically though the bottleneck for this kind of application, is what parts of the serving pipeline hit the disk, and which disk accesses need to be synchronous. –  James Youngman May 9 '12 at 23:31
    
the question you say you asked before, is it this one? Is it better to use a Database or a data structure for network stack? –  gnat May 10 '12 at 11:04
add comment

4 Answers

A database solution can have different structures:

1-Using Random Access Method for Reading the File.

Using this approach, you don't need a database. You can open the file and use fseek (or similar method) to move to the desired row to perform your read. You may want to see a tutorial here: Random Access Function

2-Using database loaded table

This approach requires that you perform a load before you access the data. This complicates the solution slightly but the load should not be a problem if you use the database supplied loader and drop the indexes before load. To gain max. performance using this approach, you could build a clustering index on the desired key. This too will take few seconds even if you have millions of rows. At this point, your query will be very fast and nothing could probably beat this.

3-Using database External files (provided by Oracle and possibly by other databases)

This approach allows you to access rows using SQL without physical loading the file into the database. Advantages are ease of use by using SQL only and the fact that no database load need to be programmed or executed. You can dig further and see if such an access method allows partitioning without index build (assuming your data is already in order). It could then be very quick.

I would suggest that you try the solutions in the listed order and test the performance. I guess solution number 1 should be fastest if you have exact key.

share|improve this answer
    
Thank you Emmad –  poly May 10 '12 at 1:39
    
@poly, anytime! –  Emmad Kareem May 10 '12 at 10:31
add comment

An Inverted Index seems to be what you seek. The basic idea is:

  • The messages/files are saved on disk in their full structure.
  • Each word in the file has a row in a table in the database.
  • There's a link table that allows you to do a join between the words and a unique ID for each message/file.

For example, here's the 3 database tables as I would create:

CREATE TABLE words (
    word_id INT PRIMARY KEY,
    word TEXT
)
CREATE TABLE links (
    word_id INT FOREIGN KEY words(word_id),
    file_id INT FOREIGN KEY files(file_id),
)
CREATE TABLE files (
    file_id INT PRIMARY KEY,
    filename TEXT
)

To find all filenames that contain the words "help" and "me":

SELECT filename
FROM files
INNER JOIN links l1 ON (files.file_id = l1.file_id)
INNER JOIN words w1 ON (l1.word_id = w1.word_id)
INNER JOIN links l2 ON (files.file_id = l2.file_id)
INNER JOIN words w2 ON (l2.word_id = w2.word_id)
WHERE w1.word = "help" AND w2.word = "me"

That help?

share|improve this answer
    
Thanks a lot... –  poly May 10 '12 at 1:38
    
@poly If this is the best answer, be sure to accept it by clicking on the checkmark to the left. –  Izkata May 10 '12 at 2:08
add comment

B-Trees sound like exactly the data structure you might be looking for.

To quote the Wikipedia article:

...the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

share|improve this answer
add comment

You could try http://lucene.apache.org/core/ . It's full text search library which offers powerful features through a simple API. It's written in Java, but there's a .NET version: http://incubator.apache.org/lucene.net/

I've used it many Web/Desktop projects to implement enterprise search functionality.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.