1. 什么是索引

索引提供指向存储在表的指定列中的数据值的指针,然后根据您指定的排序顺序对这些指针排序。数据库使用索引的方式与您使用书籍中的索引的方式很相似:它搜索索引以找到特定值,然后顺指针找到包含该值的行。这样就避免了一一比对数据的IO损耗,大大提高了查询效率。

2. 索引的实现方法

2.1 B-tree索引

B树索引是数据库当中使用最广泛的索引。其主要使用B+数这种数据结构(改进的而二分查找树),值全部保存在叶子节点,查询效率比较稳定。B+数的根节点常驻内存,每次查找的IO次数和树的高度h相关。B树的结构如下:

关于B树的一个性质,在数据库中采用的B树结构的索引,除了上面平衡树的基础特征外,结合数据库索引使用的需要,都有如下的结构要求。

  • 内节点不存储data,只存储key和指向下级节点的指针;叶子节点不存储指针,存储真正的数据。即 内节点的作用是导航,叶节点才真正存数据。 不同的索引类型,叶节点data域存储的东西会有不同,导致查询也会不同。在后面会对此详细介绍。
  • 在叶子节点上都会有个双向的指针指向相邻的叶子节点。提高在索引键上的区间访问的性能。通常在B树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点。因此可以对B树进行两种查找运算:一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找。

B+数按照叶子节点存储的内容不同又分以下几种

  1. B树叶节点存完整数据的索引结构:即聚集索引,存储的索引值在叶子节点上,一个表只能一个聚集索引。物理上连续,适合对属性的范围查询,例如查询学分30-100分之间的学生的数据。当然如果联合索引就是查询的结果,采用联合索引这种非聚集索引性能更加好。
  2. B树叶节点存物理指针的索引结构(常见):非聚集索引
  3. B树叶节点存逻辑指针的索引结构:辅助索引

2.2 哈希索引

hash索引顾名思义,基于hash函数来找到索引值,常数时间复杂度内就可以找到数据(前提不发生成图),效率很高。不过不是所有DBMS都支持这种索引方式。基于哈希的方法实现了索引,虽然在某种场景下效率高了,但是显然局限性大了很多,比如查询中只能用等于和不等于,不支持范围的查找。因为哈希结构不像B+树一样在最后叶子节点上还维持一个顺序结构。同时是哈希索引不太稳定,如果冲突较多,甚至还是可能发生全表索引。

3 倒排索引

倒排索引是搜索引擎中核心技术之一。有了倒排索引技术,搜索引擎才能有效率的进行数据库查找、删除等操作。
倒排索引的思想
传统索引针对数据表上已有的表的行记录,然后找到了属性值所在的位置。倒排索引则相反,根据已有的属性值,去找到相应的行记录所在的位置。在搜索引擎中,单词就是对应的属性值,记录就对应着不同的网页。

倒排索引在搜索引擎中的应用

  • 单词和单词字典:搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
  • 倒排列表:倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。
  • 倒排文件:所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

搜索引擎中倒排索引大概流程框架

  1. 用户在搜索引擎搜索框输入查询词进行搜索时,搜索引擎会对查询词进行切词以及近义词匹配等操作
  2. 根据原始查询词得到一系列的单词列表。
  3. 根据搜索引擎内部的字典来查询每个单词对应的倒排列表,从而定位到包含这个单词的网页或者说是文档。
  4. 搜索引擎根据特定的网页排序算法将查询到的网页进行排序,通过前端将搜索结果展示给用户。

搜索引擎中倒排索引大概流程框架:用户在搜索引擎搜索框输入查询词进行搜索时,搜索引擎会对查询词进行切词以及近义词匹配等操作,根据原始查询词得到一系列的单词列表。然后根据搜索引擎内部的字典来查询每个单词对应的倒排列表,从而定位到包含这个单词的网页或者说是文档。最后搜索引擎根据特定的网页排序算法将查询到的网页进行排序,通过前端将搜索结果展示给用户。下图2为倒排索引的主要流程:

4. 位图索引

位图索引的使用一定要非常小心,同时满足以下两点的场景可以使用:

  1. 属性值可选项非常少的情况(比如性别)
  2. 属性基本上不做修改,十分固定(比如性别)

位图索引原理
将每行数据的属性值用二进制表示,这样多行就可以形成一个位图,对属性值做and,or,in,count等操作的时候可以进行或运算,快速得到结果。

5. R树索引(MYSQL)

R树索引基于R树数据结构,解决了高纬空间搜索问题。篇幅限制,这里就不细说了。
tree索引用于查询空间数据,比如查找所有离San Francisco, CA. 10英里之内的城市。

6. 索引与性能

索引加快了查询速度,但是要付出代价。比如表的插入和删除速度会减慢,因为需要更新索引。如果表需要不断更新,索引很可能会导致performance问题。还有空间代价。索引会占用内存或磁盘空间。单个索引比表小,因为它不存所有的表数据,而是存相应的指针。表越大,索引通常也会跟着变大。

总结:频繁更新的数据列加索引可能导致性能下降。

参考资料:
http://www.cnblogs.com/maybe2030/p/4791611.html?utm_source=tuicool&utm_medium=referral