All types of index and when to use

B-Tree

• How it works: balanced tree, sorted keys, leaf nodes linked together. Lookup = walk down the tree, O(log n).
• Where to use: default choice for almost everything — exact-match *and* range queries (WHERE price BETWEEN 10 AND 50). This is what Postgres/MySQL use natively for primary keys and most secondary indexes.

Hash Index

• How it works: hashes the key, points directly to the row. O(1) lookup.
• Where to use: only exact-match lookups — hashing destroys ordering, so no range queries. DynamoDB partition-key-only access is effectively this.

Composite (multi-column) Index

• How it works: index on (col1, col2) — order matters. Efficiently supports queries filtering on col1 alone, or col1 + col2 together, but not col2 alone.
• Where to use: whenever your query filters on multiple columns together — design the column order to match your actual query pattern (leading column = what you always filter on).

Inverted Index

• How it works: term → list of document IDs containing it (e.g., “pizza” → \[doc4, doc88, …\]). Flips “scan every doc for this word” into “look up this word’s doc list directly.”
• Where to use: full-text search — Elasticsearch/Lucene’s core mechanism for name/description search (Yelp business names, Ticketmaster event search).

Geohash

• How it works: encodes lat/long into a string; nearby points usually share a prefix. Range/prefix query on the string ≈ “nearby.”
• Where to use: simple proximity search, especially when points move frequently (Tinder user locations) — updating is just a cheap string recompute, no tree rebalancing. Weakness: edge effects at cell boundaries, so you query neighbor cells too (3×3 grid).

Quadtree

• How it works: recursively splits space into 4 quadrants, subdividing only where density is high.
• Where to use: proximity search over unevenly distributed, mostly static points (dense cities vs. sparse rural areas) — adapts better than geohash’s fixed grid, but costly to rebalance if points move often.

R-Tree

• How it works: groups nearby shapes into bounding boxes, recursively (like a B-tree but for rectangles).
• Where to use: static geo data, especially regions/polygons (delivery zones, geofences), not just points. This is what PostGIS uses under the hood via GiST. Same rebalancing weakness as quadtree if data moves a lot.

Bloom Filter

• How it works: bit array + k hash functions; “maybe present” or “definitely absent” — no false negatives, tunable false positives.
• Where to use: cheap large-scale membership checks where an occasional false positive is acceptable but a false negative isn’t (Tinder’s “have I ever swiped on this person” at massive scale, without storing the full ID list).

One-line decision cheat sheet:

**Query type**	**Index**
**Exact match or range, general purpose**	**B-Tree**
**Exact match only**	**Hash**
**Multiple filter columns together**	**Composite**
**Text/keyword search**	**Inverted**
**“Near me,” points move often**	**Geohash**
**“Near me,” points mostly static, uneven density**	**Quadtree**
**“Near me,” regions/polygons**	**R-Tree**
**“Have I seen this before,” huge scale, cheap**	**Bloom Filter**