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 |