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