Indexes in depth series: 1. Inside an index · 2. Index types beyond the B-tree
A B-tree is great at “equal to”, “within a range” and “sorted by”, but backends also need posts that contain a tag, JSON that has a key, text that matches keywords, ranges that overlap, the nearest point, or huge write loads. After this post you can pick hash, GIN, GiST, bitmap or an LSM tree by query shape and know what each costs on writes (measured on PostgreSQL 16 and MySQL 8.4 in Docker on a laptop: remember the ratios, not the absolute values). Read Inside an index and the PostgreSQL index lab first; the lab already measured hash and BRIN indexes.
1. Hash indexes: the missing pieces
Key idea: a hash index only answers “equal to this value”. A hash function deliberately destroys ordering, so there are no ranges, sorting, UNIQUE or multiple columns.
- Two neighbouring keys land in arbitrary buckets, so there is no way to “step to the next key”. The earlier lab: on PostgreSQL a hash index only edges out a B-tree for
=. - Two different keys can share a bucket (a collision), so the index only returns candidates and the database has to compare the real values again.
- MySQL: InnoDB has the adaptive hash index (AHI), an in-memory hash table InnoDB builds by itself for B-tree pages that keep getting equality lookups. Since 8.4 it is off by default.
Hash on the MySQL side: the MEMORY engine and the adaptive hash index
The MEMORY engine uses hash indexes by default (and loses its data on restart). The slide’s claim that “an InnoDB clustered index cannot be a hash” is right about the on-disk structure, but AHI is still a hash layer sitting on top of it.
2. GIN: an inverted index for “contains an element”
Key idea: GIN splits every value into elements and stores, for each element, the list of rows that contain it. It answers “contains X” for arrays, jsonb and full-text, but only for operators in its operator class.
2.1. How it is built
Key idea: GIN is a B-tree over the elements, and each leaf points to a posting list (the IDs of the rows that contain that element).
A B-tree on a tags text[] column treats the whole array as one value. GIN (Generalized Inverted Index) flips the relationship, like the index at the back of a book, and is also the heart of Elasticsearch.
flowchart LR
R1["id 1: {kafka, java}"] --> K2["kafka → [1, 3]"]
R1 --> K1["java → [1]"]
R2["id 2: {redis}"] --> K3["redis → [2, 3]"]
R3["id 3: {kafka, redis}"] --> K2
R3 --> K3
- Posting lists are compressed; a very long one becomes a posting tree.
tags @> ARRAY['kafka','redis']looks up two elements and intersects the two lists.- GIN returns a set of rows in no particular order, which is why it almost always comes with a Bitmap Heap Scan.
2.2. Tag arrays
Key idea: GIN on an array is small and fast for @> and &&, but = ANY can’t use it.
A 300,000-post table, each post with 1–4 tags out of 50, skewed (tag0 appears in 92,065 posts, tag49 in 7,386). The GIN index on tags is only 1.6 MB for a 64 MB table.
| Query | No index | With GIN |
|---|---|---|
tags @> ARRAY['tag49'] |
Parallel Seq Scan 20.8 ms | 3.6 ms |
tags @> ARRAY['tag49','tag48'] (156 rows) |
Seq Scan | 0.43 ms |
tags && ARRAY['tag49','tag48'] (either one) |
Seq Scan | 5.0 ms |
'tag49' = ANY(tags) |
Seq Scan 18 ms | still Seq Scan, 18 ms |
2.3. jsonb: two operator classes
Key idea: GIN on jsonb serves containment (@>) for every key. Filtering with attrs->>'k' = 'v' uses no GIN index at all; it needs an expression index.
attrs @> '{"author_id": 42}'(GIN): 0.07 ms.attrs->>'author_id' = '42': 33 ms Seq Scan.- The fix is a B-tree expression index on exactly
((attrs->>'author_id')::int): 0.08 ms.
jsonb_ops vs jsonb_path_ops, and the measurement details
For attrs jsonb shaped like {"lang": "vi", "author_id": 42, "featured": false}:
| Operator class | What gets indexed | Operators | Size |
|---|---|---|---|
jsonb_ops (default) |
Every key and every value separately | @>, ?, `? |
, ?&, @?, @@` |
jsonb_path_ops |
A hash of the whole path to each value | @>, @?, @@ |
2.7 MB |
attrs ? 'promo'(does the key exist) can only usejsonb_ops.attrs->>'author_id' = '42'uses no GIN index, because->>plus text=is not in the operator class.- The full expression index:
CREATE INDEX ON post (((attrs->>'author_id')::int)), then writeWHERE (attrs->>'author_id')::int = 42.
2.4. Full-text search
Key idea: full-text search splits text into lexemes (normalised words) in a tsvector and indexes it with GIN. ILIKE '%kafka%production%' takes 180 ms, full-text 22 ms.
ALTER TABLE post ADD COLUMN tsv tsvector
GENERATED ALWAYS AS (to_tsvector('simple', title)) STORED;
CREATE INDEX post_tsv_gin ON post USING gin (tsv);
SELECT id, title, ts_rank(tsv, q) AS rank
FROM post, websearch_to_tsquery('simple', 'kafka production') q
WHERE tsv @@ q
ORDER BY rank DESC LIMIT 10;
- 5,981 posts match; the Bitmap Index Scan alone is 1.9 ms, the rest of the 22 ms is ranking and sorting.
websearch_to_tsqueryunderstands Google-style syntax ("phrase",-exclude,or) and is safer thanto_tsqueryfor whatever users type.- Vietnamese: there is no Vietnamese configuration, so use
'simple'plusunaccent. If you need word segmentation, synonyms or suggestions, move search to Elasticsearch/OpenSearch.
Vietnamese with unaccent, MySQL FULLTEXT and the unique-token trap
PostgreSQL and Vietnamese. 'simple' does no stemming; unaccent gives accent-insensitive search ('Tối ưu Kafka' becomes 'toi' 'uu' 'kafka'). unaccent() isn’t IMMUTABLE, so putting it straight into a generated column fails with generation expression is not immutable; wrap it in an IMMUTABLE function that calls unaccent with an explicit dictionary.
MySQL has FULLTEXT indexes on InnoDB (MATCH ... AGAINST). The lab on 100,000 Vietnamese titles:
+kafka +productionreturns 2,078 rows, exactly whatLIKEreturns.+toiwithout accents still matches “tối” thanks to theutf8mb4_0900_ai_cicollation.+ưureturns 0 rows: the default parser drops tokens shorter thaninnodb_ft_min_token_size = 3characters, and many Vietnamese syllables are two characters long.- The
ngramparser (2-character chunks, designed for Chinese, Japanese and Korean) does find “ưu”, at the cost of a bigger index and more false matches. - The first load hit a client trap: the
mysqlclient defaulted tolatin1, UTF-8 strings were double-encoded, andMATCHreturned 0 rows for every accented word. Always set--default-character-set=utf8mb4orSET NAMES utf8mb4.
2.5. The write cost: the pending list
Key idea: a row with 7 elements means GIN must insert into 7 posting lists. fastupdate (on by default) collects new rows in a pending list so writes are cheap, at the price of p99 spikes.
The pending list is unsorted and gets merged into the main structure when it grows past gin_pending_list_limit (4 MB by default), when autovacuum runs, or when you call gin_clean_pending_list(). Inserting 300,000 rows into a table with two GIN indexes (tags, attrs):
| Setting | Time |
|---|---|
| No index | 0.29 s |
fastupdate = on |
1.07 s |
fastupdate = off |
4.5 s |
3. GiST and SP-GiST: ranges, coordinates and “nearest”
Key idea: GiST is a tree of bounding boxes; it answers “overlaps” and “nearest”. Its most important backend use is the exclusion constraint against double booking.
3.1. The R-tree idea
Key idea: every inner node stores a bounding box containing everything below it; to find “what overlaps this area” you only descend into branches whose box intersects that area.
- GiST (Generalized Search Tree) builds balanced trees for any type that can define a “bounding box” and an “overlaps” test. For
tstzrange, the “box” is the smallest time interval covering the sub-intervals. - Unlike a B-tree, boxes may overlap: one query can follow several branches, and index results need a recheck.
- SP-GiST (space-partitioned) splits space into non-overlapping regions (quadtree, k-d tree) and is usually smaller for evenly spread points: 8.9 MB versus 13 MB for GiST on 200,000 points.
3.2. Exclusion constraints: no double-booked rooms
Key idea: an exclusion constraint generalises UNIQUE to “no two rows for which all the listed operators are true”. The database enforces it, even when two transactions run in parallel.
UNIQUE can’t express “overlapping times”, and checking in code (SELECT, then INSERT) races between two transactions (see transactions and isolation levels).
CREATE EXTENSION IF NOT EXISTS btree_gist; -- allows = on bigint inside GiST
CREATE TABLE room_booking (
id bigserial PRIMARY KEY,
room_id bigint NOT NULL,
during tstzrange NOT NULL,
EXCLUDE USING gist (room_id WITH =, during WITH &&)
);
INSERT INTO room_booking (room_id, during) VALUES
(1, tstzrange('2026-12-01 14:00+07', '2026-12-03 12:00+07', '[)')),
(1, tstzrange('2026-12-03 12:00+07', '2026-12-05 12:00+07', '[)')), -- back to back: OK
(2, tstzrange('2026-12-01 14:00+07', '2026-12-03 12:00+07', '[)')); -- another room: OK
INSERT INTO room_booking (room_id, during)
VALUES (1, tstzrange('2026-12-02 14:00+07', '2026-12-04 12:00+07', '[)'));
-- ERROR: conflicting key value violates exclusion constraint (SQLSTATE 23P01)
[)bounds (start included, end excluded): a guest checking out at 12:00 and another checking in at 12:00 don’t count as overlapping.- The constraint’s GiST index is also used by the planner for ordinary queries such as “which rooms are busy on 1 March”.
The two-session concurrency test and the bigint trap with btree_gist
Concurrency test. Session A inserts room 7 for the 10th–12th and holds its transaction for 2 seconds; session B inserts room 7 for the 11th–13th and blocks for about 1.5 seconds, then gets 23P01 once A commits. The constraint holds under parallel transactions with no application-level locking.
3.3. Nearest-neighbour search (KNN)
Key idea: GiST and SP-GiST order by distance inside the index with <->, walking “closest box first” and stopping once they have enough results.
CREATE INDEX homestay_loc_gist ON homestay USING gist (loc); -- loc is a point
SELECT id, name FROM homestay ORDER BY loc <-> point(105.85, 21.03) LIMIT 5;
- On 200,000 points: SP-GiST 0.03 ms, GiST 0.08 ms; without an index a Parallel Seq Scan plus top-N sort takes 30 ms.
pointis a flat coordinate; real distances on latitude/longitude need PostGIS with thegeographytype, which still uses GiST underneath.- MySQL has
SPATIAL INDEX(an R-tree) for geometry types, but no index-driven KNN like<->.
4. Bitmap indexes and bitmap scans are different things
Key idea: a stored bitmap index (Oracle, warehouses) is a completely different thing from PostgreSQL’s run-time bitmap scan. The slides’ “count the PROCESSING orders” problem is solved on PostgreSQL with a partial index.
- A stored bitmap index (Oracle, columnar warehouses): one bit string per column value, where bit i is 1 if row i has that value, and it compresses extremely well.
status = 'PROCESSING' AND region = 'HN'is an AND of two bit strings; counting is counting 1-bits. - A bitmap scan at run time (PostgreSQL): there is no bitmap index on disk. The executor uses a B-tree/GIN/GiST index to build a bitmap in memory (
Bitmap Index Scan), can AND/OR several of them (BitmapAnd,BitmapOr), then reads the heap in physical order. - MySQL has neither; the closest thing is index merge (
Using union(idx_author, idx_lang)forauthor_id = 42 OR lang = 'ja'in the lab).
Why columnar warehouses (ClickHouse) suit reports that scan many rows but few columns is covered in choosing a database.
On a 1-million-row orders table, a partial index on (id) WHERE status = 'PROCESSING' takes only 128 KB and still gives an Index Only Scan under 1 ms; for a common value (90% of the table) no index helps.
Counting orders on the 1-million-row orders table
5,105 orders in PROCESSING, counted with count(*):
| Approach | Size | Time |
|---|---|---|
| No index | – | Parallel Seq Scan 43 ms |
B-tree (status) |
6.9 MB | Index Only Scan 0.37 ms |
Partial index (id) WHERE status = 'PROCESSING' |
128 KB | Index Only Scan 0.69 ms |
Orders moving to COMPLETED leave the partial index on their own. WHERE status = 'COMPLETED' (90% of the table) gets no help from any index: still a 90 ms Seq Scan, exactly the slide’s point about not indexing low-cardinality columns for common values.
5. LSM trees: when writes dominate
Key idea: a B-tree updates pages in place, so heavy write loads are limited by random writes. An LSM tree (Log-Structured Merge tree) never updates in place: it appends, then merges files in the background.
flowchart TB
W["Write (put/delete)"] --> WAL["WAL on disk"]
W --> M["Memtable in RAM"]
M -->|"full: flush"| L0["L0: immutable SSTables"]
L0 -->|"compaction"| L1["L1"]
L1 -->|"compaction"| L2["L2: about 10x L1"]
R["Read a key"] --> M
R --> BF["Bloom filter per SSTable"]
BF --> L0
BF --> L1
BF --> L2
- Writes go into the memtable (a sorted tree in RAM) and are appended to the WAL. A full memtable is flushed as an SSTable, an immutable file sorted by key. A delete writes a tombstone (a “deleted” marker).
- Reads check the memtable, then SSTables from newest to oldest; each file’s bloom filter answers “this key is definitely not here” so the file can be skipped.
- Compaction is a background process that merges SSTables and drops old versions and tombstones. Size-tiered merges files of similar size (cheap writes, more space, reads touch more files; Cassandra’s long-time default). Leveled keeps each level about 10 times larger than the previous one, with no overlapping keys inside a level (better reads and space, more rewriting; RocksDB’s default).
This section has no lab; the amplification figures are typical ranges from the RocksDB documentation and should be re-measured with your own workload.
6. Picking an index type by query shape
Key idea: look at the operator in WHERE/ORDER BY, then pick the index type that serves that operator.
The course slides classify indexes by data structure (B+tree, hash, inverted, LSM tree, R-tree, bitmap); the table below regroups them by the question you need answered.
| Query shape | Example | PostgreSQL | MySQL |
|---|---|---|---|
| Equality, range, sort | created_at >= ? ORDER BY created_at |
B-tree | B-tree |
| Element in an array | tags @> '{kafka}' |
GIN | N–M table, or a multi-valued index on JSON (8.0.17+) |
| Containment in JSON | attrs @> '{"featured": true}' |
GIN jsonb_path_ops |
Multi-valued index / generated column |
| Keywords in text | “kafka production” | GIN on tsvector |
FULLTEXT |
| Arbitrary substring | LIKE '%abc%' |
GIN pg_trgm |
A search engine |
| Overlapping ranges, no double booking | during && ? |
GiST + exclusion constraint | Locking + checks |
| Nearest | ORDER BY loc <-> ? |
GiST / SP-GiST / PostGIS | SPATIAL filtering by area |
| A rare value in a low-cardinality column | status = 'PROCESSING' |
Partial index | Regular index |
A real case of the LIKE '%abc%' row is the product search in the pagination and dynamic filters post: lower(name) like '%tuf%' scans the whole table until a GIN pg_trgm index exists.
7. Case study: searching posts by tag, keywords and date
Key idea: three single indexes (GIN on tags, GIN on tsv, B-tree on created_at) are fast enough at 300,000 rows and serve several screens. Move to Elasticsearch when Vietnamese ranking matters or search starts eating most of the database’s CPU.
The problem. A blog admin page: pick a tag, type keywords, choose “last 30 days”, show the 20 newest posts. The post table has 300,000 rows and grows by about 2,000 posts a day. There is also a “latest posts for a tag” page without keywords.
The SQL, three options, option 1 measured and the ORDER BY … LIMIT trap
SELECT id, title, created_at FROM post
WHERE tags @> ARRAY['tag12']
AND tsv @@ websearch_to_tsquery('simple', 'kafka production')
AND created_at >= now() - interval '30 days'
ORDER BY created_at DESC
LIMIT 20;
| Option | Gain | Cost |
|---|---|---|
| (1) Three separate indexes, the planner chooses | Small, each index serves several screens | Depends on the planner’s choice |
(2) One multi-column GIN with btree_gin |
A single index takes all three conditions | GIN returns rows unordered, so a sort remains; writes get more expensive |
| (3) Elasticsearch synced through CDC | Best ranking and Vietnamese handling | One more system, data lags by a few seconds |
Measuring option 1. The planner doesn’t use BitmapAnd. It starts from the condition it believes is most selective (tsv, 5,981 rows), filters tags and created_at on each heap row, ends with 34 rows and sorts them: 4.9 ms with warm cache, 176 ms with cold cache (4,444 pages read from disk). For the tag-only page the plan changes completely: Index Scan Backward on the created_at B-tree, filtering the tag row by row and stopping after 20 posts: 0.13 ms for tag49, 0.02 ms for tag0.
Decision. Option 1 (three separate indexes, 4.9 ms with warm cache) rather than (2) one multi-column GIN with btree_gin or (3) Elasticsearch via CDC. The ORDER BY ... LIMIT plan can suddenly slow down for rare tags, so watch max latency.
Exercises
Exercise 1: Stop double bookings in the database
Task (paraphrased). Two guests clicking “book” on the same room at the same moment sometimes both succeed. Block it in the database and return HTTP 409 to whoever comes second.
Solution to Exercise 1: an exclusion constraint and catching 23P01 in Spring Boot
The exclusion constraint from section 3.2, with [) bounds. In Spring Boot, error 23P01 comes out of Hibernate as a DataIntegrityViolationException; catch it and turn it into a 409:
@Transactional
public Booking book(long roomId, OffsetDateTime checkIn, OffsetDateTime checkOut) {
try {
return repo.saveAndFlush(new Booking(roomId, checkIn, checkOut)); // flush so the error surfaces here
} catch (DataIntegrityViolationException e) {
if (e.getMostSpecificCause() instanceof SQLException sql
&& "23P01".equals(sql.getSQLState())) { // exclusion_violation
throw new RoomAlreadyBookedException(roomId); // @ResponseStatus(CONFLICT)
}
throw e;
}
}
If you’d rather not map tstzrange in JPA, store check_in and check_out and put the constraint on an expression: EXCLUDE USING gist (room_id WITH =, tstzrange(check_in, check_out, '[)') WITH &&). The SQL part ran on PG16, including the two-session concurrency test; the Java snippet was not run.
Exercise 2: Why don’t these three queries use an index?
Task. There is a GIN index on tags, a GIN jsonb_path_ops index on attrs, and a GiST exclusion constraint (room_id WITH =, during WITH &&) with room_id bigint. Explain and fix:
SELECT id FROM post WHERE 'tag49' = ANY(tags);
SELECT id FROM post WHERE attrs->>'author_id' = '42';
SELECT 1 FROM room_booking WHERE room_id = 500 AND during && tstzrange('2027-03-01','2027-03-02');
Solution to Exercise 2 (run)
= ANYisn’t in the GIN array operator class; writetags @> ARRAY['tag49'](18 ms down to 3.6 ms).->>plus text=isn’t a GIN operator; writeattrs @> '{"author_id": 42}'(0.07 ms), or create an expression index and use exactly that expression (0.08 ms).500is anint4andbtree_gisthas noint8 = int4; write500::bigint(6.4 ms down to 0.65 ms).
The lesson: indexes are matched by operator and type, not by column name; read Index Cond and Filter in the plan.
Remember
- Explain why hash can’t serve ranges or sorting, and why GIN returns rows in no particular order.
- Know why
= ANY,->> =and anint4literal on abigintcolumn make an index get skipped, and fix each one. - Write an exclusion constraint against double bookings and say why it holds under concurrency.
- Tell a stored bitmap index from a bitmap scan, and know to use a partial index for a rare value.
- Compare B-trees and LSM trees through the three amplifications, and recognise the signs of compaction falling behind.
Interview questions
Junior
Why can’t a hash index serve range queries or ORDER BY?
Because a hash function deliberately destroys ordering: the index doesn’t know which key sits next to which.
Neighbouring keys land in arbitrary buckets, so you can’t move from one key to the next. A hash index only answers “equal to this value”, and because of collisions the database still compares the real values.
What is an inverted index?
A structure that stores, for each element (a word, a tag, a JSON key), the list of rows that contain it, like the index at the back of a book.
“Contains X” is a lookup of X; “contains X and Y” is an intersection of two lists. PostgreSQL’s GIN and Elasticsearch both follow this idea.
Mid
How do jsonb_ops and jsonb_path_ops differ?
jsonb_ops indexes each key and value and also supports ?; jsonb_path_ops indexes a hash of the whole path, smaller and faster for @> but without ?.
The key-existence operators of jsonb_ops are ?, ?|, ?&. Neither serves attrs->>'k' = 'v'; that needs an expression index.
How does full-text search work in PostgreSQL?
Text becomes a tsvector, the search string a tsquery, @@ tests for a match, and a GIN index on the tsvector makes it fast.
A tsvector holds normalised lexemes with positions under a language configuration; ts_rank ranks results. The tsvector usually lives in a generated column. For Vietnamese, use the simple configuration plus unaccent.
What does an exclusion constraint solve that UNIQUE can’t?
UNIQUE only forbids two equal rows; an exclusion constraint forbids two rows for which all listed operators are true, such as same room and overlapping times.
room_id WITH =, during WITH && forbids two bookings of the same room with overlapping times. It is enforced with a GiST index and holds under concurrent transactions: the later one waits, then gets 23P01.
How does GIN fastupdate affect latency?
On, writes are much cheaper but you get p99 spikes; off, write latency is steady but higher.
With it on, new rows go into an unsorted pending list; reads also scan that list, and whichever write pushes it past gin_pending_list_limit has to merge all of it.
Senior
How is a bitmap index different from PostgreSQL’s bitmap heap scan?
A bitmap index is stored on disk (Oracle, warehouses); a bitmap heap scan uses bitmaps PostgreSQL builds in memory at run time from ordinary indexes.
A bitmap index keeps one bit string per value; it’s excellent for low-cardinality columns but locks whole bitmap segments, so it’s bad for concurrent OLTP writes. PostgreSQL builds bitmaps from B-tree/GIN/GiST indexes, can AND/OR them, then reads the heap in physical order. “Count the PROCESSING orders” on PostgreSQL is solved with a partial index.
When would you choose an LSM-tree storage engine over a B-tree?
When writes are heavy and dominant (events, logs, time series, counters), access is by key, and compression matters.
You accept read amplification (bloom filters only help point lookups), write amplification from compaction, temporary space overhead, and the risk of compaction falling behind. Read-heavy OLTP, range scans and ad-hoc queries still suit a B-tree better.
How do size-tiered and leveled compaction differ?
Size-tiered has cheap writes but worse reads and space; leveled has better reads and space but rewrites more.
Size-tiered merges SSTables of similar size: a key can live in many files and merges need lots of free space. Leveled keeps each level about 10 times the previous one with non-overlapping keys inside a level, so each byte is rewritten more times.
How would you index a search screen filtering by tag, keywords and date, newest first?
Start with single indexes that serve many screens (GIN on tags, GIN on the tsvector, B-tree on created_at), measure plans on real data and watch max latency.
The planner usually starts from the most selective condition and filters the rest, or walks the time B-tree backwards when there’s a LIMIT. An ORDER BY ... LIMIT plan degrades with rare filters, so look at the max, not just the average. When ranking and Vietnamese handling matter, move search to Elasticsearch synced via CDC.
Useful phrases for interviews
- “GIN is an inverted index, so it answers containment queries, not range or sort queries.”
- “The index wasn’t used because that operator isn’t in the index’s operator class; I rewrote the predicate to use
@>.” - “For one hot JSON key with range filters I’d rather add an expression index than rely on a GIN index over the whole document.”
- “An exclusion constraint guarantees no overlapping bookings at the database level, even with concurrent transactions.”
- “PostgreSQL doesn’t have stored bitmap indexes; it builds bitmaps at query time, so for a rare status I’d use a partial index.”
- “With
fastupdateon, writes are cheaper, but one unlucky insert pays for flushing the pending list, so I’d watch p99.” - “LSM trees trade read and space amplification for sequential writes; I’d pick one for write-dominated, key-based workloads.”
- “If compaction falls behind, read latency creeps up and the disk fills, so compaction lag is the first thing I’d monitor.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.