先由一个例子来引入索引:
假设有一张表Users,三个字段分别是user_name,user_age,user_sex。
现在要做一个这样的查询:找出表中所有用户名是“cwj”的人。一般会这样写:
select * from Users
where user_name = "cwj"
这样的查询语句,数据库会扫描Users表中的每一行数据来确定user_name是否为“cwj”;而且,我们要查询的是所有名为“cwj”的人,所以在你找到第一个符合条件的人时,查询并不会停止,所以一直要遍历整个表才能实现我们的需求。这就是 全表查询。
索引的作用
通过上面例子,应该大体能猜出索引的作用了。我们可能会想,数据库怎么如此笨拙,这样简单的一个查询却要遍历整张表,就像用人眼从头到尾一行一行找一样。当然不是,索引就是数据库解决这类问题的方法。使用索引的全部意义就是通过缩小一张表中的记录/行的数目,来加快搜索的速度!
什么是索引
说了那么多,是时候提出索引的概念了。一个索引是一个数据结构,这个数据结构中存储的是表中一个特定列的值,以及指向这个值所在行的指针。 需要注意的是,索引中并不存储这个列所对应行的其它字段的值,只是有一个指向这个列值所在行的指针,我们通过这个指针就可以找到这条记录的位置了。比如某个结点可能是这样的("cwj", 0x88989),后面这个指针就是这条记录在内存中的地址,如果没有这个指针,你就只能访问到一个单个的列值,这样是没有意义的。拿一个比喻来说,书的目录就像索引,目录每一章节就是键,对应的页码就是值,你想看具体哪一章当然不用翻遍全书,只需要在目录中找到那一章,然后根据对应的页码翻书就行了
索引使用的数据结构
那么什么样的数据结构能够作为索引呢。常用的有B-Tree,哈希索引,R-Tree,位图索引等等。
B-tree 是最常用的用于索引的数据结构,因为它的时间复杂度低,增删改查都可以在对数时间内完成。另外就是存储在B-Tree中的数据是有序的。有关B-tree数据结构的讨论将单独写一篇文章介绍。而像R-Tree以及位图索引不太了解,日后再说
哈希索引
说道哈希索引,就得知道哈希表和哈希算法的概念。哈希表是以键值对的方式存储对象的
存储: 首先对键进行哈希算法生成一个Hashcode,然后在哈希表中根据这个Hashcode找到存储的bucket的位置。注意这个bucket中存储的是键和值都有。然后如果刚好键的Hashcode相等,就称为冲突,解决冲突有很多种方法,最常用的是链表解决法,即将Hashcode相同的数据按照链表的方式存储。
查找:查找时,先对键进行哈希算法,并根据生成的Hashcode在哈希表中找到相应的值,如果冲突,就按链表依次查找。
Hash索引:原理是一样的,列的值作为键,列所对应的行的地址作为值。
优点:在等式比较的查询中速度非常快,因为不需要遍历整个列的值,而是根据值进行哈希算法得到地址,最多解决一下冲突而已,所以效率大大提升
缺点:既然哈希索引效率这么高,怎么不是数据库最常用的索引方式呢,当然是有局限的
- 因为哈希索引比较的是经过Hash计算后的值,所以只能进行等式比较,不能用于范围查询,比如要查个所有小于40岁的员工,这就没办法了。
- 虽然哈希值是按照顺序排列的,但是哈希值映射的真正数据在哈希表中就不一定按顺序排列,所以无法加快任何排序操作的效率
- 当哈希值大量重复,也就是冲突特别多时,检索效率会大大降低。
- 对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
- 哈希索引也不能避免表扫描,前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使找到了满足某个 Hash 键值的数据的记录,但这个记录可能是多条,所以也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。
数据库中创建索引
一般来说,当SQL(select * from Users where user_name = "cwj")运行时,数据库会检查在查询的列上是否有索引,假设有,数据库会接着检查使用这个索引查询是否合理(因为有些场景下,使用索引比起全表扫描更加低效。)
之前的例子中,在user_name列上创建索引的SQL如下:
create index name_index on Users (user_name);
创建联合索引:
create index name_index on Users (user_name, user_age);
数据库索引的代价
当然,事物都有两面性,索引这么好就没有问题吗?当然有
- 索引会占用空间,表越大,索引占用的空间就越大
- 性能损失, 当在表中进行增删改操作时,在索引中也会有相同的操作,因为建立在某列或多列的索引需要保存该列最新的数据
什么时候使用索引
一般来说,如果表中某列在查询过程中使用的非常频繁,那就在该列上创建索引
文章大部分内容引自http://blog.csdn.net/weiliangliang111/article/details/51333169
网友评论