Data structure for storing sorted data

What’s a good way to store loads of sorted string on a file so that inserts and reads are fast?

I could store it up in a tree, and read/modify/store it as needed, but that seems wasteful for operations like ‘seeking the nth object’. Isn’t there an indexed data structure that’s used specifically to store and retrieve sorted information?

Of course a database would work, but how databases store their index for faster access? I doubt they linear scan trough an index for figuring out the nth element of a list and they read/write all the index to update a single row in the middle.


If you are talking about huge data, you should consider using BTree data structure (or its variants). BTrees are used by most relational databases for indexing huge data.

You can check B-tree on Wikipedia for more details.

Based on the amount of data you have to deal with, your objective functions vary. For example, if you have to deal with very huge data, your objective function is to optimize (minimize) the number of disk reads(/seeks). In case you have to deal with small set of data (that can fit in your RAM), your objective function is to optimize (minimize) the number of CPU cycles.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *