-3

Is the purpose of the indexing data structures to address the limitations of disks?

If data is stored in RAM, do we still need index into data? Thanks.

Question comes from Design Data Intensive Applications

The data structures discussed so far in this chapter have all been answers to the limitations of disks. Compared to main memory, disks are awkward to deal with. With both magnetic disks and SSDs, data on disk needs to be laid out carefully if you want good performance on reads and writes. However, we tolerate this awkwardness because disks have two significant advantages: they are durable (their contents are not lost if the power is turned off), and they have a lower cost per gigabyte than RAM.

...

Besides performance, another interesting area for in-memory databases is providing data models that are difficult to implement with disk-based indexes. For example, Redis offers a database-like interface to various data structures such as priority queues and sets. Because it keeps all data in memory, its implementation is compara‐ tively simple.

  • 1
    The question is clear and focused. Why the adversaries? – Tim Dec 8 '19 at 15:56
  • My questions are specific problem from what I am reading and will be helpful for future practices. If "without such context, your question is unanswerable", then post why you think it is incorrect, but don't impose adversaries on my post. I am asking if it is correct, not claiming it is correct. That is clear and focused. – Tim Dec 8 '19 at 16:21
  • 2
    "needs" are driven by requirements. Certainly we can index and sort data in memory as well as on disc. – Erik Eidt Dec 8 '19 at 16:21
  • 1
    Well, I tried to make a guess what you are after and give you an equally broad answer to a very broad question. If that's not what you are looking for, please leave a comment. – Doc Brown Dec 8 '19 at 16:33
10

Indexes to data in RAM are well-known and widely used. They are usually not called indexes, they are often called dictionaries, maps, hashmaps, associative arrays, or key-value stores. I am pretty sure you have heard of them.

These data structures are useful for the same reason why disk-based indexes are useful for databases: to reduce the search time in a list of N elements from O(N) (for a naive linear search) to a sublinear order, ideally O(1).

Of course, if we focus on "in-memory" databases vs disk-based DBs, one can surely find (or construct) cases where an index for disk-based database table is required to meet the performance requirements of a specific problem, and if this disk-based database is replaced by an in-memory DB, the same requirements may be met without an index. But that depends on the specific case, the specific numbers, and it would definitely make neither sense to answer your question with "yes, we do not need indexes any more" or "no, indexes are still required in general". In reality, things are is not that simple as this question pretends they might be.

3

Is the purpose of the indexing data structures to address the limitations of disks?
No. The purpose of using keys or indices with different types of data structures is to allow for O(1) access. The partitioning of data on disks and the organization of data into RAM are two vastly different subjects, though they have some crossover.

If data is stored in RAM, do we still need index into data?
Yes, the use of indices in an array, for instance, allow for limited overhead in storage requirements. We can store the address of the beginning of the array, and the length of the entries. Then we simply multiply the length by the index and add that to the beginning address and voila, we have the exact address of the data we are looking for.

2

Yes, indexes are still essential for in-ram data, as soon as you have a large amount of data and need to find a particular item by looking it up with a key (rather than via its address).

It's basically the same reason why you need indexes for disk-based data, the main difference is that RAM access is much fast, especially random access (Harddisks are incredibly slow at that, literally millions of times slower). That makes the performance impact of indexes smaller (you can often get away with scanning through a few million elements) and it makes indexes much easier to implement (because you don't have to minimize random accesses as much).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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