索引查找 gaunthan Posted on Jan 17 2017 ? Searching ? ## 索引的定义 索引是为了加快查找速度而设计的一种数据结构，如在关系数据库中可以创建关系上的索引，以加快查询速度。一般来说，建立与删除索引由数据库管理员(DBA)或表的属主(owner)，即建立表的人负责完成。DBMS会在存储数据时自动选择合适的索引作为存取路径，用户不必也不能显式地选择索引。 **索引**(index)，就是把一个关键字与它所对应的记录相关联的过程。**一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息**。索引技术是组织大型数据库以及磁盘文件的一种重要技术。 ## 索引的种类 索引按照结构可以分为：线性索引、树形索引以及多级索引。 ## 线性索引 所谓**线性索引**就是将索引项集合组织为线性结构，也称为索引表。线性索引主要有3种：稠密索引、分块索引和倒排索引。 ### 稠密索引 **稠密索引**是指在线性索引中，将数据集中的每个记录对应一个索引项，同时索引项都是按照关键码序排列的。 稠密索引的优点是显而易见的，由于关键码有序，查找关键字时可以使用折半、插值、斐波那契等有序查找算法，使得效率大大提高。然而，由于每个记录都对应一个索引项，就使得数据集大时，索引的规模也很大。对于内存有限的计算机来说，可能就需要反复访问磁盘，反而可能导致查找性能大大降低。由于这个问题，又提出了树形索引、多级索引的概念。 因为关键码是有序连续存放的，因此稠密索引的插入和删除操作的执行时间代价可能非常高昂，与插入排序的时间代价是相同的。 ### 分块索引 稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其按块排序（块间有序），然而再对每一个块建立索引项，从而减少索引项的个数，这就是**分块索引**。 分块索引就跟图书馆藏书是一样的道理。把书籍分门别类摆放，然后指出该类图书所在楼层或书架。比如第一层是人文图书、第二层是科技图书、第三层是…… 按块排序，指得是将数据集的记录先分成了若干块，同时这些块需要满足以下条件： - 块内无序，即每一块内的记录不要求有序。 - 块间有序。如第二块所有记录的关键字均要大于第一块中所有记录的关键字。 分块索引的索引项结构分三个数据项： - 最大关键码，存储每个块中的最大关键字，便于分块。 - 块含有的记录个数，便于循环遍历该块时使用。 - 指向块首数据元素的指针，便于遍历记录。 在分块索引表中查找，分两步进行： 1. 在分块索引表中查找要查关键字所在的块。由于块间有序，可以使用折半、插值查找等算法。 2. 根据块首指针找到该块第一个记录，同时用块记录个数作为循环次数，顺序遍历整个块以查找关键码。由于块内无序，该步只能顺序查找。 ### 倒排索引 **倒排索引**(Inverted Index)源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录，它使用一张记录号表，存储具有相同次关键字的所有记录的记录号（也可以是指向记录的指针或该记录的主码）。 假设现在有几个文件，我们想根据关键字来查找其所在文件，则可以建立下表来查询： |次关键字|文件名| |--| |"Hello"|"HelloWorld.c", "Greeting.txt"| |"go"|"MyProgram.go"| 当我们查找"Hello"时，可以查上表，得知它在文件HelloWrold.c和Greeting.txt都有出现。因为是根据属性值来确定记录的位置，而不是由记录来确定属性值，因此称这种方式为倒排索引。 倒排索引的优点是查找记录非常快，生成索引表后，查找时都不用读取记录，即可直接得到结果。但缺点就是记录号不定长。比如上面的例子，对于"Hello"有两个记录，然而对于"go"却只有一个，因此也使得维护比较困难。 倒排索引在搜索引擎中使用到，但却要复杂得多。比如我们不仅仅想知道"Hello"在哪些文件出现过，还想知道具体到哪些行等等。同时，由于互联网海量数据的特点，往往要做非常多的压缩、优化操作。 ## 树形索引 树形索引使用了特殊的数据结构B树或B+树来实现索引。由于这些树是平衡树，因此查找效率是输入规模的对数。相比于线性索引，树形索引有优秀的插入、删除操作效率，它能够在对数时间内完成操作，而不像线性索引那样需要线性时间。 现实中的数据库产品常使用B+树实现索引，因为它对很多类型的查询都有效： - 全值匹配。查询可以和索引中的所有列进行匹配。 - 匹配最左前缀。可以只使用索引的前面几列。 - 匹配列前缀。可以只匹配某一列的值的开头部分。 - 匹配范围值。相当于匹配列前缀的推广。 - 精确匹配某一列并范围匹配另外一列。 - 只访问索引的查询。由于索引中包含部分关键字，因此该查询只需要访问索引，而无须访问数据行。 虽然树形索引有很多优点，但它也是有所限制的： - 如果不是按照索引的最左列开始查找，则无法使用索引。 - 不能跳过索引中的列。 - 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。 ## 多级索引 当索引项越来越多的时候，将占据许多的磁盘块，这导致磁盘I/O的操作逐渐增多，使得查找效率下降。这时候，我们可以把索引看作是数据，对其进行索引。在操作系统中，具有多个磁盘块的文件的索引结点就是按照多级索引的方式管理的。 ## References - 程杰. 大话数据结构[M]. 清华大学出版社, 2011. 赏 Wechat Pay Alipay 工厂模式 线性查找算法
