MySQL索引结构

InnoDB的索引使用B+树 

1.二叉树

时间复杂度O(n),无法随机查找 父节点左子树所有结点的值小于父节点的值, 右子树所有结点的值大于父节点的值

2.平衡二叉树

时间复杂度O(logN) 树高度越高,访问代价越高

3.B树

平衡二叉树的基础上减少高度 时间复杂度O(logN) 叶子节点存储数据,查找会读取过多无用的data

B 树的特性:(m 为阶数:结点的孩子个数最大值)

1. 树中每个节点最多含有 m 个孩子节点 (m>=2);

2. 除根节点和叶子结点外,其他节点的孩子数量 >=ceil(m / 2);

3. 若根节点不是叶子结点,最少有两个孩子 

4.B+树

  • 非叶子节点只保留 KEY,放弃 DATA;
  • KEY 和 DATA一起,在叶子节点,并且保存为一个有序链表(正序,反序,或者双向);
  • B+ 树的查找与 B 树不同,当某个结点的 KEY 与所查的 KEY 相等时,并不停止查找,而是沿着这个 KEY 左边的指针向下,一直查到该关键字所在的叶子结点为止。(观看树变化https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html )

MySQL索引结构

聚集索引:也称 Clustered Index。是指关系表记录的物理顺序与索引的逻辑顺序相同。由于一张表只能按照一种物理顺序存放,一张表最多也只能存在一个聚集索引。与非聚集索引相比,聚集索引有着更快的检索速度。 MySQL 里只有 INNODB 表支持聚集索引,INNODB 表数据本身就是聚集索引,也就是常说 IOT,索引组织表。非叶子节点按照主键顺序存放,叶子节点存放主键以及对应的行记录。所以对 INNODB 表进行全表顺序扫描会非常快。

非聚集索引:也叫 Secondary Index。指的是非叶子节点按照索引的键值顺序存放,叶子节点存放索引键值以及对应的主键键值。MySQL 里除了 INNODB 表主键外,其他的都是二级索引。MYISAM,memory 等引擎的表索引都是非聚集索引。简单点说,就是索引与行数据分开存储。一张表可以有多个二级索引。  

主键索引结构 

辅助索引结构 

数据查找 

聚集索引查找

根据索引进行查找id=50的记录,如下图,沿着B+树一直往下寻找,最终找到第四页**,然后把该页加载到buffer pool中,在缓存中遍历对比查找**,由于里面的行记录是顺序组织的,所以很快就可以定位到记录了。

聚集索引注意事项:

  • 当在表上面定义了PRIMARY KEY之后,InnoDB会把它作为聚集索引。为此,为你的每个表定义一个PRIMARY KEY。如果没有唯一并且非空的字段或者一组列,那么请添加一个自增列;
  • 如果您没有为表定义PRIMARY KEY,则MySQL会找到第一个不带null值的UNIQUE索引,并其用作聚集索引;
  • 如果表没有PRIMARY KEY或没有合适的UNIQUE索引,则InnoDB 内部会生成一个隐藏的聚集索引GEN_CLUST_INDEX,作为行ID,行ID是一个6字节的字段,随着数据的插入而自增。

 

如何建立合适的索引 

  • 选择性好的字段才考虑加索引 Cardinality高的,即唯一值多,数据过滤性好,选择性更高
  • 选择合适的字段顺序 最左前缀原则,选择性高的字段放最前面 B+ 树的数据项是复合的数据结构,比如 (aa,bb) 的时候,B+ 树是按照从左到右的顺序来建立搜索树的
  • 覆盖索引 alter table xx add key idx_xxx(col_1,col_2);
  • innoDB辅助索引会保留字段的值,查询不用在回表。因此也不能随便使用select * 即执行计划里面的Extra:Using Index 创建索引后对数据变更也会有额外开销,不能盲目全覆盖
  • 排序相关 order by 会导致排序,只有顺序跟索引顺序一致,才能使用
  • 多表关联的数据类型一致,统一字符集,且相关列上有索引
  • varchar类型建议指定宽度 根据文本区分度决定索引长度
      • innodb_large_prefix=0  767bytes
      • innodb_large_prefix=1  3072bytes
  • 索引不是越多越好 额外的索引维护成本、页分裂 

为何走错/不走索引

1.索引选择性太差

索引选择性好坏,与索引(Cardinality)的基数有关联 Cardinality是由索引中唯一值计算的一个预估值。索引基数值的准确程度直接影响到 MySQL 优化器基于此索引的查询计划是否准确高效

2.统计信息不准确

MySQL 5.6开始执行计划基于CBO(cost based optimizor),统计信息错误会导致执行计划选择错误 alanyze、optimize  table重新收集

3.隐式转换

表结构中的字段类型跟查询传入的不一致,常见的varchar类型字段查询传入数值类型

4.函数

字段上使用函数会导致无法使用索引

5.如何排查

索引信息+SQL中加入hint force index(xxx) + profile 查看开销 8.0.12开始explain format=extended ,show warnings; 或者set optimizer_trace=’enabled=ON’; 


关于作者

不羁的风
一起哈皮YQHP
获得点赞
文章被阅读