Why must a Primary Index be sparse?

Question

Reading Fundamentals of Database Systems 7th Edition, on Page 603, it says,

Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense) index, on the other hand, has index entries for only some of the search values. A sparse index has fewer entries than the number of records in the file. Thus, a primary index is a nondense (sparse) index, since it includes an entry for each disk block of the data file and the keys of its anchor record rather than for every search value (or every record).

Is that true though? As far as a database is concerned, if there are no sparse-indexes provided, is it said that all data-files have no "primary index"? I get that a specific designation for a sparse unique index on a block may be required, but is that what primary means? What does this mean for a database, like PostgreSQL, that implements Primary Keys on a dense btrees, and stores its rows in an unordered heap? Does it, technically, not have a "Primary Index"?

Answer 1

Without the context of the excerpt, I found it confusing since it seemed to depend on fairly specific implementation details. This is, in fact, the case. These course notes give a decent overview of this and related terminology.

A primary index refers to an index stored in sorted order on the sorting key of data stored in blocks. To look up a value, you do a binary search on the index which will produce a pointer to the block, and then you can do a binary search on the data in the block. If the data wasn't in blocks, there would be no point to this as you could just do binary search directly on the data file. (With a primary index, while the contents of the blocks need to be in sorted order, the blocks themselves don't necessarily need to be.) This index is not dense since it stores a pointer to a block which will typically contain multiple records, so there is not a one-to-one correspondence between index entries and records.

If you wanted to lookup data based on a key that the records are not sorted on, then you couldn't rely on records between index entries being in the same block, thus an index entry would be required for each specific record. This would be a dense index.

So the thing to note is that this terminology is referring to a specific way of storing and indexing data, namely as a collection of sorted blocks. "Primary index" has nothing to do with "primary key" in this terminology. A primary index depends on how the data is actually sorted (assuming it is sorted) which doesn't at all need to be based on the primary key, e.g. you may sort by a timestamp. There is no need for a "primary index" to exist at all.

A B-tree (and its variations) is just a different indexing approach entirely. You can still potentially apply the "dense index"/"sparse index" terminology to it. For example, if your data is sorted on the key the B-tree index is indexing, then it could just as well store only pointers to blocks and then perform a binary search within the block once fetched. This arrangement would produce a sparse index. You could easily imagine different arrangements that would produce a B-tree index that is dense.

I think you are viewing "primary index" as being more widely applicable than it is. I know I was at first which was the source of my confusion. In the context in which it applies, it is a reasonable term, but "primary index" is way too uninformative to stand alone.