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’;