2.19 索引

1. 索引是什么

• 索引是一种把查找关键字和对应的数据记录关联起来（可以看作key-value对）的数据结构
• 索引查找是通过索引来查找数据

2. 为什么需要索引

• 用来加速数据的查找

3. 稀疏索引 vs 稠密索引

• 稀疏索引.md

4. 正排索引 vs 倒排索引

• 倒排索引.md

5. 如何实现索引

5.1. 有序数组

• array.md

5.2. HashMap

• hashmap.md

5.3. BitMap

• BitMap.md

5.4. BloomFilter

• BloomFilter.md

5.5. SSTable

• LSM.md

5.6. 红黑树

• 红黑树.md

5.7. B+树

• B Tree.md

5.8. SkipList

• 跳表.md

6. 如何选择索引实现

• 数据是格式化数据还是非格式化数据
• 数据是静态数据还是动态数据
• 索引存储在内存还是硬盘
• 单值查找还是区间查找
• 单关键词查找还是多关键词组合查找

6.1. Hash vs SSTable

	Hash	SSTable
是否全部放入内存	是	否
查询效率	等值查询效率高	范围查询效率高
Key是否重复	否	是

7. 参考

• 算法07 五大查找之：索引查找 - 云+社区 - 腾讯云
• 索引查找算法_百度百科
• 8.4　线性索引查找 - 大话数据结构笔记
• 线性索引查找 - 概念_静水流深-CSDN博客_线性索引
• SSTable and LSM-trees. How to store Key-Value storage on the disk? :: /etc/notes — A personal blod about software engineering