索引

1 稀疏索引和稠密索引

参考 https://zhuanlan.zhihu.com/p/261130303

• 稠密索引： 在密集索引中，数据库中的每个搜索键值都有一个索引记录。这样可以加快搜索速度，但需要更多空间来存储索引记录本身。索引记录包含搜索键值和指向磁盘上实际记录的指针。
• 稀疏索引： 在稀疏索引中，不会为每个搜索关键字创建索引记录。此处的索引记录包含搜索键和指向磁盘上数据的实际指针。要搜索记录，我们首先按索引记录进行操作，然后到达数据的实际位置。如果我们要寻找的数据不是我们通过遵循索引直接到达的位置，那么系统将开始顺序搜索，直到找到所需的数据为止。

**稀疏索引占用空间少**，查找可能首**先需要直接索引，再顺序查找**；**稠密索引可以直接索引到数据**，但**占用的空间比较大**。

2 聚集索引和非聚集索引

参考 https://zhuanlan.zhihu.com/p/528069989

- 聚集索引和非聚集索引又分别称作聚簇索引和非聚簇索引。
- 以MySQL 默认引擎 InnoDB（B+树实现）来说，**聚簇索引**的叶子节点直接存储的value数据，而**非聚簇索引**（也叫二级索引）存储的是主键ID数据，然后再通过主键ID查询真正的行数据，我们把这个过程称之为**回表查询**。

• 聚集索引：数据行的 物理顺序 与列值（一般是主键的那一列）的 逻辑顺序 相同，一个表中只能拥有一个聚集索引。由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。
• 非聚集索引：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。其实按照定义，除了聚集索引以外的索引都是非聚集索引，只是人们想细分一下非聚集索引，分成普通索引，唯一索引，全文索引。如果非要把非聚集索引类比成现实生活中的东西，那么非聚集索引就像新华字典的偏旁字典，他结构顺序与实际存放顺序不一定一致。

3 正排索引和倒排索引

参考 https://zhuanlan.zhihu.com/p/338069587

简单的说，**文档->关键字是正排索引，关键字->文档是倒排索引**。

• 使用场景：倒排索引常用在 搜索场景 中，如搜索引擎、大规模数据库索引、文档检索、多媒体检索/信息检索领域等等。
• 倒排索引解决的问题：当从文档中查找关键字时，如果是正排索引，只能遍历所有的文档，对比是否含关键字，而倒排索引已经建立了关键字到文档的索引，这能大大加快索引速度。 倒排索引创建步骤：
• 将文档排序，编号文档 ID。
• 从文档中提取关键字，建立关键字到文档 ID、文档位置的索引。（数据量大时，关键字可能就会索引到多个文档了）