---
title: 'Index Types'
source: 'https://academia.sh/en/courses/database-administration/index-types'
course: 'Relational Database Administration'
language: en
updated: '2026-08-23T07:00:42+00:00'
license: 'CC BY-SA 4.0'
---

# Index Types

The measured cost of an unindexed foreign key, the tree-based index's ability to answer range and order questions, the hash-based approach's equality-only operation, and the inverted index for word-level search.

The Engine Architecture topic closed with the system catalog, and it left behind a single
finding: the branch reference in the book table was unindexed. That finding was written as
a recommendation — "every column carrying a foreign key should have its own index."
Recommendations remain opinion until they are measured.

This lesson first turns that finding into a number, then moves on to its real question.
Query Performance introduced the index as a single structure: a sorted copy of the table
kept alongside it. In reality an index is not one structure but a family of structures, and
the members of the family are told apart by which question they can answer. One index type
answers equality but not range; another finds not the whole value but the words inside it.
The choice is made by looking at the shape of the question.

## The Finding Left Open

A foreign key constraint requires that a value in one table exist in another table. That
requirement also runs in the opposite direction: when a row is deleted from the parent
table, the engine must verify that no child row still refers to it. What determines how
that verification is carried out is whether the child column carries an index.

```sh
rm -f fk.db fk_indexed.db
sqlite3 fk.db <<'SQL'
PRAGMA foreign_keys = ON;
CREATE TABLE branch (branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL,
                    branch_id INTEGER NOT NULL REFERENCES branch(branch_id));
INSERT INTO branch VALUES (1,'Central'),(2,'Bahcelievler'),(3,'Kadikoy'),(4,'Beyoglu'),
                        (5,'Konak'),(6,'Nilufer'),(7,'Selcuklu'),(8,'Cankaya'),(9,'Warehouse');
INSERT INTO book (book_id, title, branch_id)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000)
SELECT n, 'Book ' || n, 1 + (n % 8) FROM s;
SQL
cp fk.db fk_indexed.db
sqlite3 fk_indexed.db 'CREATE INDEX book_branch ON book(branch_id);'

for db in fk.db fk_indexed.db; do
  printf '%s: ' "$db"
  sqlite3 "$db" <<'SQL'
PRAGMA foreign_keys = ON;
.stats vmstep
DELETE FROM branch WHERE branch_id = 9;
SQL
done
```

```
fk.db: VM-steps: 600013
fk_indexed.db: VM-steps: 15
```

The deleted branch carried no books at all; both runs delete exactly one row. The
difference is in the work performed: in the unindexed copy the engine looked at all two
hundred thousand books one by one and confirmed that none belonged to branch nine. In the
indexed copy the same check took fifteen steps — entering the index and seeing that key had
no entries was enough.

The ratio here is forty thousand-fold, and it grows with the table. This is the reason
behind the check written into the catalog: an index on a foreign key column is needed not
for read performance but for **every delete and key update on the parent table**. This cost
is invisible in query plans, because the statement that produces it is a `DELETE`
statement, and the expensive part is the constraint check.

## The Tree-Based Index

The index type used in Query Performance is the **tree-based index (tree index)**: a
structure, usually shaped as a B-tree, that keeps its entries sorted by key value.
Measurements run on the library dataset; the setup below is used throughout the topic.

```sh
rm -f library.db
cat > setup.sql <<'SQL'
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE loan (
  loan_id      INTEGER PRIMARY KEY,
  book_id      INTEGER NOT NULL,
  member_id    INTEGER NOT NULL,
  pickup_date  TEXT NOT NULL,
  return_date  TEXT
);
INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;
INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 library.db < setup.sql
sqlite3 library.db <<'SQL'
CREATE INDEX loan_pickup ON loan(pickup_date);
.print '--- equality ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats vmstep
SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats off
.print '--- range ---'
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-15' AND '2021-03-21';
.stats vmstep
SELECT count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-15' AND '2021-03-21';
.stats off
.print '--- minimum value ---'
EXPLAIN QUERY PLAN SELECT min(pickup_date) FROM loan;
.stats vmstep
SELECT min(pickup_date) FROM loan;
SQL
```

```
--- equality ---
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_pickup (pickup_date=?)
820
VM-steps: 2471
--- range ---
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_pickup (pickup_date>? AND pickup_date<?)
5744
VM-steps: 17245
--- minimum value ---
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_pickup
2018-01-01
VM-steps: 14
```

All three questions were answered from the index, and for one reason: **order**. Equality
descends the tree to a single key. Range descends to the lower bound and walks sideways
until the upper bound is passed; the climb from 2,471 steps to 17,245 steps tracks the
sevenfold increase in matching rows. The minimum-value question was answered in fourteen
steps — the leftmost entry in the index was read and the work was done.

The abilities that order provides form a list: equality, range, prefix, minimum and
maximum, a ready order for `ORDER BY`, duplicates arriving side by side for grouping. This
is why the tree-based index is the default type in every engine — a single structure
answers all of these questions.

## The Hash-Based Index

A **hash-based index (hash index)** does not index the key itself but the value the key
produces after passing through a hash function. This is the same structure built in the
Hash Tables lesson of the Data Structures course; the difference here is that the table
sits on disk rather than in memory.

Not every engine has a hash index. The run below models one with an **expression index**:
the day number of the date is passed through a multiplicative hash function, and the
indexed value becomes that hash. The model carries over the defining property of a real
hash index exactly — order in the index is not order in the value.

```sh
rm -f hash.db
sqlite3 hash.db < setup.sql
sqlite3 hash.db <<'SQL'
-- The value itself is not indexed; its multiplicative hash is.
CREATE INDEX loan_pickup_hash ON loan(
  (CAST(julianday(pickup_date) AS INTEGER) * 2654435761) % 4294967296 );
.print '--- hash value of the searched date ---'
SELECT (CAST(julianday('2021-03-15') AS INTEGER) * 2654435761) % 4294967296 AS hash_value;
.print '--- equality, queried through the hash ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan
  WHERE (CAST(julianday(pickup_date) AS INTEGER) * 2654435761) % 4294967296 = 2436359960;
.stats vmstep
SELECT count(*) FROM loan
  WHERE (CAST(julianday(pickup_date) AS INTEGER) * 2654435761) % 4294967296 = 2436359960;
.stats off
.print '--- same equality, queried through the date itself ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats vmstep
SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats off
.print '--- range ---'
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-15' AND '2021-03-21';
.stats vmstep
SELECT count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-15' AND '2021-03-21';
SQL
```

```
--- hash value of the searched date ---
2436359960
--- equality, queried through the hash ---
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_pickup_hash (<expr>=?)
820
VM-steps: 3292
--- same equality, queried through the date itself ---
QUERY PLAN
`--SCAN loan
820
VM-steps: 6000831
--- range ---
QUERY PLAN
`--SCAN loan
5744
VM-steps: 7046372
```

Three results say three separate things. Equality queried through the hash was answered in
3,292 steps — close to the tree index's 2,471 steps, in the same order of magnitude.

The second measurement shows the model's limit: the same equality, written against the
date column itself, did not use the index. In a real hash index, the engine performs this
conversion itself; the caller writes an ordinary equality and the engine computes the
search key's hash. In the model, the conversion has to be carried out by whoever writes the
query. What stays constant is this: **as long as the search key's hash can be computed**,
equality is answered.

The third measurement is the real distinction. The range query fell all the way to a full
table scan despite the index existing, spending 7,046,372 steps. The reason is structural:
the hash function is deliberately disordered. The hash values of two consecutive dates can
sit at opposite ends of the index. A range such as "between March 15 and March 21" has no
hash counterpart, because which hashes the values in between fall into cannot be computed —
not without trying each one individually.

From here the hash index's use case follows: columns queried only by equality, where range
and order are never wanted. What it earns in exchange is space; when long text keys collapse
into a fixed-size hash, the index shrinks. Giving up everything the tree index offers in
exchange for this gain is not the preferred trade in most deployments.

## The Inverted Index

A third family targets a different question. A tree index treats **the whole value** as
the key; this is why it answers prefix queries but cannot find a word sitting in the middle
of a value. Searching book subject headings in a library catalog is exactly this question.

```sh
rm -f subject.db
sqlite3 subject.db <<'SQL'
CREATE TABLE book_subject (book_id INTEGER PRIMARY KEY, subject TEXT NOT NULL);
INSERT INTO book_subject (book_id, subject)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000),
word(i, w) AS (VALUES (0,'astronomy'),(1,'geography'),(2,'history'),(3,'poetry'),(4,'novel'),
                        (5,'atlas'),(6,'dictionary'),(7,'handbook'),(8,'seamanship'),
                        (9,'architecture'),(10,'music'),(11,'philosophy'),(12,'cartography'),
                        (13,'botany'),(14,'mineralogy'),(15,'law'),(16,'theater'),
                        (17,'logic'),(18,'economics'),(19,'anatomy'))
SELECT n, (SELECT w FROM word WHERE i = n % 20)       || ' ' ||
          (SELECT w FROM word WHERE i = (n/20) % 20)  || ' ' ||
          (SELECT w FROM word WHERE i = (n/400) % 20)
FROM s;
CREATE INDEX subject_tree ON book_subject(subject);
CREATE VIRTUAL TABLE subject_inverted USING fts5(subject, content='book_subject', content_rowid='book_id');
INSERT INTO subject_inverted(subject_inverted) VALUES('rebuild');
SQL
sqlite3 subject.db <<'SQL'
PRAGMA case_sensitive_like = ON;
.print '--- tree index, left-anchored pattern ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM book_subject WHERE subject LIKE 'cartography seamanship%';
.stats vmstep
SELECT count(*) FROM book_subject WHERE subject LIKE 'cartography seamanship%';
.stats off
.print '--- same tree index, left-open pattern ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM book_subject WHERE subject LIKE '%cartography seamanship%';
.stats vmstep
SELECT count(*) FROM book_subject WHERE subject LIKE '%cartography seamanship%';
.stats off
.print '--- inverted index, same phrase ---'
EXPLAIN QUERY PLAN SELECT count(*) FROM subject_inverted WHERE subject_inverted MATCH '"cartography seamanship"';
.stats vmstep
SELECT count(*) FROM subject_inverted WHERE subject_inverted MATCH '"cartography seamanship"';
SQL
```

```
--- tree index, left-anchored pattern ---
QUERY PLAN
`--SEARCH book_subject USING COVERING INDEX subject_tree (subject>? AND subject<?)
500
VM-steps: 1518
--- same tree index, left-open pattern ---
QUERY PLAN
`--SCAN book_subject
1000
VM-steps: 801011
--- inverted index, same phrase ---
QUERY PLAN
`--SCAN subject_inverted VIRTUAL TABLE INDEX 0:M1
1000
VM-steps: 2013
```

The first measurement shows what the tree index can do: the left-anchored pattern was
turned into a range and answered in 1,518 steps. In the second measurement the same index
still stands, the same phrase is searched, and the only change is opening the left edge of
the pattern — and the index dropped out of use. The rule established in Query Performance
shows up again here: a left-open pattern leaves no entry point in a sorted structure.

The **inverted index (inverted index)** clears this wall by changing the structure. Instead
of the whole value, it takes as its key every word extracted from the value; against each
word stands the list of records containing it. The phrase search is answered by an
intersection of two lists plus a position comparison: 2,013 steps, one four-hundredth of the
scan path.

It has a cost. An inverted index grows in proportion to the word count of the source text,
and every text change updates more than one word entry. The rule for splitting text into
words is also language-dependent: stemming, affix handling, and case mapping are set up
separately for each language. This is the area where engines diverge the most.

## The List of Families and the Selection Criterion

Common index families are told apart by the question they answer. A tree-based index
answers every question that needs order. A hash-based index answers only equality. An
inverted index finds a word inside text. Two more families show up often alongside these: a
**bitmap index**, which keeps a bit pattern per value for columns with very few distinct
values, and a **spatial index**, which covers two-dimensional boxes with enclosing
rectangles. The second solves the same problem as the k-d tree in the Data Structures
course: searching data whose order is not one-dimensional.

The selection criterion fits in one sentence: an index type is chosen not by the column's
data type but by **the shape of the query**. The same date column suits a hash-based
structure if it is queried only by equality, and a tree-based structure if it is queried by
range. Which types are available is engine-specific; what stays constant is that the type
is decided on the query side.

## Summary

- An unindexed foreign key column turns every delete on the parent table into a scan of the
  child table; in the measurement a single-row delete fell from 600,013 steps to 15 steps.
- A tree-based index keeps its entries sorted, so it answers equality, range, prefix,
  minimum-maximum, and ready-order questions all at once.
- A hash-based index sorts the hash of the key; it answers equality at a cost close to the
  tree index, but a range query cannot use the index and falls to a scan.
- An inverted index takes as its key not the whole value but the words inside it; a
  left-open pattern search that took 801,011 steps was answered as a phrase search in 2,013
  steps.
- Index type is chosen by the shape of the query rather than the column's data type; on a
  column where order is never wanted, the cost of everything a tree index offers is paid
  without collecting the return.

## Next Step

Every index in this lesson carried a single column and covered every row of the table. Both
restrictions can be relaxed. When an index carries more than one column, the order those
columns are written in determines which query it serves — the same two columns indexed in
two different orders produce two different structures. When an index covers only part of
the table, it both shrinks and works more cheaply over the part it covers. The next lesson
measures these two decisions: the effect of column order on three separate queries, and the
size and plan-side gain of a conditional index.