Indexing Mind Map
Algorithm & Systems VisualizationsEvery indexing visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.
1. How the map is organized
Ask what kind of question the index must answer:
- Exact key, or a range in order? Exact only: hash tables (and caches built on them). In order: ordered search in memory, disk trees on disk.
- Is the key a string you search by prefix? Then a trie. Is it a point on a map? A spatial index.
- Is the question a sum over a range of positions? That is range queries.
- Is an approximate answer in tiny memory enough? That is sketches and sampling.
2. The branches side by side
| Branch | Lookup time | Keeps order? | Answer |
|---|---|---|---|
| Ordered search | O(log n) | yes | exact |
| Hash tables | O(1) average | no | exact |
| Caches | O(1) | by recent use | hit or miss |
| Tries | O(key length) | yes | exact, prefixes |
| Disk trees | O(logB n) page reads | yes | exact, ranges |
| Spatial indexes | about O(log n) per query | by area | exact, near points |
| Range queries | O(log n) | by position | exact sums |
| Sketches and sampling | O(1) or O(k) | no | approximate |
3. Five facts to remember
- A plain BST can become a list (O(n)); balanced trees keep the height O(log n).
- Hash tables give O(1) average lookups but cannot answer range or sorted-order queries.
- A B+ tree keeps all data in linked leaves, so range scans just walk the leaves.
- A Bloom filter can say "maybe present" wrongly, but never "absent" wrongly.
- A Fenwick tree and a segment tree both do point update and range sum in O(log n).
See all indexing pages in the index, or the other mind maps.