Dense vs Sparse Indices
A dense index has a record for every search key value. Each index record contains the key value and a pointer to the actual record. If there are duplicates (given cluster by search key), the index points to the first one. Good for determining whether a record with said key exists.
A sparse index has an index record for every block. Records must be clustered according to search key. Main benefit: we are guaranteed to retrieve the correct block unless record is on overflow block. Index size is small.
Lazy deletion: mark as deleted, but don't actually delete. Overwritten on write / search.
https://www.cs.duke.edu/courses/fall02/cps196.3/lectures/20-index.pdf
http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter11/node5.html
