Memory Map in C++

[Man4ish]

I am working on file indexing and successful in indexing and retrieving the records. But If file is too big having millions of records then it takes to read the index file. Is there any way that index is stored in memory and when i run my program i can use that map?

Manish

[weaknessforcats]

If there are millions of records, why are you not using SQL?

For very large files, indexes may reside partly in memory an partly on disc using a thing called a segment index.

It may be that you are redeveloping the database software industry instead of using already written code. I mean, there's the Access JET Engine, Oracle, MS SQL Server, MySQL, etc...

[Man4ish]

@weaknessforcats
As per my project guidelines i am not supposed to use mysql.
How segmentation index works?Is there any tutorial with sample code, so that being a novice in this area i can use it properly.

Manish

[weaknessforcats]

OK, but you are in for a lot of work.

First, you need to segment your keys by ranges. Let's say, by the first character of the key. You will build 128 index files.

Second, you will read your millions of records and locate all keys plus the offset from the front of the file. You will build a record consisting of the key and the offset. Records with keys starting with letter 1 go in file 1. Records with keys starting with letter 1 go in file 2.

You now have your millions of records broken into 128 segments.

Third, you now create a 2-3-4 binary tree for each of these 128 files. 2-3-4 trees can be found in any textbook. In this tree you have the key plus offsets in the tree for the children plus the offset for the key in the millions of records.

Fourth, you write the segment index binary tree to a disc file and mange it there rather than in memory. That way you read the millions of records once and create the index file once. Since it is a 2-3-4 tree, it never needs rebalancing.

Fifth, you can now delete the 128 segments keeping only the 128 segment index files.

Six, to access a record, you ask the user for the key. From the first character of the key you open the correct segment index file.

Seven, using your own code, you access the segment index file as a 2-3-4 tree intil you have a complete match on the key. That leaf will have the offset into the millions of records. You then read thay file to get your data.

Eight, you may wish to break your millions of records into segment files to avoid file size limitations.

Nine, I would package all of this code carefully. This would be a complete database access system that you should be able to use for the rest of your life.
I have written these things and my experience says this is about a 1000-hour job.

Ten, add protections for multithreading and you are good to go.

Truly, a SQL solution is your best bet. Any project you work on should not require you to handle millions of records. If it's a business project you would use SQL. If it's a class project, it needs to be much, much simpler.

[Man4ish]

@weaknessforcats
Thank you very much for your detailed reply. I am very much happy to see this answer.I am really thankful to you. And will proceed the way you explained.

Manish

[JosAH]

I moved this thread from the C/C++ Insights part because it doesn't belong there.

kind regards,

Jos