Database query on a non-dense index

I'm having trouble understanding what this question is asking:

Given a non-dense index on Attribute SALARY of Table EMPLOYEE, is it pos开发者_运维技巧sible to answer query

SELECT COUNT(*) FROM EMPLOYEE WHERE SALARY < 10,000

without performing a linear scan of the file? If not, how can you revise the non-dense index to enable a more efficient process?

I understand what the query is looking for but I don't really understand what the properties of a non-dense index are that relate to performing queries. Since there are values for salary that Employees won't necessarily have, then that means that index is non-dense?

If so, I don't see how I'm allowed to change the index to make the query more efficient.

---

A non-dense index has:

• One entry for each block
• One entry for each different value

A dense index has:

• One entry in index for each record

A non-dense index on Salary contains an entry for each different salary value, but not each record. So the index does not contain enough information to perform the COUNT(*) without reverting to a linear scan of the data file.

If the index on Salary was dense then you could perform

SELECT COUNT(*) FROM EMPLOYEE WHERE SALARY < 10,000

without a linear scan of the file.