Indexing fundamentals: dense, sparse, and multilevel indexes

What an index actually is — a small lookup table pointing at the real data — and how dense, sparse, and multilevel indexes trade index size against search speed.