How efficient are databases?

Question

If databases can support up to a million records, how is all this data organized in such a way that queries can be executed within a reasonable amount of time?

Answer 1

Indices!

Wikipedia link for a full discussion on indexes

Answer 2

The full answer is the theme of numerous books and dissertations; -)

However, the main answer is that in all modern DBMSs there are several possibilities: Firstly, they have a query optimizer that is very efficient. This is to find a good (not always the best) way to respond to the request. Of course, this can do more to help complex issues than simple ones.

Secondly, they store data in a structured format that is easy to find. Data without a clustered index is called heap, and it is usually less efficient to search, but it is still structured data. Data typically contains a clustered index that logically organizes the data. (Some people believe that he physically orders the data. There is some truth in this, but this is not entirely true. Itzik Ben Gan, among others, has an excellent article debunking this belief).

In addition to the clustered index, non-clustered indexes are usually used. They are similar to indexes in a book, which can help the query optimizer where to look for the requested data, or in some specific cases the index itself may have all the necessary data.

This, of course, is a gross and terrible simplification. If you want a deep level of understanding, be prepared to continue your PHD in database theory. For an understanding of the general level, you can take a look at books on database internals. For SQL Server, in particular, SQL Server 2008 Internals has a lot of information on this topic.

Answer 3

I really like this explanation (including the graphics;)

This is an artistic conclusion:

Conclusion

_{(source: mattfleming.com )}

B-tree indexes are created to reduce the number of I / O operations needed to find and load a dataset. A highly selective index uses the least amount of I / O required; poorly selective indexes are not much better than table scans.