mysql索引详解
索引(在mysql中也叫键(key))是数据库用来快速找到记录的一种数据结构。索引对于良好的性能非常关键,特别是当表中数据量越来越大的时候,索引对性能的影响就越来越明显了。在数据量较少并且负载较低的时候,不良的索引对性能的影响还不明显,但当数据量逐渐增大,则性能下降会越明显。
可以类比一本书的目录来理解mysql索引工作的原理,当我们想在一本书上找到某个主题内容时会先在书的”索引”(目录)上找到指定的页码,然后通过页码
找到具体的内容。mysql中存储引擎使用类似的方法来使用索引,先在索引中找到对应值,然后通过匹配的索引找到对应的行。假设运行下面的查询:
select * from product where product_id=10;如果在product_id列上建了索引,那么执行查询的时候会先找到product_id为10的索引(这一步很快),然后通过索引记录找到数据行返回里面的数据。一个索引可以包含一个或多个列的值,如果索引中包含多个列,那么列的顺序也非常重要,因为mysql只能高效的使用索引的最左边列。所以创建一个包含两个列的索引和创建两个只包含一个列的索引是大不相同的。
mysql中的索引是在存储层而不是服务层实现的,所以并没有统一的标准;各个存储引擎支持的索引类型不同,就算是支持同一种类型的索引,底层的实现方式也可能各有不同。目前用的最多的还是B-TREE索引，所以下面重点研究下B-TREE索引，顺便介绍下其它类型的索引。<
1.B-TREE数据结构结构简介
当平常谈论到索引的时候,如果没有特别指明类型,那多半说的是B-TREE索引,它使用B-TREE这种数据结构(很多存储引擎使用的是B+TREE)来存储数据;大部分mysql存储引擎都支持这种索引。存储引擎以不同的方式使用B-TREE索引,性能方面也各有优劣,MyISAM使用前缀压缩技术来减少索引的大小,而InnoDB则按原数据格式存储;MyISAM索引通过数据物理位置来引用被索引的行,而InnoDB则根据主键引用被索引的行。下面先来简单介绍下B+TREE的原理,先从B树说起:
B树是为了磁盘或其它存储设备而设计的一种多叉（相对于二叉树，B树每个内结点有多个分支，即多叉）平衡查找树,和红黑树有点类似,可以在插入 删除等操作的时候很好的保持树的平衡性,不同的是B树的一个节点可能有许多的子节点,从几个到几百个;一个包含n个元素的B树高度为lgn,但因为子节点数比红黑树多很多,这里实际的高度会小于红黑树,可以在O(lgn)的时间复杂度下实现各种插入 删除等动态集合操作。下面是英文字母集形成的B树：
可以看到每个非叶子结点中包含有n个关键字信息,并且是按顺序排列的,关键字之间还有指向子节点的指针(a,p,b:a b是关键字,p是指针),指针指向的子节点中关键字的大小都在指针两侧关键字之间;这里的n是和该节点的子节点数目有关的,比如一个节点有4个子节点,则会在节点中存储3个关键字。
B树可以用”阶”来度量,一个m阶的B树具有以下特点:
1) 树中每个结点最多含有m个孩子（m>=2）；
2) 除根结点和叶子结点外，其它每个结点至少有[ceil(m/2)]个孩子（其中ceil(x)是一个取上限的函数）；
3) 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
5) 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
- Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki
- Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)
- 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1
B树的特性：
1. 关键字集合分布在整颗树中
2. 任何一个关键字出现且只出现在一个结点中
3. 搜索有可能在非叶子结点结束
4. 其搜索性能等价于在关键字全集内做一次二分查找
5. 自动层次控制
下面是一个M=3的B树
B+树是B树的一种变种,也属于多叉平衡搜索树。和B树相比：
1.非叶子结点的子树指针与关键字个数相同
2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间）
3.为所有叶子结点增加一个链指针
4.所有关键字都在叶子结点出现
M=3的B+树
B+的搜索与B树也基本相同,区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找。
B+树的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
2.不可能在非叶子结点命中，非叶子节点不存储数据
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储(关键字）数据的数据层
4.更适合文件索引系统(更适合进行范围查找和排序查找)
2.B-TREE索引使用示例
通过上面的分析可以开看到存储引擎使用B+TREE索引之后,不再需要遍历全部的数据,而是直接在B+TREE上进行数据的查找,极大的优化了查询的效率。B+TREE对索引是顺序组织存储的,所以很适合查找范围数据。例如在一个基于文本域的索引树上,按字母顺序传递连续的值进行查找是非常合适的,所以像”找出所有以L到K开头的名字”这样的查找效率会很高。假设有如下数据表:
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('e','f') not null,
key(last_name,first_name,dob)
);对于表中的每一行数据,索引中包含了last_name first_name和dob的值,下图展示了该索引是如何组织数据的存储的:
索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时候列的顺序,看下最后一个条目,两个人的姓和名都一样,则根据他们的出生日期来进行排序。
可以使用B-TREE索引的类型：总的来说B-TREE索引适用于全键值,键值范围或键前缀查找.其中键前缀查找只适用于根据最左前缀的查找。以上面所建索引为例,适用于如下类型的查询:
- 全值匹配
全值匹配是指和索引中的所有列进行匹配,例如前面的索引可以用来查找姓名为 Cuba Allen,出生于1960-01-01的人。 - 匹配最左前缀
前面提到的索引可用于查找所有姓为Allen的人,即只使用索引的第一列 - 匹配列前缀
也可以只匹配第一列的开头部分,比如前面的索引可以用来查询姓以”J”开头的人 - 范围匹配
通过所有可以查找姓在Allen和Barry之间的人,这里也只使用了索引的第一列 - 精确匹配某一列并范围匹配另一列
可以通过查询所有姓为Allen,并且名字以”K”开头的人,即第一列last_name全匹配,第二列first_name范围匹配 - 只访问索引的查询
B-TREE通常支持只访问索引的查询,即查询只需要访问索引而不需要访问数据行
因为索引树中的节点是有序的,所以除了按值查找外,还可以用于查询中的Order by(排序查找)。一般来说,如果B-TREE索引支持按哪种方式查找值,那么也就可以排序,所以如果order by子句满足前面列出的几个条件,那么这个索引也可以满足排序要求。
3.B-TREE索引的限制和优点
索引的优点(针对所有类型的索引)
索引可以让服务器快速定位到表中某条数据的位置,但这并不是索引的唯一作用。根据索引使用的数据结构不同,索引也会有些不同作用,比如对于B+TREE结构类型的索引,因为数据是顺序存储的,所以可以用于做order by操作,另外因为相同的数据被聚集到了一起,所以可以用于group by操作,最后索引中就存储了实际的列值,所以有些查询可以只使用索引就完成全部的查询。对于不同类型的索引,可以将它们的有点归纳如下:
- 索引帮助服务器大大减少了需要扫描的数据量
- 所以可以避免服务器避免临时表和排序
- 索引可以帮助将随机IO变为顺序IO
B-TREE索引的限制
- 如果不是按照索引的最左边列进行查找,那么将无法使用索引。例如上面的索引无法用于查询某个名字为”bill”的人,也无法用于查询出生日期是1980-11-21的人,因为这两个都不是索引最左边的列;同理也无法用于查找名字以特定字母如”H”结尾的人。这个限制是因为B+TREE本身节点组织是按第一列进行的,所以没法根据其它列进行快速查找。
- 不能跳过索引中的列.也就是说前面的索引不能用来查询姓为”Smith”并且在某个特定日期出生的人,因为没有指定”first_name”,所以只能应用索引的第一列。这是因为B+TREE节点排序的时候,如果第一列相同就会按照第二列进行排序,如果第二列相同才会按第三列进行排序,现在忽略了第二列自然也就没法确定遍历节点的顺序了。
- 如果查询中有某个列的范围查询,则右边所有列都无法使用索引查找优化。例如查询
where last_name='Smith' and first_name like 'H%' and dob='1987-12-24'只能使用查询的前两列,因为like是一个范围条件,没有办法精确匹配第二列也就没有办法利用第三列的顺序来进行查找。
上面的几个限制其实都是B+TREE这种数据结构自身的限制。B-TREE可以说是最常见的索引,但是除了B-TREE之外还有基于哈希表的hash索引,基于R树可以用来存储空间数据的空间索引,类似于存储引擎可以进行关键字查找的全文索引。
这里有一种比较特别的关于哈希索引的用法,哈希索引必须在查询命中索引的所有列的情况下才会生效,所以一般数据库不会主动去建立哈希索引,但可能存在这样一种情况:表中用来建立索引的数据特别大(比如一个很长的url),这时候可以在表中附加一个该url通过Hash函数产生的较短的列,然后在这个列上建立索引,查询的时候将这个列也加入where条件中,这样可以比较显著的加快查询效率;需要注意的是使用的Hash函数产生的输出不能太大,所以MD5()这种函数不能使用,但是同时也要保证不会产生太多的冲突,所以不能用过于简单的hash函数,解决方案是可以自己实现一个hash函数也可以截取md5函数输出的一部分作为hash值。