CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 7 of 8 · 4 min read

Special indexes: hash, spatial and text

Hash maps in memory, ranges in two dimensions, and searching words.

Special indexes: hash, spatial and text

Think of three questions that a sorted list answers badly. "Which entry has exactly this id?" can be answered even faster with a direct address. "Which restaurants are inside this rectangle?" needs two sorted lists at once. "Which pages mention the word 'cheese'?" needs a list for every word.

Hash index. The book describes the simplest scheme. Keep a hash map in memory from each key to the byte offset of its latest value in an append-only data file. A lookup is one memory access and one disk read. Writes append to the file and update the map. It is fast for exact keys, but it cannot do range queries, such as "keys between 100 and 200", since a hash map has no order. The book also notes that all keys must fit in memory.

Spatial index. A latitude range and a longitude range are two separate sorted orders. The book explains that a standard tree index can give a range on one but not both. Two approaches: turn the two-dimensional position into one number with a space-filling curve and use a normal index, or use a special structure such as an R-tree. PostGIS implements location indexes as R-trees. The book adds that multi-dimensional indexes are not only for maps: a shop could index on colour (red, green, blue), and a weather database on date and temperature.

A common practical form is the geohash, which gives each rectangle of the map a short text code. Nearby places share the beginning of their codes, so a prefix search on an ordinary index finds places near each other. Level 11 uses this for the "nearby places" design.

Inverted index

An inverted index maps each word to the list of documents that contain it. The list is called a postings list.

Example: the word "cheese" maps to the documents 4, 17 and 90. A search for "cheese" reads that list and returns those three documents.

The book describes how a full-text engine such as Lucene works. The word dictionary is kept in sorted files like those of log-structured storage, merged in the background. Fuzzy search, such as finding words within one typing mistake of the query, uses extra structures built for the purpose. Level 6 describes search engines in detail.

A worked example for an inverted index. Three documents:

  • Doc 1: "red apple pie"
  • Doc 2: "green apple"
  • Doc 3: "apple pie recipe"

The index:

Word Documents
apple 1, 2, 3
green 2
pie 1, 3
recipe 3
red 1

The query "apple pie" reads the lists for "apple" (1, 2, 3) and "pie" (1, 3). Documents in both lists: 1 and 3. No document is read until the answer is known.

Index Best for Cannot do
Tree (B-tree, LSM) Equality, ranges, sorting Two-dimensional ranges, words
Hash Exact key lookup Ranges, sorting
Spatial (R-tree, geohash) "Near here", "inside this box" Sorting by anything else
Inverted Words and phrases Numeric ranges

Interview angle

Answer in your head first, then open it.

This query is slow. What do you do?

Run EXPLAIN, look for a scan, add or fix an index for the filter and the sort, check selectivity, and mention the write cost.

How would you index "latest 20 orders of a user"?

A composite index on (user_id, created_at), read backwards, no sort needed.

Why not index every column?

Each index adds a write on every insert, takes space and competes for memory.

How do you search by location or by word?

A spatial index such as a geohash or R-tree for places; an inverted index in a search engine for words.

Check yourself:

  • Why can a hash index not answer "keys between 100 and 200"?
  • What does a postings list hold?

Words you will meet

Word Plain meaning
Full scan Reading every row of a table
Index An extra structure that finds rows without a full scan
Query planner The database part that chooses how to run a query
EXPLAIN A command that shows the planner's choice
Selectivity How few rows a condition matches
Primary index Finds a row by its unique key
Secondary index Finds rows by another column
Heap file Rows stored in no particular order
Clustered index Rows stored inside the index, in key order
Covering index An index that carries extra columns to answer a query alone
Composite index An index on several columns
Leftmost prefix The rule that an index helps only queries fixing its first columns in order
Hash index A map from key to location, for exact lookups
Spatial index An index for positions in two or more dimensions
Geohash A short text code for a map rectangle
Inverted index A map from each word to the documents that contain it