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 a database to save my transaction/messages for the network stack I've built, and as you know it's slower than using a 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 database is doing a way better job than this on my behalf.

Please share whatever you have in mind.

  • 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. Commented May 9, 2012 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
    Commented May 10, 2012 at 11:04

4 Answers 4


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:

    word_id INT PRIMARY KEY,
    word TEXT
    word_id INT FOREIGN KEY words(word_id),
    file_id INT FOREIGN KEY files(file_id),
    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?

  • @poly If this is the best answer, be sure to accept it by clicking on the checkmark to the left.
    – Izkata
    Commented May 10, 2012 at 2:08

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.


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.

  • @poly, anytime!
    – NoChance
    Commented May 10, 2012 at 10:31

You could try Lucene. It's a full text search library which offers powerful features through a simple API. It's written in Java, but there's a .NET version, Lucene.net.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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