数据库索引原理理解

 

1.什么是索引?

我想这个用过数据库的人都应该知道了,索引类似于书的目录,主要用于提高查询效率,也就是按条件查询的时候,先查询索引,再通过索引找到相关的数据,索引相当于记录了对某个关键词,指定到不同的文件,或者文件里的不同位置,当然索引自身也是通过文件来保存的。

2.索引的类型

有两种基本的索引结构,也就是索引文件的保存方式,一个是顺序索引,就是根据值的顺序排序的(这个文件里面的值,也就是为其建索引的字段值,是顺序的放在索引文件里面),另外一个是散列索引,就是将值平均分配到若干散列桶中,通过散列函数定位的。

2.1.顺序索引

顺序索引下面又有很多概念。
如果被索引的字段本身按照一定的顺序排序,那么这种索引叫做聚集索引。否则叫做非聚集索引
如果被索引的每条记录都有一个索引与其对应,那么这种索引叫做稠密索引,否则叫做稀疏索引(对记录进行分组索引)。
顺序索引分为两类,单级索引(不怎么用)和多级索引(通常是B+树,大量使用)。
单级索引就是把所有的索引字段以及对应的文件位置按顺序一个个的排列出来,这种索引查找起来比较慢,因为是顺序存储的,可以使用二分查找法,但是总体来说效率不高,这种索引是最基础的索引,一般不用,ORACLE里面好像不支持这种索引。
多级索引实际上就是在单级索引之上再加索引(稀疏索引),也就是指向索引的索引,二级索引上面还可以再加三级索引,可以不停的加,加到最后最上层只剩下一个节点(根节点),就成了一个树状结构了。
我 们经常听到B+树就是这个概念,用这个树的目的和红黑树差不多,也是为了尽量保持树的平衡,当然红黑树是二叉树,但B+树就不是二叉树了,节点下面可以有 多个子节点,数据库开发商会设置子节点数的一个最大值,这个值不会太小,所以B+树一般来说比较矮胖,而红黑树就比较瘦高了。
关于B+树的插入,删除,会涉及到一些算法以保持树的平衡,这里就不详述了。ORACLE的默认索引就是这种结构的。
如果经常需要同时对两个字段进行AND查询,那么使用两个单独索引不如建立一个复合索引,因为两个单独索引通常数据库只能使用其中一个,而使用复合索引因为索引本身就对应到两个字段上的,效率会有很大提高。

2.2 散列索引

第二种索引叫做散列索引,就是通过散列函数来定位的一种索引,不过很少有单独使用散列索引的,反而是散列文件组织用的比较多。
散列文件组织就是根据一个键通过散列计算把对应的记录都放到同一个槽中,这样的话相同的键值对应的记录就一定是放在同一个文件里了,也就减少了文件读取的次数,提高了效率。
散列索引呢就是根据对应键的散列码来找到最终的索引项的技术,其实和B树就差不多了,也就是一种索引之上的二级辅助索引,我理解散列索引都是二级或更高级的稀疏索引,否则桶就太多了,效率也不会很高。

2.3 位图索引

位图索引是一种针对多个字段的简单查询设计一种特殊的索引,适用范围比较小,只适用于字段值固定并且值的种类很少的情况,比如性别,只能有男和女,或者级别,状态等等,并且只有在同时对多个这样的字段查询时才能体现出位图的优势。
位 图的基本思想就是对每一个条件都用0或者1来表示,如有5条记录,性别分别是男,女,男,男,女,那么如果使用位图索引就会建立两个位图,对应男的 10110和对应女的01001,这样做有什么好处呢,就是如果同时对多个这种类型的字段进行and或or查询时,可以使用按位与和按位或来直接得到结果 了。

聚集索引和非聚集索引的区别:
       汉语字典的正文本身就是一个聚集索引。比如,我们要查“安”字,就会很自然地翻开字典的前几页,因为“安”的拼音是“an”,而按照拼音排序汉字的字典是 以英文字母“a”开头并以“z”结尾的,那么“安”字就自然地排在字典的前部。如果您翻完了所有以“a”开头的部分仍然找不到这个字,那么就说明您的字典 中没有这个字;同样的,如果查“张”字,那您也会将您的字典翻到最后部分,因为“张”的拼音是“zhang”。也就是说,字典的正文部分本身就是一个目 录,您不需要再去查其他目录来找到您需要找的内容。正文内容本身就是一种按照一定规则排列的目录称为“聚集索引”。
     如果您认识某个字,您可以快速地从自动中查到这个字。但您也可能会遇到您不认识的字,不知道它的发音,这时候,您就不能按照刚才的方法找到您要查的字,而 需要去根据“偏旁部首”查到您要找的字,然后根据这个字后的页码直接翻到某页来找到您要找的字。但您结合“部首目录”和“检字表”而查到的字的排序并不是 真正的正文的排序方法,比如您查“张”字,我们可以看到在查部首之后的检字表中“张”的页码是672页,检字表中“张”的上面是“驰”字,但页码却是63 页,“张”的下面是“弩”字,页面是390页。很显然,这些字并不是真正的分别位于“张”字的上下方,现在您看到的连续的“驰、张、弩”三字实际上就是他 们在非聚集索引中的排序,是字典正文中的字在非聚集索引中的映射。我们可以通过这种方式来找到您所需要的字,但它需要两个过程,先找到目录中的结果,然后 再翻到您所需要的页码。

我们把这种目录纯粹是目录,正文纯粹是正文的排序方式称为“非聚集索引”。

通过以上例子,我们可以理解到什么是“聚集索引”和“非聚集索引”。

进一步引申一下,我们可以很容易的理解:每个表只能有一个聚集索引,因为目录只能按照一种方法进行排序。


总结:

B+树最常用,性能也不差,用于范围查询和单值查询都可以。特别是范围查询,非得用B+树这种顺序的才可以了。
HASH的如果只是对单值查询的话速度会比B+树快一点,但是ORACLE好像不支持HASH索引,只支持HASH表空间。
位图的使用情况很局限,只有很少的情况才能用,一定要确定真正适合使用这种索引才用(值的类型很少并且需要复合查询),否则建立一大堆位图就一点意义都没有了。


Total views.

© 2013 - 2018. All rights reserved.

Powered by Hydejack v6.6.1