索引原理

标签: 索引 原理 | 发表时间:2014-12-20 18:05 | 作者:
出处:http://www.iteye.com
1 索引的定义
索引是存储引擎用于快速找到记录的一种数据结构。 也就会说索引也是一种数据结构,也占用磁盘空间。

2 索引的价值
索引是对查询优化最有效的手段,可以将查询提升几个数量级,相当牛掰啊。

索引优点:
1)索引大大减少了服务器需要扫描的数据量。
2)索引可以帮助服务器避免排序和临时表。
3)索引可以将随机IO变为顺序IO。



3 索引原理
数据库索引可以想象成一本书的目录,如果想在一本书中找到某个主题,那么先到书的目录中找到这个主题,然后根据目录提供的页码,找到要找的主题。数据库的索引道理是一样一样的,因为通常做索引的只有表中的几个字段,所以索引占用的空间也更小,并且索引是有序的,所以根据索引查起来会快很多。

说到索引如果没有特别指明索引的类型,那么说的就是B-Tree索引,它使用B-Tree的数据结构来存储数据,本文说的也是B-Tree索引,其他索引如位图索引、全文索引、哈希索引等均为涉及。实际上大多数数据库使用B+Tree,即每个叶子节点都包含指向下一个叶子节点的指针,这样方便叶子节点的范围遍历。



因为通常索引页会比数据页小,所以数据表刚开始填充数据时,索引页只有一个,可能的示意图如下所示:
 


索引块只有一个,数据块有2个,图中的块也可以成为页。

随着表中的数据量逐步增多,一个索引块可能存不下了,这样就会多出一层管理块,如下图所示:




然后随着数据量越来越多,层级可能越来越多,最终可能会如下图所示:



4 索引适用的查询和限制
对于如下表:
create table people(
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date          not null,
gender enum('m','f') not null,
key(last_name,first_name,dob)
);

脚本中的key表示建立的索引。
4.1 走索引的查询

1)全值匹配。匹配所有的列,即根据last_name,first_name和dob查找。
2)匹配最左前缀。比如根据last_name或者根据last_name和first_name查找。
3)匹配列前缀。例如查找last_name以某字母开头的。比如用like 'J%' ,如果使用like '%J%'和like '%J' 就无法走索引了。
4)匹配范围值。例如查找last_name在某个范围之间的数据。比如last_name between 'a' and 'c';
5)精确匹配某一列并范围匹配另外一列。比如last_name='ab' and first_name between 'xx' and 'xxoo';
6)只访问索引的查询。例如查询的列都在索引中,例如select last_name,first_name from people where last_name='xxx'; 这个因为无需回表,所以速度最快。
7)group by 也按如上规则决定是否通过索引进行排序。select * from people where last_name='xx' order by first_name;//可以按索引排序。
4.2 不走索引的查询
1)只能根据最左前缀使用索引,否则无法使用索引。例如select * from people where first_name='xx',这个语句无法使用索引。
2)不能跳过索引的列。例如:select * from people where last_name='xx' and dob='2014-1-1';这个就只能使用last_name这一列的索引了。
3)如果某个列是范围查询,那么他右边的列就不能使用索引了。比如select * from people where last_name='xx' and first_name like 'J%' and dob='2014-1-1',这样dob这一列的索引就失效了。
4)如果带有表达式则无法使用索引。比如select * from people where substring(last_name,1,2) ='xx';
5) group by 一个升序一个降序。select * from people order by last_name desc,first_name asc;//不走索引。





5什么情况适合建索引
1)表的数据量。
对于数据量非常小的表,使用全表扫描通常更有效。
对于中到大型的表,索引非常有效。但对于特大型的表,建立和使用索引的代价随之增长,这是可以采用分区表或者通过字段做hash分表的策略解决。


2)字段的选择性。
选择性高的字段适合建索引,否则不适合。例如性别就2个值,'男'或者'女',严格来说还有变性人、皇帝身边的缺少某个关键器官的、还有某国的人妖、还有黄海波找的那种,还真不少啊,哈哈。这种就不适合建索引,还有固定的几种状态的字段都不适合建索引。

选择性计算公式:
select count(distinct col)/count(*) from tbl; 如果表的数据量很大,计算性别的选择性的话,接近于0。


6 索引的开销
索引可以提高查询速度,但是索引会增加insert delete update的开销,做这些操作的时候需要维护索引,所以要做权衡,并不是索引越多越好。



7 MyISAM和InnoDB索引的区别



由图中可以看出,主要区别如下:
1)InnoDB主键索引存储了整个数据行,MyISAM存储的是指向数据行的指针。
2) InnoDB二级索引存储的是主键,MyISAM存储的仍然是指向数据行的指针。



8 MySQL索引和锁
索引可以减少InnoDB访问的数据行数,所以也减少了锁定的数据行。但是即使有索引,也可能会锁住一些不需要的数据,如果没有索引的话会更糟糕。




9 参考资料
《高性能MySQL》
《Java特种兵》





已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [索引 原理] 推荐:

索引原理

- - ITeye博客
索引是存储引擎用于快速找到记录的一种数据结构. 也就会说索引也是一种数据结构,也占用磁盘空间. 索引是对查询优化最有效的手段,可以将查询提升几个数量级,相当牛掰啊. 1)索引大大减少了服务器需要扫描的数据量. 2)索引可以帮助服务器避免排序和临时表. 3)索引可以将随机IO变为顺序IO. 数据库索引可以想象成一本书的目录,如果想在一本书中找到某个主题,那么先到书的目录中找到这个主题,然后根据目录提供的页码,找到要找的主题.

mysql索引原理之B+/-Tree

- - CSDN博客架构设计推荐文章
索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree. 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子. 假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录.

数据库索引的实现原理

- - 孟飞阳的博客
说白了,索引问题就是一个查找问题. 二、数据库索引介绍及特点说明. 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据. 索引的实现通常使用B树及其变种B+树. 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法.

【Oracle】-【创建索引】-创建索引的操作原理与一些体会

- - CSDN博客数据库推荐文章
1、将index key的data读到cache. 如果之前这部分数据未读到DB Cache,那么此时可能有db file scatter read write的等待事件. 2、对index key的data进行排序. 排序的操作,如果sort_area_size或pga_aggregate_target不大的情况下,可能就会做disk sort,我们知道,磁盘排序的效率要小于Cache不少,因此速度上肯定受影响,会有direct path read/write,同时也会消耗CPU time.

MySQL索引背后的数据结构及算法原理

- Mike - 博客园-EricZhang&#39;s Technology Blog
在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,很多东西,如果你愿意稍稍往深处挖一点,那么扑面而来的一定是各种数据结构和算法知识. 例如几乎每个程序员都要打交道的数据库,如果仅仅是用来存个数据、建建表、建建索引、做做增删改查,那么也许觉得数据结构和这东西没什么关系.

SqlServer索引的原理与应用 - 张龙豪

- - 博客园_首页
索引的用途:我们对数据查询及处理速度已成为衡量应用系统成败的标准,而采用索引来加快数据处理速度通常是最普遍采用的优化方法. 索引是什么:数据库中的索引类似于一本书的目录,在一本书中使用目录可以快速找到你想要的信息,而不需要读完全书. 在数据库中,数据库程序使用索引可以重啊到表中的数据,而不必扫描整个表.

【转载】MySQL索引原理及慢查询优化

- - 数据库 - ITeye博客
MySQL凭借着出色的性能、低廉的成本、丰富的资源,已经成为绝大多数互联网公司的首选关系型数据库. 虽然性能出色,但所谓“好马配好鞍”,如何能够更好的使用它,已经成为开发工程师的必修课,我们经常会从职位描述上看到诸如“精通MySQL”、“SQL语句优化”、“了解数据库原理”等要求. 我们知道一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,所以查询语句的优化显然是重中之重.

解读百度搜索引擎工作原理

- - MyBlog
【文章摘要】以下便是百度搜索引擎决定搜索结果排序时考虑的六大原则,那么六大原则的侧重点是怎样的呢. 哪个原则在实际应用时占比最大呢. 在百度搜索引擎早期,这些阈值的确是相对固定的,比如“相关性”在整体排序中的重量可以占到七成. 但随着互联网的不断发展,检索技术的进步,网页数量的爆发式增长,相关性已经不是难题.

全文检索引擎Solr系列—–全文检索基本原理

- - ImportNew
场景:小时候我们都使用过新华字典,妈妈叫你翻开第38页,找到“坑爹”所在的位置,此时你会怎么查呢. 毫无疑问,你的眼睛会从38页的第一个字开始从头至尾地扫描,直到找到“坑爹”二字为止. 这种搜索方法叫做 顺序扫描法. 对于少量的数据,使用顺序扫描是够用的. 但是妈妈叫你查出坑爹的“坑”字在哪一页时,你要是从第一页的第一个字逐个的扫描下去,那你真的是被坑了.