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"?


1 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.

  • $\begingroup$ What if the data is stored in an unordered heap (as PostgreSQL uses to store rows), would you call the indexing mechanism of the unordered heap a "Primary Index" if it is dense (because the blocks themselves are not ordered physically or logically). $\endgroup$ Jan 15, 2018 at 16:38
  • 1
    $\begingroup$ If the contents of blocks are not sorted by the field being indexed, then the index is not a primary index. Again, "primary index" is not an epithet you apply to indexing mechanisms that satisfy certain properties, it is itself a very specific indexing mechanism: a sorted table of pointers to sorted blocks. It is a specific data structure and associated algorithms, just as each of a B-tree, hash index, or bitmap index is a specific data structure with associated algorithms. $\endgroup$ Jan 15, 2018 at 19:10
  • $\begingroup$ I believe that the book refers to column by which the file is ordered when saying "primary key", and not to the column with unique values used to uniquely identify the records. For both either interpretation, I have three questions: (1) isnt it technically possible to have dense primary index? (2) Does actual RDBMS implementations (postgres, sql server, oracle etc) follow any specific approach? (2) Does author mean to say that primary key column (column with unique values used to identify records) cannot have dense index? $\endgroup$
    – RajS
    Jan 27, 2019 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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