1

I have a question in my textbook:

When is it preferable to use a dense index rather than a sparse index? Explain your answer.

My first thought was that the dense index would be good when it'd cost a cheap / worthwhile amount of space relevant to the performance gain. When I was googling for the answer (to verify), I found this answer in multiple places

It is preferable to use a dense index instead of a sparse index when the file is not sorted on the indexed field (such as when the index is a secondary index) or when the index file is small compared to the size of memory.

and it's not very clear to me what it's saying.


For the first reason

when the file is not sorted on the indexed field (such as when the index is a secondary index)

What is "the file", and likewise which field is "the indexed field", the field in the primary index or the one in the secondary index? Also just in general, I'm still not sure how this justifies the dense index.


For the second part

when the index file is small compared to the size of memory.

What is "the size of memory" in this context? Is this trying to say what I said? (the dense index is cheap to make?)


I'd really appreciate a better explanation/clarification of the above.

2

In context:

when the file is not sorted on the indexed field (such as when the index is a secondary index)

  • "the file" = the database table (or similar object) being indexed
  • "the indexed field" = the field being considered for the new index. A sparse index relies on the records being sorted in the same order as the indexed field.

Example: data in table is sorted on ID:

  ID    Last Name
   1    Smith
   2    Francis
   3    Jones
   4    Zygoski
   5    Bohr
   6    Josephson
   7    Michaels
   8    Able

And, imagine this is a sparse index on Last Name (with pointers to the appropriate records:

Index
  Able
  Francis
  Jones
  Smith

Now, to find "Bohr", You go to "Able" and then search sequentially. Unfortunately, "Able" is the last record in the file, so, you can't get to "Bohr" from there.

when the index file is small compared to the size of memory.

Basically, if the entire index can be loaded into memory, and still have plenty of room to load in the data from the table that's needed, then the database engine should be able to find each record in the index, and go directly to that record in the data table (instead of possibly having to pull in several pages from the table, scanning to locate the record it wants). If the dense index takes up too much room in memory, then either you have to read it in in parts, or it's going to squeeze the available memory for the rows you need from the data table.

Or, at least, that's my best guess. Note that I'm speaking form the view of someone who's been working with databases for almost 30 years; when I was in class, I don't remember dense vs sparse indexes being discussed.

| improve this answer | |
  • Awesome...much appreciated :) – m0meni May 4 '17 at 19:33

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.