为了看懂这一篇博文,请先看懂 B+ 树。因为 MySql 中大多数的引擎都是用这个数据结构作为索引的,特别是 InnoDB,因为基本上绝大多数的应用都是这个引擎,所以如果你有 10 份时间,花 9 份时间在这个引擎上也是没错的,本文后面要讨论的内容也大多数是基于这个类型的索引的。
我们要注意这一个特性,就是 B+ 树只有叶子节点才存储数据(也就是在数据库中指向某一行的指针),知道这个特性对于理解后面的内容非常重要。比如说主键要尽量的小,这样可以一次性读入更多的索引来查找数据,
BTW,这里有一个组成原理的知识需要大家掌握。对于机械硬盘来说,顺序的读取比随机读取快非常多。
机械硬盘长这样:
读取数据的时候,需要把磁头移动到相应的柱面上然后通过磁盘旋转来读取这一个柱面的数据。
读取时间 = 移动磁头 + 磁盘旋转读取 + 传输时间
期中移动磁头占绝大部分时间,如果顺序的读取的话,就只需要移动一次磁头,速度自然就提上去了。
随机读取,每读一块都要重新移动磁头到相应的位置上去,速度就慢很多。
#2 明确目标对于数据库查询优化,一个好的索引能让操作快上好几个数量级。索引的优点有
减少服务器需要扫描的数据量
帮助服务器避免排序和临时表
将随机 IO 变为 顺序 IO
一个好的索引应该具备以下三个优点。
索引将相关记录放在一起
索引中的顺序和查找顺序(比如 ORDER BY)操作一致
索引包含了需要查找的全部内容
书上把满足这几条需求的索引称作”三星索引“,在后面三星索引一章会介绍这几条原则。
#3 B+ 树索引 #3.1 如何最大化利用索引B+ 树索引只能高效的使用最左前缀,我们拿下面的索引举例:
key(姓,名,生日)只有以下的情况会用到索引:
全值匹配
全值匹配指的是匹配用到全部索引值,比如匹配姓为张,名为三,生日为 1998-11-11 的人,就可以用到索引。
WHERE 姓='张' AND 名='三' AND 生日='1998-11-11'
匹配最左前缀
可以匹配到姓为张的全部人,也就是用到索引的第一列
WHERE 姓='张'
匹配列前缀
比如里面有英文名字,可以匹配到所有姓是以 A 开头的人。
精确匹配到某一列并且范围匹配到另一列
可以使用从索引的左边到右边任意的数量的前缀,比如可以用一个半索引,查找用
WHERE 姓='张' AND like '三%'
在上面的情况除了按值查找能用到索引,ORDER BY 操作也能用到索引。
最左前缀匹配也就是匹配需要从最左边开始,无论 key 取多少位,一位,一位半,两位都行。上面的索引不能用到查找生日为某一天的人,因为没有用到前面的姓和名,也就是没有从最左边开始,直接从第三列开始了。
B-Tree 索引有如下几个限制
只能从索引的最左列开始查找
比如说上面的例子无法查找特定名的人,也不能查找特定生日的人
不能跳过前缀
上面的例子中,不能查找特定的姓并且生日为某一天的人,因为跳过了中间的索引名。
当前面的key用到范围查找后,后面的查找都不能使用索引查找了
比如说,不能查找这样的语句
WHERE 姓 LIKE 'A%' AND ...
在前面使用过范围查找后,后面的数据都不能通过索引找出了。
从上面的限制得出几个比较重要的优化点:
尽量避免多个范围匹配在同一个查询中出现
索引的顺序对于搜索至关重要
#4 聚簇索引什么是聚簇索引?对于这棵 B+ 树来说,如果不是采用的聚簇索引(比如在 MyISAM 引擎中),那些 Data 保存的是索引对应的列的指针,也就是说,如果你想要访问列的数据还需要根据指针查找到那一列然后才能获取数据。而对于聚簇索引来说,保存的是列的数据,在读入索引的时候可以直接将这一列的值读入。
聚簇指的是数据和 B+ 树的叶子节点紧凑的存储在一起。因为无法把数据放在两个地方,所以一张表只有一个聚簇索引。一般来说被索引的列是主键,如果没有主键,会隐式的生成一个主键作为索引。
聚簇索引的实现是在引擎层面上的,这里讨论的是 InnoDB,原理对于其他的同样引擎适用。
#4.1 聚簇索引优点