2.19 Index

1. What Is an Index

• An index is a data structure that associates search keys with corresponding data records (it can be regarded as key-value pairs)
• Index lookup finds data through the index

2. Why Index Is Needed

• Used to speed up data lookup

3. Sparse Index vs Dense Index

• Sparse Index

4. Forward Index vs Inverted Index

• Inverted Index

5. How to Implement an Index

5.1. Sorted Array

• array.md

5.2. HashMap

• hashmap.md

5.3. BitMap

• BitMap.md

5.4. BloomFilter

• BloomFilter.md

5.5. SSTable

• LSM.md

5.6. Red-Black Tree

• Red-Black Tree

5.7. B+Tree

• B Tree.md

5.8. SkipList

• Skip List

6. How to Choose an Index Implementation

• Is the data structured or unstructured?
• Is the data static or dynamic?
• Is the index stored in memory or on disk?
• Exact-value lookup or range lookup?
• Single-keyword lookup or multi-keyword combined lookup?

6.1. Hash vs SSTable

	Hash	SSTable
Fully loaded into memory?	Yes	No
Query efficiency	High for equality queries	High for range queries
Can keys repeat?	No	Yes

7. References

• Algorithm 07: Index Search Among Five Major Search Methods - Tencent Cloud
• Index Search Algorithm - Baidu Baike
• 8.4 Linear Index Search - Data Structures Notes
• Linear Index Search: Concepts - CSDN
• SSTable and LSM-trees. How to store Key-Value storage on the disk? :: /etc/notes — A personal blod about software engineering