Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 79 ยท Storage and Indexing

Indexing Basics: Dense, Sparse, Primary and Secondary

Learn how ordered indexes work: dense vs sparse, primary vs secondary, clustering, multilevel and covering indexes, with SQLite query plans and a Python cost demo.

An index is a separate, small structure that helps the DBMS find rows without reading the whole table. It works like the index at the back of a book: a sorted list of terms, each with a page number. Instead of reading 400 pages to find "isolation", you look the word up and jump to page 212.

Indexes are the single biggest lever for query speed, and they come at a price: every index takes space and must be updated on every insert, update and delete of the indexed data. This lesson explains the vocabulary and the ideas behind ordered indexes (the next lessons dive into B+ trees and hashing). For the day-to-day SQL syntax of CREATE INDEX, see SQL Indexes.

What an index entry holds

Search key The column value you look up.
Pointer Where the row (or its page) lives.

Entries are kept sorted by the search key.

1 / 2

Primary, clustering and secondary indexes

Index names vary between books, so here are the meanings used in this tutorial.

  • A primary index is an index on the column by which the data file is sorted, and the search key is a key of the table. The file is ordered, and the index exploits that.
  • A clustering index is the same idea when the search key is not unique: records with equal keys sit together.
  • A secondary index is an index on any other column. The data file is not ordered by that column, so the index entries point to scattered places in the file.

The terms clustered (index order matches the file order) and non-clustered (it does not) say the same thing from the other side. A table has at most one clustered index, because the rows can be stored in only one order, but it may have many secondary indexes.

A primary key constraint and a primary index are related but not identical: the constraint is a logical rule, the index is a physical structure. Many engines happen to build the primary index for the primary key, others (SQLite for a text key, PostgreSQL) build a separate secondary index to enforce it.

Dense and sparse indexes

In a dense index there is one entry per record: every search key value of the file appears in the index. In a sparse index there is only one entry per data page, usually the smallest key on that page. A sparse index requires the data file to be sorted by the key (otherwise you cannot tell which page a missing key would sit in), so it can only be a primary or clustering index.

To find a key in a sparse index, look for the largest index entry that is smaller than or equal to the key, jump to that page and read it. If the key is on that page you find it, otherwise it does not exist.

Dense Sparse
Entries One per record One per data page
Size Large Small, records-per-page times smaller
Works for secondary indexes Yes No (needs a sorted file)
"Does this key exist?" without reading data Yes No, the data page must be read
Insert/delete cost Update an entry every time Update only when a page splits or empties

Secondary indexes on a non-unique column are usually dense, with one entry per record, or with an extra level of buckets of pointers so that a repeated key is stored only once.

Multilevel indexes

A big file produces a big index, and searching a big index costs many reads. The cure is to treat the index as a sorted file and put a sparse index on it. Repeat until the top index fits on a single page. The result is a multilevel index, and you read exactly one page per level plus one data page. A B+ tree is the practical version of that idea, which also copes with inserts.

The TryIt below builds a sorted file of 1,000 records (100 pages of 10), a dense and a sparse index, and counts the page reads for a lookup. Index pages hold 20 entries.

Python Dense, sparse and multilevel index sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each tuple printed is (found?, page reads). The sparse index is ten times smaller than the dense one, so searching it takes fewer reads, and it still finds the right data page. The multilevel version needs one read per level; with realistic page sizes, 3 or 4 levels cover billions of rows.

Indexes in SQLite

SQLite builds secondary indexes (B-trees) on request. The first TryIt creates a table of 2,000 employees and asks for the plan before and after adding an index on salary. Without it SQLite can only SCAN; with it, it can SEARCH and even answer a range.

SQL Creating an index and reading the plan

Press Run (or Ctrl + Enter) to see the result here.

The plans read SCAN emp, then SEARCH emp USING INDEX idx_emp_salary (salary=?), then the same index with (salary>? AND salary<?). In SQLite terms, idx_emp_salary is a secondary index: each entry holds the salary and the rowid, so the engine first searches the index and then fetches the row from the table by rowid.

Covering indexes

Following the pointer from the index to the data page costs an extra random read per matching row. If the index already contains every column the query needs, the engine can skip the table entirely. That is a covering index, shown by SQLite as USING COVERING INDEX.

Because an index entry stores the indexed columns plus the rowid, SELECT salary FROM emp WHERE salary = 3500 is already covered by idx_emp_salary. You can also add extra columns to the end of the key purely so that more queries are covered, at the cost of a larger index.

SQL Covering vs non-covering indexes

Press Run (or Ctrl + Enter) to see the result here.

The second plan uses idx_emp_dept_salary (dept=? AND salary>?) without the word COVERING, the third shows USING COVERING INDEX idx_cover, and the last one is again a plain index search. The indexed columns appear in (dept=? AND salary>?): equality on the first column, then a range on the second. Why column order matters is the subject of Bitmap, Composite, Partial and LSM Indexes.

Everything above runs in the browser with SQLite. Features such as INCLUDE columns (PostgreSQL, SQL Server) and index-organized tables with a clustered key (InnoDB, SQL Server) exist in other engines but are only mentioned here.

What an index costs

Operation Effect of one more index
SELECT with a matching predicate Often much faster
INSERT One more entry to write
DELETE One more entry to remove
UPDATE of an indexed column Remove and re-insert the entry
Disk space The index needs its own pages

So index the columns that appear in WHERE, JOIN and ORDER BY of frequent, slow queries. Do not index tiny tables, columns with very few distinct values (a boolean flag) or tables that are written far more often than read.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main difference between a dense and a sparse index?

    Sparse indexes are smaller because they point to pages, not records. That only works if the data file is sorted by the key.
  2. 2. Why can a table have only one clustered index?

    A clustered index defines the order of the data itself. Secondary indexes just point into it.
  3. 3. A SQLite plan says SEARCH emp USING COVERING INDEX idx_emp_dept_salary. What does COVERING tell you?

    All columns the query needs are stored in the index entries, so the extra lookup of the row is skipped.
  4. 4. Which situation makes an additional index a poor idea?

    Low selectivity means the index rarely narrows the search, yet every write still has to maintain it.

Summary

  • An index maps search keys to row locations; entries are kept in sorted order.
  • Dense indexes have one entry per record, sparse ones one per page (and need a sorted file). A multilevel index indexes the index, which is how B+ trees get their short height.
  • A clustered (primary or clustering) index matches the file order; secondary indexes do not, and a table can have many.
  • A covering index holds all columns a query needs and avoids the table lookup.
  • Indexes speed reads and slow writes, so choose them for frequent, selective queries.

Next: B-Trees and B+ Trees.