Mysql索引原理及树

一、索引的分类

聚簇索引不是一种单独的索引类型，而是一种数据存储方式；通常称聚簇索引为一级索引，非聚簇索引称为二级索引；

在谈MyISAM和InnoDB区别的时候，我们都知道：
（1）MyISAM存放三个文件 .MYD（数据）、.MYI（索引）、.frm(建表语句)；而innodb是一个文件
（2）MyISAM不支持事物而InnoDB支持事物
（3）MyISAM执行count（*）能够直接返回行号。

二、聚簇索引

二、索引原理

2.1 MyISAM索引原理与数据分布

如下图所示，MyISAM按照数据插入的顺序存储在磁盘上，在行的旁边存储了行号，从0开始递增；

图1：MyISAM数据分布

MyISAM底层使用的是B-Tree，其主键索引与二级索引一样，叶子节点和非叶子节点上，保存着行号和关键字；我们都知道，B-Tree树，有指针域，和数据域，指针域指向下个子树，而数据域用来存储数据；
如下图的MyISAM索引树，例如我们对 age 字段进行加索引，第二层最左侧，是小于25的数据，并按照顺序排列第二层第二块数据，是大于25小于50的数据，同理，第二层第三块是大于50小于75的数据块，而第二块最右侧是大于75的数据块；
而下面树中的数据，诸如25、50等等就是age的真实数据，下面的data保存的是指向数据块的地址（或者说是行号，MyISAM的 .MYD的地址及行号）；
MyISAM的主键索引和其他索引在结构上没有什么不同，主键索引就是一个名为PRIMARY的唯一非空索引；

MyISAM索引存储的特点：
（1）叶子节点和非叶子节点存储这关键字和行号；
（2）要想范围查找，首先需要中序遍历，获取所有的值；

图2：MyISAM 索引分布

图3：MyISAM 索引查找数据原理

2.2 InnoDB索引原理及数据分布

2.2.1 InnoDB聚簇索引和二级索引

聚簇索引不是一种单独的索引类型，而是一种数据存储方式；

InnoDB是采用的 B+Tree 的存储方式，当表有聚簇索引时，非叶子节点存储的是指向下一个节点的指针，而叶子节点存储的是关键字和数据行，即数据行和相邻的键值紧凑地存储在一起；

当表有聚簇索引时，它的数据行实际上存放在索引的叶子页中。通常来说，如果表中有主键的时候，会用主键作为聚簇索引，没有主键，会创建一个虚拟的，不重复的列作为聚簇索引；

图4：InnoDB主键索引分布

从上图可以看到，聚簇索引（主键索引）上不仅包含了完整的数据行，而且包含了事物的指针，用于事物的回退，以及MVCC多版本并发控制；

而InnoDB的二级索引大致分布如下，与聚簇索引差不多，都是B+Tree树，非叶子几点存储的是指向下一个结点指针，叶子节点存储的是关键字和主键值；

图5：InnoDB二级索引分布

2.2.2 InnoDB索引查询原理

这里建立一张数据表，来进行模拟下InnoDB是如何运行的；如下图所示，PID是主键

图6：聚簇索引分布
在建立主键索引的时候，如上图所示，分为上下两部分，上半部分是由主键形成的B+Tree树，非叶子节点存储的是索引指针，而叶子节点存储的是主键和实际数据行（当然还有事物ID等没有画出来）；
下半部分存储的是完整的数据行；

当执行以下的SQL语句时，运行流程为

select * from table where pId='11'

图7：聚簇索引查找流程

而当我们对 ‘name’ 字段建立索引的时候，则生成一棵新的索引树，查询的时候，如下图所示

# name字段建立索引
create index index_name on table(name);

# 执行查询
select * from table where name='lisi'

图8：普通索引查找流程
如上图所示，当我们对name创建索引的时候，会生成一个新的索引树，上部分是B+Tree树，非叶子节点存储的是索引的指针，叶子结点存储的是关键字和主键；
当执行上述SQL的时候，我们可以看到，首先，根据B+Tree树，查出关键字对应的主键值，然后根据主键值，再经过一次B+Tree树查找到了具体的数据行；

这里我们也可以看到为什么不要建立过多的索引：每建立一个索引，都会生成一个B+Tree树，然后每次更新、插入和删除都要去维护相应的索引树，当索引树过多的时候，就会造成性能的低下；

除此之外，细心的童鞋也能发现，上述的查询，执行了两次B+Tree树查询，然而是必然的吗？下面就说下覆盖索引；

2.2.3 覆盖索引

覆盖索引是组合索引的一种，即覆盖索引必是组合索引，而组合索引不一定是覆盖索引；覆盖索引指的是select 中选择的所有字段，以及where 查询中的字段，都在组合索引中，那么就是覆盖索引，explain的时候，extra为using index；优点是避免了回表查询；

这里举个例子，例如我有个数据表，名为test，一共四个字段，a,b,c,d，然后在a,b上建立组合索引；当执行以下的SQL语句的时候：

select a,b,c from table where a=1 and b=2;

因为我们的索引是a,b，查询的时候，我们只能从索引上得到a和b的值，c列的值无法得到，索引需要再根据查询出来的主键，查询下c的值，这样select 列就完整了；

而如果是下面的SQL，我们直接从索引上就能得到select 列上的所有值，就不需要再查一次主键的B+Tree树，就能加快了速度，这便是覆盖索引能够避免回表查询；

select a,b from table where a=1 and b=2;

但是覆盖索引有一些性质，需要记住，否则是无法使用覆盖索引的：
（1） 覆盖索引遵循最左前缀原则
（2）覆盖索引如果跳过其中的某个行，将导致后面的字段无法使用索引
（3）范围查询后面的字段无法使用索引
（4）like全匹配无法使用索引，但是仅右侧的通配符是可以匹配的

因此建立索引时，应该将区分度高的放在左侧，经常范围查询的，放到最右侧；详情《MySQL数据库优化技术大全》

补充：
组合索引遵循最左原则，例如a、b、c三个字段上建立了索引，如果查询条件为

where a = 1 and b > 1 and c = 1;

最终结果，只有a和b字段能够使用索引，而c字段无法使用索引的，这一点，可以通过EXPLAIN SQL语句，看 key_len列，可以知道此次的查询走了几个字段的索引

2.2.4 使用索引来做排序

（1）子句的顺序完全一致，并且所有列的排序方向（倒叙或顺序）都一样时，才能够使用索引来对结果进行排序

（2）索引排序也满足最左前缀的原则，但是可以于where结合组成最左前缀

（3）未使用索引排序的话，explain的时候extra列出现是filesort；

举个例子，在a,b,c上建立了索引

select * from table where a=1 and b=2 order by c

可以看到 extra 列没有出现filesort；因为c与前面的 a,b 组合，符合最左前缀的要求；

而下面的例子，

select * from table where a=1 order by b desc, c asc;

即使 order 列中与 where 组合成最左前缀，也是无法使用索引进行排序，导致extra出现了 filesort，这是因为两者的排序方向不一致导致无法使用索引；

2.2.4 主键优化

通常我们建议建立主键的时候，使用AUTO_INCREMENT自增列作为主键，这样可保证数据行是按照顺序写入，对于根据主键做关联操作的性能也会更好；
在了解原理的时候，先来看一下MySQL在磁盘上的存储，MySQL表中的所有数据被存储在一个空间内，称之为表空间，表空间内部又可以分为段(segment)、区(extent)、页(page)、行(row),逻辑结构如下图：

图9：数据库存储示意图

• 行

  行对应的是表中的行记录，每页存储最多的行记录也是有硬性规定的最多16KB/2-200,即7992行（16KB是页大小，我也不明白为什么要这么算,据说是内核定义）

• 页

  页是InnoDB存储引擎的最小管理单位，每页大小默认是16KB，从InnoDB 1.2.x版本开始，可以利用innodb_page_size来改变页size，但是改变只能在初始化InnoDB实例前进行修改，之后便无法进行修改，除非mysqldump导出创建新库，常见的页类型有：数据页、undo页、系统页、事务数据页、插入缓冲位图页、插入缓冲空闲列表页、未压缩的二进制大对象页、压缩的二进制大对象页。

• 区

  区是由连续页组成的空间，每个区的固定大小为1MB,为保证区中页的连续性，InnoDB会一次从磁盘中申请4~5个区，在默认不压缩的情况下，一个区可以容纳64个连续的页。但是在开始新建表的时候，空表的默认大小为96KB,是由于为了高效的利用磁盘空间，在开始插入数据时表会先利用32个页大小的碎片页来存储数据，当这些碎片使用完后，表大小才会按照MB倍数来增加。

• 段

  表空间是由不同的段组成的，常见的段有：数据段，索引段，回滚段等等，在 MySQL中，数据是按照B+树来存储，因此数据即索引，因此数据段即为B+树的叶子节点，索引段为B+树的非叶子节点,回滚段用于存储undo日志，用于事务失败后数据回滚以及在事务未提交之前通过undo日志获取之前版本的数据，在InnoDB1.1版本之前一个InnoDB,只支持一个回滚段，支持1023个并发修改事务同时进行，在InnoDB1.2版本，将回滚段数量提高到了128个，也就是说可以同时进行128*1023个并发修改事务。

再来看下当我们往表中插入数据的时候索引发生了什么

图10：向聚簇索引插入顺序的索引值
如上图所示，因为主键的值是顺序的，所以，InnoDB把每一条记录都存储在上一条的记录的后面，当达到页的最大填充因子时（InnoDB默认的最大填充因子是页大小的15/16，留出部分空白空间用于以后的修改），下一条记录就会写入到新的页中，一旦数据按照这种方式加载 ，主键页就会近似于被顺序的记录填满，这也是所期望的记过（然而二级索引页可能是不一样的）;

假设我们以随机的数字UUID作为主键，会发生什么呢？因为新行的主键值不一定比之前插入的大，所以InnoDB无法简单的总是把新行插入到索引的最后，而是需要为新的行寻找合适的位置—-通常是已有数据的中间位置，并分配空间。这会增加很多的额外工作，并导致数据分布不够优化。下面是总结的缺点：

• 写入的目标页可能已经刷到磁盘上并从缓存中移除，或者是还没有被加载到缓存中InnoDB在插入之前不得不先找到并从磁盘读取目标页到内存中，这将导致大量的随机I/O
• 因为写入是乱序的，InnoDB不得不频繁地做页分裂操作，以便为新的行分配空间，页分裂会导致移动大量的数据，一次插入至少需要修改三个页而不是一个页。、
• 由于频繁的页分裂，页会变得稀疏并不被规则地填充，所以最终数据会有碎片；

但是顺序主键页不是绝对的

对于高并发的工作负载，在InnoDB中按主键顺序插入可能会造成明显的争用。主键的上界，会成为“热点”。因为所有的插入都发生在这里，所以鬓发插入可能导致间隙锁竞争。另一个热点可能是AUTO_INCREMENT锁机制；如果遇到这个问题，可能需要考虑重新设计表或应用，或者更改innodb_autoinc_lock_mode配置。

三、二叉树和B树（B-Tree）和B+Tree

我们知道，MySQL的InnoDB使用的是B+Tree，而MyISAM使用的是B-Tree，MogoDB使用的也是B-Tree，然而各个结构有什么优缺点呢，因为篇幅有限，这里便不细讲各个各个树插入及删除节点的变化，仅对读取做一个简单的理解；

3.1 二叉树

二叉树具有以下性质，左子树的节点值小于父节点的值，而右节点的值大于父节点的值，如下图所示：

图11：常见二叉树结构
特殊情况下二叉树查找会退化成链表，查询效率低下；

图12：特殊二叉树的值

3.2 B-Tree

B-Tree具有以下的特点：
（1）每个节点最多含有m个孩子；
（2）根节点含有[2,m]个孩子；
（3）非叶子节点含有[[m/2],m]个孩子节点（向上取整的意思）；
（4）一个节点如果含有K个关键字，那么它就有k+1个孩子；
（5）所有叶子节点都在同一层，所有键值分布在整棵树中；
（6）所有节点关键字是按递增次序排列，并遵循左小右大原则

图13：B-Tree索引结构
如上图所示，B-Tree 的非叶子结点上存储关键字信息、指向子结点的指针，以及数据域（数据的存放地址，例如MyISAM的行号）,第一层的p1指向的磁盘块，小于17，p2指向的磁盘块3大于17小于35，而p3指向的磁盘块4大于35，以此原理去寻找相应的数据；

3.3 B+Tree

B+Tree相对于B-Tree有几点不同：
（1）非叶子节点只存储键值信息。
（2）所有叶子节点之间都有一个链指针。
（3）数据记录都存放在叶子节点中。

图14：B+Tree索引结构

B+Tree是在B-Tree基础上的一种优化，更适合作为索引结构，InnoDB就是B+Tree实现的；

从之前的学习中，我们知道，B-Tree中，每个节点中不仅包含数据的key值，还有data值。而每一页的存储空间都是有限的，如果data数据较大时，会导致每页存储的key的数量较少，同样导致B-Tree的深度较大，增大查询时磁盘I/O 次数，进而影响查询效率。

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个结点存储的key值数量，降低B+Tree的高度；
B+Tree和B-Tree有几点不同：
（1）非叶子节点只存储键值信息。
（2）所有叶子节点之间都有一个链指针
（3）数据记录都存放在叶子节点中。

3.4 B+Tree 和B-Tree的区别

（1）B+Tree的层级更少；

相较于B树，B+每个非叶子节点存储的关键字数更多，树的层级更少，且每页存储的关键字更多，所以查询数据更快；

 文件与数据库都是需要较大的存储，也就是说，它们都不可能全部存储在内存中，故需要存储到磁盘上。

为了提升效率，要尽量减少磁盘IO的次数。实际过程中，磁盘并不是每次严格按需读取，而是每次都会预读。磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中，这样做的理论依据是计算机科学中注明的局部性原理： （1）当一个数据被用到时，其附近的数据也通常会马上被使用 （2）程序运行期间所需要的数据通常比较集中

数据库系统巧妙利用了局部性原理与磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，而红黑树这种结构，高度明显要深的多，并且由于逻辑上很近的节点(父子)物理上可能很远，无法利用局部性。最重要的是，B+树还有一个最大的好处：方便扫库。

而所谓索引，则为了数据的快速定位与查找，那么索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数，因此B+树相比B树更为合适。

B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持，这是数据库选用B+树的最主要原因。

（2）B+Tree树查询速度更稳定

B+树所有的关键字数据地址都在叶子节点上，所以每次查找的次数都相同，所以查询速度比B树更稳定；

（3）B+Tree树天然具备排序功能

B+树所有的叶子节点数据都构成一个有序链表，在查询数据时候更方便，数据紧密性很高，缓存的命中率也比B树高

（4）B+树全节点遍历更快

B+Treee遍历整棵树，只需要遍历所有的叶子节点即可，在数据库中基于范围的查询是非常频繁的，而B树要中序遍历，效率低下

（5）B树的优点

经常访问的数据离根节点很近，而B树的非叶子几点本身存有关键字数据地址，所以这种数据检索的时候会比B+树快；