2.18 Sparse Index

1. What Is a Sparse Index

• First, it is an index
  • Index
• Second, it is sparse
  • The difference between a sparse index and a dense index is whether an index is created for every key

2. Why Sparse Index Is Needed

A sparse index occupies less space.

2.1. Sparse Index vs Dense Index

	Sparse Index	Dense Index
Does every key have an index?	No	Yes
Space usage	Small	Large
Lookup speed	Slower. Binary-search for the first range greater than the target, then scan	Faster. Binary-search for an exact lookup
Insert/update/delete speed	Faster. Update indexes for only some keys	Slower. Need to update the index for every key

3. How to Implement a Sparse Index

Binary Search

4. References

• Do You Understand Sparse and Dense Indexes? - Zhihu
• What are sparse and dense indexes?