4.5 Secondary indexes and where values live

Primary key uniquely identifies one row / document / vertex; other records refer to it by that key, and the index resolves such references.

Secondary indexes (CREATE INDEX) let you search by other columns. The key difference: indexed values are not necessarily unique — many rows may share one index entry. Two solutions:

1. Make each value in the index a list of matching row identifiers — like a postings list in a full-text index
2. Make each entry unique by appending a row identifier to it

Both B-trees and log-structured storage can implement an index.

5.1 Three ways to store the value

Clustered index	Heap file	Covering index
The index leaf holds the actual row: [k1 | full row]	The index leaf holds a reference — a primary key or disk location: [k1 | →heap:0x4A2]	The index holds some columns, with the row still in the heap or clustered index: [k1 | col_a, col_b | →row]
MySQL InnoDB always clusters the primary key; SQL Server allows one per table. InnoDB secondary indexes store the primary key as the reference.	The heap has no order — append-only, or reusing deleted rows. PostgreSQL uses this approach.	The query is answered from the index alone, so the index “covers” it. ✔ Faster for those queries. ✗ Duplicated data means more disk and slower writes.

The heap-file update gotcha: updating a value without changing the key can overwrite in place, provided the new value is not larger. If it is larger, the record probably must move to a new heap location with enough space — and then either all indexes must be updated to point at the new location, or a forwarding pointer is left behind in the old location.

(This is exactly why PostgreSQL's HOT updates and MySQL's clustered-PK design exist, and why "update a TEXT column from 20 bytes to 2000 bytes" can be surprisingly expensive.)

---