[TOC] # 索引 ## 定义： > 索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干索引项构成，每个索引项至少包含关键字和其对应记录在存储器中的位置等信息。 > 由此可见，索引技术是组织大型数据库和磁盘文件的一种重要技术。 ## 索引技术的划分 > 1. 线性索引 > 2. 树形索引 > 3. 多级索引 ## 线性索引 ### 定义： > 线性索引就是将索引项集合组织为线性结构，也称索引表。  ### 线性索引分类 > 1. 稠密索引 > 2. 分块索引 > 3. 倒排索引 ### 稠密索引 #### 定义： > 稠密索引是指在线性表中，将数据集中的每个记录对应一个索引项。就像我们上面示例图中的那样。以主键为例，可以将其抽象化如下： >  #### 应用： > 对于稠密索引这个索引表来说，索引项一定按照关键码有序排列，这样可以应用二分查找，以免索引查找本身影响性能。可见，稠密索引性能可以做到和二分查找相当（找到对应关键码就可以通过指针直接指向对应记录），但是索引项长度和数据集一样长，空间复杂度高，如果数据太多需要存放到磁盘上，反复读取磁盘对性能影响很大。 ### 分块索引 #### 定义： > 我们对数据集进行分块，并使其**分块有序**，然后再给每个分块建立一个索引项（索引值是分块中最大关键码），至于分块内部，则不管其有序性，从而减少索引项的个数。在查找的时候在索引项中通过二分查找找到指定索引项，然后根据该索引项中的关键码去相应分块遍历查找指定元素，这是一种折中方案，既兼顾了空间复杂度，又兼顾了时间复杂度。 >  #### 分块有序 > 1. 块内无序：每一块内的记录不要求有序。当然，有序更理想，只不过要花费大量的时间和空间的代价。 > 2. 块间有序：要求后一块的所有关键字都大于前一块的所有关键字。只有块间有序，才能给查找带来效率。 #### 分块索引的索引项的组成 > 1. 最大关键码：它存储每一块中的最大关键字。这样做的好处是在它之后的下一块中的最小的关键字也能比这一块最大的关键字要大。 > 2. 块长：存储块中的记录的个数，以便于循环时使用。 > 3. 块首指针：用于指向块首数据元素的指针，便于开始对这一块的记录开始遍历。 #### 应用 > 1. 在分块索引表中查找关键字所在的块。由于块间有序，所以可以通过二分查找快速定位（通过不小于给定值的第一个元素，不大于给定值的最后一个元素确定区间，以前面给出的示例图为例，58位与57和96之间，则会去第三块中查找）。 > 2. 根据块首指针找到对应的块，并在块中顺序查找指定的值（即关键码，块中无序所以只能顺序查找）。 #### 性能 > 分块索引的时间复杂度是：O(log(m)+n)，其中 m 是分块数，n 是块内元素个数，在索引表长度和块内元素相等时，时间复杂度最优。性能要由于顺序查找，但是比二分查找要差。 总体来说，分块索引在兼顾存储空间和查找性能的情况下，被普遍用于数据库查找等技术中。 ### 正向索引 #### 定义 > 正向索引指的是通过文档 ID 找到对应的文档，如果通过文档ID查找对应文档，再在文档中匹配关键词，意味着要扫描所有文档，最后还要排序，对于互联网上的海量资源来说，显然是不可取的。 ### 倒排索引 > 通过分析每个文档，提取其中的关键字，并建立关键词与文档 ID 的映射关系，每个关键词都对应着多个文档 ID。由于不是通过文档来确定属性（这里的属性是关键词），而是通过属性来确定文档，故而将其称作倒排索引。