您的位置: 首页  >  文章  >  《深入MySQL》一、MySQL索引原理解析

《深入MySQL》一、MySQL索引原理解析

分类: 文章 • 2024-05-08 08:13:52

索引，是帮助MySQL高效获取数据的一数据结构，也就是说，通过创建索引，我们可以提高查询的效率。索引的本质是一种数据结构。下面让我们慢慢的分析下MySQL的索引实现原理。

一、为什么要用索引

假如我们一张表中有一百万的条数据，执行select * from user where id='1'，在没有创建索引的情况下，将会进行全表扫描。显然是超级不可取的一种方式。因此我们需要对id进行建立索引，提高查询效率。

二、索引分类

1、数据结构-Hash

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。是的，若仅仅执行语句select * from user where id='1'，无疑用Hash查询是超级快的，但是假如我需要查询select * from user where id>'1'，那么由于Hash是根据键值进行访问的，此时是范围查询，就不方便了，将会类似于全表扫描。

 
  1. 优点：查找可以直接根据key访问
  2. 缺点：不支持范围查询

2、数据结构-平衡二叉树

平衡二叉查找树，又称 AVL树。 它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1。 也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。如下图所示：
《深入MySQL》一、MySQL索引原理解析
这里假如查找0010，顺序如下

 
  1. 从硬盘读取0004到内存中，比较0010>0004, 取右子树；
  2. 从硬盘读取0008到内存中，比较0010>0008, 取右子树；
  3. 从硬盘读取0009到内存中，比较0010>0009，取右子树；
  4. 从硬盘读取0010到内存中，比较0010==0010，查询成功；

由上可知，。进行了4次的IO操作。
优点：查询效率较高，
缺点：虽然支持范围查询，但是回旋查询效率较低，插入操作需要进行旋转。并且随着树的深度增加，IO查询次数将会增大。

3、数据结构-B树

维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
《深入MySQL》一、MySQL索引原理解析
这里假如查找0010，顺序如下

 
  1. 从硬盘读取0004到内存中，比较0010>0004, 取右子树；
  2. 从硬盘读取0006和0008到内存中，比较0010>0008, 取右子树；
  3. 从硬盘读取0009和0010到内存中，比较0010>0010, 查询成功；

由上可知。只进行了三次IO操作。因为B树节点元素比平衡二叉树要多，所以B树数据结构相比平衡二叉树数据结构实现减少磁盘IO的操作。

 
  1. 优点：B树查询效率比平衡二叉树效率要高，因为B树的节点中可以有多个元素，从而减少树的高度，减少IO操作，从而提高查询效率。
  2. 缺点：范围查询效率还是比较低。

4、数据结构B+树

通过继承了B树的特征，B+树相比B树，新增叶子节点与非叶子节点关系，叶子节点中包含了key和value，非叶子节点中只是包含了key，不包含value。通过非叶子节点查询叶子节点获取对应的value，所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高。
也就是说，上面的二叉树和B-tree，都是每个节点不仅保存key，而且还保存了value(可能是地址，可能是内容)，但是B+tree非叶子节点只会保存key，只有叶子节点才会保存key和value。
《深入MySQL》一、MySQL索引原理解析
由图可以知道，虽然都是三层IO，但是叶子节点包含了非叶子节点，使用链表进行结合，有一定的顺序排序，所以范围查询效率也是非常高的，不需要一个个做回旋对比。

 
  1. 优点：范围查询效率非常高；
  2. 缺点：因为有冗余的节点数据，所以比较耗内存；

5、小结

有上可知，最终还是会回到了时间和空间的问题，不可能二者兼得，减少了时间就必须多耗费空间，减少了空间的使用，就必须降低查询效率。当然我们知道mysql索引的数据结构是树，常用的存储引擎innodb采用的是B+Tree。MyISAM和InnoDB对B-Tree索引的实现方式是不同的，我们下面来分析下。顺便说一句：有一个很好用的网站可以让我们直观的操作数据结构：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html ，我上面的图就是根据这个画得。

三、MyISAM和InnoDB对B-Tree索引的实现方式

我们先理解两个概念：非聚簇索引和聚簇索引

 
  1. 非聚集索引。表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。非聚簇索引的数据表和索引表是分开存储的。

叶结点包含索引字段值及指向数据页数据行的逻辑指针。

 
  1. 聚集索引。表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。对于聚集索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。

叶子结点即存储了真实的数据行，不再有另外单独的数据页。

MyISAM存储引擎采用的是非聚簇索引，叶子结点的key都存储指向键值对应的数据的物理地址。InnoDB存储引擎采用的是聚簇索引，聚簇索引的数据和主键索引存储在一起。也就是对于B+树来说，非聚集索引，叶子节点只会存储指向数据页数据行的逻辑指针。而聚集索引则存储了真实的数据行，不再有另外单独的数据页。如下人图：
MyISAM非聚集索引

《深入MySQL》一、MySQL索引原理解析

InnoDB聚集索引
《深入MySQL》一、MySQL索引原理解析

通过上面两个图，我们应该很清楚的明白了MyISAM和InnoDB对B-Tree索引的实现方式上的区别。再总结一下：MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

四、MyISAM和innoDB引擎对比

上面是描述了两大引擎实现B+tree上的区别，这里再比较一下这两个引擎。

  MyISAM innoDB
索引类型 非聚簇 聚簇
支持事务 否 是
支持表锁 是 是
支持行锁 否 是（默认）
支持外键 否 是
支持全文索引 是 是（5.6以后支持）
适用操作类型 大量select下使用 大量insert、delete和update下使用

五、MySQL数据库优化方案

Mysql的优化，大体可以分为三部分：索引的优化，sql慢查询的优化，表的优化。

1、索引的优化

1.最左前缀
索引的最左前缀和和B+Tree中的“最左前缀原理”有关，举例来说就是where之后的条件如果设置了组合索引<col1,col2,col3>那么以下3中情况可以使用索引：col1，<col1,col2>，<col1,col2,col3>，其它的列，比如<col2,col3>，<col1,col3>，col2，col3等等都是不能使用索引的。也就是：

 
  1. select * from table where col1="a";
  2. select * from table where col1="a" and col2="b";
  3. select * from table where col1="a" and col2="b" and col3="c";

上面三条语句是可以用到索引的。但是如下三条不遵从最左前缀的,导致索引失效：

 
  1. select * from table where col2="b";
  2. select * from table where col3="c";
  3. select * from table where col2="b" and col3="c";
  4. select * from table where col1="a" and col3="c";

当然前提是<col1,col2,col3>为组合索引。

2.不在索引列上做任何操作,否则会导致索引失效而转向全表扫描
select * from table where left(col1,4)=’a’;

3.存储引擎不能使用索引中范围条件右边的列,范围之后全失效,将导致col1和col2被用到了，col3失效
select * from table where col1=’a’ and col2 >25 and col3=’c’;

4.尽量用覆盖索引(覆盖索引:查询的列和所建立的索引的列个数相同,字段相同),减少select * 的使用

5.尽量不使用!=或<>,如果使用,则无法使用索引,会导致全表扫描

6.is null, is not null无法使用索引

7.带索引的模糊查询优化
like查询,%要在最右侧(‘字符串%’),否则会进行全表扫描,那么如何解决like查询时’%字符串%’时索引不被使用的方法(可以使用覆盖索引)

8.字符串类型不加单引号会导致索引失效,因为mysql会自己做类型转换,相当于在索引列上进行了操作

9.少用or,用它会索引失效

2、sql慢查询的优化

查询优化神器 – explain命令,步骤如下：

 
  1. 先运行看看是否真的很慢，注意设置SQL_NO_CACHE
  2. where条件单表查，锁定最小返回记录表。这句话的意思是把查询语句的where都应用到表中返回的记录数最小的表开始查起，单表每个字段分别查询，看哪个字段的区分度最高
  3. explain查看执行计划，是否与1预期一致（从锁定记录较少的表开始查询）
  4. order by limit 形式的sql语句让排序的表优先查
  5. 了解业务方使用场景
  6. 加索引时参照建索引的几大原则
  7. 观察结果，不符合预期继续从0分析

3、表的优化

当MySQL单表记录数过大时，增删改查性能都会急剧下降，可以参考以下步骤来优化：
单表优化
除非单表数据未来会一直不断上涨，否则不要一开始就考虑拆分，拆分会带来逻辑、部署、运维的各种复杂度，一般以整型值为主的表在千万级以下，字符串为主的表在五百万以下是没有太大问题的。而事实上很多时候MySQL单表的性能依然有不少优化空间，甚至能正常支撑千万级以上的数据量：

1.字段

 
  1. 尽量使用TINYINT、SMALLINT、MEDIUM_INT作为整数类型而非INT，如果非负则加上UNSIGNED
  2. VARCHAR的长度只分配真正需要的空间
  3. 使用枚举或整数代替字符串类型
  4. 尽量使用TIMESTAMP而非DATETIME，
  5. 单表不要有太多字段，建议在20以内
  6. 避免使用NULL字段，很难查询优化且占用额外索引空间
  7. 用整型来存IP

2.索引

 
  1. 索引并不是越多越好，要根据查询有针对性的创建，考虑在WHERE和ORDER BY命令上涉及的列建立索引，可根据EXPLAIN来查看是否用了索引还是全表扫描
  2. 应尽量避免在WHERE子句中对字段进行NULL值判断，否则将导致引擎放弃使用索引而进行全表扫描
  3. 值分布很稀少的字段不适合建索引，例如"性别"这种只有两三个值的字段
  4. 字符字段只建前缀索引
  5. 字符字段最好不要做主键
  6. 不用外键，由程序保证约束
  7. 尽量不用UNIQUE，由程序保证约束
  8. 使用多列索引时主意顺序和查询条件保持一致，同时删除不必要的单列索引

3.查询SQL

 
  1. 可通过开启慢查询日志来找出较慢的SQL
  2. 不做列运算：SELECT id WHERE age + 1 = 10，任何对列的操作都将导致表扫描，它包括数据库教程函数、计算表达式等等，查询时要尽可能将操作移至等号右边
  3. sql语句尽可能简单：一条sql只能在一个cpu运算；大语句拆小语句，减少锁时间；一条大sql可以堵死整个库
  4. 不用SELECT *
  5. OR改写成IN：OR的效率是n级别，IN的效率是log(n)级别，in的个数建议控制在200以内
  6. 不用函数和触发器，在应用程序实现
  7. 避免%xxx式查询
  8. 少用JOIN
  9. 使用同类型进行比较，比如用'123'和'123'比，123和123比
  10. 尽量避免在WHERE子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描
  11. 对于连续数值，使用BETWEEN不用IN：SELECT id FROM t WHERE num BETWEEN 1 AND 5
  12. 列表数据不要拿全表，要使用LIMIT来分页，每页数量也不要太大

4.引擎

 
  1. 总体来讲，MyISAM适合SELECT密集型的表，而InnoDB适合INSERT和UPDATE密集型的表。

当然还有一些参数配置的优化。

六、总结

我们从啥是索引，以及索引的类别和优缺点到MySQL两种引擎实现B+tree不同方式对比，到最后大概说明了下MySQL的优化。基本上对MySQL的索引有了一个大概的认识，以后每一部分还是需要再深入研究了解的。话说又费了两个钟，以后还是要换方法，比如今天学习总结，明天再整理为博文，而不是边学习边整理，太费时间啦。

相关推荐