Nothing is impossible!

MySQL 学习笔记(一) MySQL-The index of B+Tree

Posted on By zhaofuchao

1.MySQL 索引为何是B+Tree

最近看了看MySQL的一些较为深一点知识,感触颇深,觉得有必要记录一下,就先从索引开始吧,对于初学者读起来可能有点困难,入门和中级的同学比较适合,大佬请绕行。。。

我们还是从比较简单的二叉树说起,由简到难,最后说B+Tree, 一定要有耐心哦,下面开始:

1.1.二叉树基本结构及不能应用于MySQL索引的原因

对数据的加速检索,首先想到的就是二叉树,二叉树的查找时间复杂度可以达到O(log2(n))。下面看一下二叉树的存储结构,入图一:

图一。

二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率,但是它有一个问题:二叉树以第一个插入的数据作为根节点,如上图中,如果只看右侧,就会发现,就是一个线性链表结构。

如果我们要查询的数据为6则需要遍历所有的节点才能找到6,即,相当于全表扫描,就是由于存在这种问题,所以二叉查找树不适合用于作为索引的数据结构。

基于这样的推演,为了解决存在线性链表的问题,很容易就能够想到平衡二叉查找树。下面看看平衡二叉树是怎样的,如图二:

图二。

平衡二叉查找树定义为:节点的子节点高度差不能超过1,如上图中的节点20,左节点高度为1,右节点高度0,差为1,所以上图没有违反定义,他就是一个平衡二叉树。保证二叉树平衡的方式为左旋,右旋等操作,至于如果左旋右旋,可以自行去搜索相关的知识。 如果上图中平衡二叉树保存的是id索引,现在要从id = 8的数据,首先要把根节点加载进内存,用8和10进行比较,发现8比10小,继续加载10的左子树。把5加载进内存,用8和5比较,同理,加载5节点的右子树。此时发现命中,现在要加载id为8的索引对应的数据。

到这里,平衡二叉树解决了存在线性链表的问题,数据查询的效率好像也还可以,基本能达到O(log2(n)), 那为什么mysql不选择这样的数据结构呢,他又存在什么样的问题呢?

问题1: 搜索效率不足,一般来说,在树结构中,数据所处的深度,决定了搜索时的IO次数。如上图中搜索id = 8的数据,需要进行3次IO。当数据量到达几百万的时候,树的高度就会很恐怖。

问题2: 查询不不稳定,如果查询的数据落在根节点,只需要一次IO,如果是叶子节点或者是支节点,会需要多次IO才可以。

问题3: 节点存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性,也没有利用好磁盘IO的预读能力。

讲到这里差不多就应该明白为何二叉树不能作为MySQL索引的原因了。那么B-Tree又有何优势呢?下面我们慢慢揭开B-Tree的神秘面纱。

1.2.B-Tree的基本结构以及做MySQL的索引存在的问题。

我们先来看一下B-tree的数据结构。 B树是一种多路自平衡搜索树,它类似普通的二叉树,但是B书允许每个节点有更多的子节点。B树示意图如图四:

如图4.

上图为一个2-3树(每个节点存储2个关键字,有3路),多路平衡查找树也就是多叉的意思,从上图中可以看出,每个节点保存的关键字的个数和路数关系为: 关键字个数 = 路数 – 1。 假设要从上图中去寻找id = 28的数据,B TREE 搜索过程如下:

  • 首先把根节点加载进内存,加载了17,35两个关键字,
  • 17<28<35;
  • 取p2,加载23,34两个关键字;
  • 取p2,加载28,命中28后。
  • 接下来加载28对应的数据, 就去找28对应的数据区,数据区中存储的是具体的数据或者是指向数据的指针。

能够很好的利用操作系统和磁盘的交互特性,MYSQL为了很好的利用磁盘的预读能力,将页大小为16K,即将一个节点(磁盘块)的大小设置为16K,一次IO将一个节点(16K)内容加载进内存。这里,假设关键字类型为 int,即4字节,若每个关键字对应的数据区也为4字节,不考虑子节点引用的情况下,则上图中的每个节点大约能够存储(16 * 1000)/ 8 = 2000个关键字,则共2001个路数。对于二叉树,三层高度,最多可以保存7个关键字,而对于这种有2001路的B树,三层高度能够搜索的关键字个数远远的大于二叉树。 在B-Tree保证树的平衡的过程中,每次关键字的变化,都会导致结构发生很大的变化,这个过程是特别浪费时间的,所以创建索引一定要创建合适的索引,而不是把所有的字段都创建索引,创建冗余索引只会在对数据进行新增,删除,修改时增加性能消耗。 B树的特点: (1)所有键值分布在整个树中 (2)任何关键字出现且只出现在一个节点中 (3)搜索有可能在非叶子节点结束 (4)在关键字全集内做一次查找,性能逼近二分查找算法

既然B树已经很好的解决了问题,为什么MYSQL还要用B+TREE? 我们先对B-Tree和B+Tree做一个对比:

  • 1、B+TREE是B-TREE的变种,B-TREE能解决的问题,B+TREE也能够解决(降低树的高度,增大节点存储数据量)。
  • 2、 B+TREE扫库和扫表能力更强,如果我们要根据索引去进行数据表的扫描,对B-TREE进行扫描,需要把整棵树遍历一遍,而B+TREE只需要遍历他的所有叶子节点即可(叶子节点之间有引用)。
  • 3、B+TREE磁盘读写能力更强,他的根节点和支节点不保存数据区,所有根节点和支节点同样大小的情况下,保存的关键字要比B-TREE要多。而叶子节点不保存子节点引用。所以,B+TREE读写一次磁盘加载的关键字比B-TREE更多。
  • 4、B+TREE排序能力更强,如下节的图5中可以看出,B+TREE天然具有排序功能。
  • 5、B+TREE查询效率更加稳定,每次查询数据,查询IO次数一定是稳定的。当然这个每个人的理解都不同,因为在B-TREE如果根节点命中直接返回,确实效率更高。

1.3.B+Tree的基本结构以及能做MySQL索引的原因

先看看B+TREE是怎样的,B+TREE是B TREE的一个变种,在B+树种,B树种的路数和关键字的个数的关系不再成立了,B+TREE中,数据检索规则采用的是左闭合区间,路数和关键个数关系为1比1,具体如下图5所示:

图5

如果上图中是用ID做的索引,如果是搜索id = 1的数据,搜索规则如下: 加载跟节点到内存,获取到1,28,66; 1<=1; 加载子节点获取1,20,20; 1<=1 加载叶子节点获取到1;

所以相较于B-Tree,B+Tree的优势如下:

  • 1、B+TREE 关键字的搜索采用的是左闭合区间,之所以采用左闭合区间是因为他要最好的去支持自增id,这也是mysql的设计初衷。即,如果id = 1命中,会继续往下查找,直到找到叶子节点中的1。
  • 2、B+TREE 根节点和支节点没有数据区,关键字对应的数据只保存在叶子节点中。即只有叶子节点中的关键字数据区才会保存真正的数据内容或者是内容的地址。而在B树种,如果根节点命中,则会直接返回数据。并且在B+TREE中,叶子节点不会去保存子节点的引用。
  • 3、B+TREE叶子节点是顺序排列的,并且相邻的节点具有顺序引用的关系,如上图中叶子节点之间有指针相连接。
  • B+树与B树的不同在于:
  • (1)所有关键字存储在叶子节点,非叶子节点不存储真正的data
  • (2)为所有叶子节点增加了一个链指针

既然选中了B+Tree做索引,那么MySQL是如何实现的呢? 这个问题在第二章详细回答,如下。

2.MySQL的B+Tree具体落地形式

mysql5.5版本之前采用的是MYISAM引擎,5.5之后采用的是innodb引擎

本章主要讲解的是MySQ根据B+TREE索引结构不同的两种存储引擎(MYISAM 和 INNODB)的实现,mysql有多种数据的存储引擎,这里讲解MYISAM和innodb,如图6所示,为MySQL的所有存储引擎:

图6

2.1 MYISAM存储引擎索引

从图6中可以看出,使用MYISAM存储引擎存储数据库数据,一共有三个文件: Frm,表的定义文件。MYD:数据文件,所有的数据保存在这个文件中。MYI:索引文件。 在MYISAM存储引擎中,数据和索引的关系如图7:

图7

如果要查询id = 101的数据,先根据MYI索引文件(如上图左)去找id = 101的节点,通过这个节点的数据区拿到真正保存数据的磁盘地址,再通过这个地址从MYD数据文件(如上图右)中加载对应的记录。 如果是多个索引,表现形势入图8

图8

所以在MYISAM存储引擎中,主键索引和辅助索引是同级别的,没有主次之分。

2.2 Innodb存储引擎

首先看一下聚集索引的概念,聚集索引定义为:数据库表行中数据的物理顺序和键值的逻辑顺序相同。 Innodb以主键为索引来聚集组织数据的存储,下面看看Innodb是如何组织数据的。 Innodb只有两个文件如图6,Frm文件: 表的定义文件,和Ibd文件,没有专门保存数据的文件。数据以主键进行聚集存储,把真正的数据保存在叶子节点中。innodb设计初衷认为主键才是最主要的索引。具体如下图9所示:

图9

叶子节点的数据区保存的就是真实的数据,在通过索引进行检索的时候,命中叶子节点,就可以直接从叶子节点中取出行数据。 在innodb中,辅助索引的格式如下图10所示

图 10

主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是主键索引关键字的值。搜索过程为:假如要查询name = seven的数据,先在辅助索引中查询最后找到主键id = 101,再在主键索引中搜索id为101的数据,最终在主键索引的叶子节点中获取到真正的数据。所以通过辅助索引进行检索,需要检索两次索引。

所以把Innodb和MYISAM放在同一个图中,就可以和明显看出二者的区别,入图11。

图11

3. 索引拓展

3.1 创建索引的几大原则

拓展一下创建索引的几大原则 1.列的离散型:离散型的计算公式:count(distinct col):count(col),离散型越高,选择型越好。 2.最左匹配原则: 对于索引中的关键字进行对比的时候,一定是从左往右以此对比,且不可跳过。之前讲解的id都为int型数据,如果id为字符串的时候,如下图12:

图12

当进行匹配的时候,会把字符串转换成ascll码,如abc变成97 98 99,然后从左往右一个字符一个字符进行对比。所以在sql查询中使用like %a 时候索引会失效,因为%表示全匹配,如果已经全匹配就不需要索引,还不如直接全表扫描。 3.最少空间原则 前面已经说过,当关键字占用的空间越小,则每个节点保存的关键字个数就越多,每次加载进内存的关键字个数就越多,检索效率就越高。

3.2 联合索引

单列索引:节点中的关键字[name]; 联合索引:节点中的关键字[name, phoneNum]; 可以把单列索引看成特殊的联合索引,联合索引的比较也是根据最左匹配原则。 联合索引列的选择原则: (1) 经常用的列优先(最左匹配原则) (2) 离散度高的列优先(离散度高原则) (3) 宽度小的列优先,(最少空间原则) (4)减少冗余索引,冗余索引会增减维护B+TREE平衡时的性能消耗,并且占用磁盘空间

3.3 覆盖索引

如果查询的列,通过索引项的信息可直接返回,则该索引称之为查询SQL的覆盖索引。使用到覆盖索引的情况下,不需要进入到数据区,数据就能直接返回,覆盖索引可以提高查询的效率。 下面通过例子说明覆盖索引。 表:teacher 索引:PK(id), key(name, phoneNum), unique(teacherNo)

下面哪些sql使用到了覆盖索引?

Select teacherNo from teacher where teacherNo = ?:使用到了,检索到teacherNo 时候,可以直接将索引中的teacherNo 值返回,不需要进入数据区。

Select id,teacherNo from teacher where teacherNo = ?:使用到了,辅助索引的叶子节点保存了主索引的值,所以检索到辅助索引的叶子节点的时候就可以之间返回id。

Select name,phoneNum from teacher where teacherNo = ?:没有用到

Select phoneNum from teacher where name = ?, 使用到了。

知道了覆盖索引,就知道了为什么sql中要求尽量不要使用select *,要写明具体要查询的字段,一个原因就是,这样在使用到覆盖索引的情况下,不需要进入到数据区,数据就能直接返回,提升了查询效率。

3.4 索引-铁一般的结论

  • 1、索引列的数据长度满足业务的情况下能少则少。

  • 2、表中的索引并不是越多越好。

  • 3、Where 条件中,like 9%, like %9%, like%9,三种方式都用不到索引。后两种方式对于索引是无效的。第一种9%是不确定的,决定于列的离散型,结论上讲可以用到,如果发现离散情况特别差的情况下,查询优化器觉得走索引查询性能更差,还不如全表扫描。

  • 4、Where条件中 NOT IN 无法使用索引

  • 5、多用指定查询,只返回自己想要的列,少用select *。

  • 6、查询条件中使用函数,索引将会失效,这和列的离散型有关,一旦使用到函数,函数具有不确定性。

  • 7、联合索引中,如果不是按照索引最左列开始查找,无法使用索引。

  • 8、对联合索引精确匹配最左前列并范围匹配另一列,可以使用到索引。

  • 9、联合索引中,如果查询有某个列的范围查询,其右边所有的列都无法使用索引。