二叉树结构
每个节点至多有两个子节点，二叉树子树有左右序之分，在二叉树中：左子树的值<根键值<右子树的值
平衡二叉树结构
条件：左右两个子树的高度差不超过1
左子树和右子树都是平衡二叉树
一旦是不平衡的
左旋：
右旋：
https://blog.csdn.net/weixin_43855206/article/details/104846326
B-Tree结构（BTree结构）
B树的结构是一个节点可以拥有多于两个子节点的多叉查找树
上图的B书结构是一颗4阶的B树结构
每个节点中最多含有4个子节点，除了根节点和叶子节点，其他节点至少有2个子节点。
B+Tree（双向链表结构）
是BTree的一种变体：
1.所有关键字的信息都出现在叶子节点当中，并且包含关键字记录的指针，叶子节点按照关键字的大小顺序连接
2.所有数据都保存在叶子节点当中
3.关键字的顺序是连续性的，不用再访问上一个结点
聚集索引和普通索引
B+Tree可以分为两大类：一类是聚集索引；一类是非聚集索引。
InnoDB存储引擎是索引组织表
聚集索引----------->是一种索引组织形式
索引键值的逻辑顺序决定了表数据行的物理存储顺序
聚集索引----------->叶子节点存放表中所有行数据记录的信息，数据即索引，索引即数据。
创建表时，要显式的创建一个主键（聚集索引）；如果不主动创建主键，InnoDB会选择第一个不包含有NULL值的唯一索引作为主键，如果连唯一索引都没有，InnoDB就会为该表默认生成一个6字节的rowid作为主键
普通索引------->在叶子节点并不包含所有行的数据信息，只是会在叶子结点存有自己本身的键值和主键的值，但是没有数据。在检索数据的时候，通过普通索引叶子结点上的主键来获取到想要查找的行数据记录。
创建语句：
ICP、MRR、BKA
1.ICP是MySQL使用索引从表中检索数据的一种优化方式
如果where条件可以使用索引，MySQL会把这部分过滤操作放到存储引擎层，存储引擎通过索引过滤，把满足行从表中读取出。
目的：ICP减少了引擎层访问基表的次数和sever层访问存储引擎的次数。
set optimizer_switch="index_condition_pushdown=on|off"
2.MRR
默认值是自行判断，选择off强制开启
mrr=on,mrr_cost_based=on
set global optimizer_switch='mrr=on|off,mrr_cost_based=on|off'
作用：把普通索引的叶子节点上找到的主键值的集合存储到read_rnd_buffer中，然后在该buffer中对主键值进行排序，最后再利用已经排序好的主键的集合，去访问表中的数据，这样就由原来的随机IO变成了顺序IO，降低了查询过程中IO的开销
3.BKA：Batched Key Access
作用：提高表join性能的算法，作用是在读取被join表的记录的时候使用顺序IO
原理：
1.对于多表join语句，当MySQL使用索引访问第二个join表时，使用一个join buffer来收集第一个操作对象生成的相关列值。
2.BKA构建好key后，批量传给引擎层做索引查找，key是通过MRR接口提交给引擎的，这样一来MRR使得查询更加高效
通过batched_key_access的选项来控制（默认关闭off）
要使用BKA必须是在强制使用MRR的基础上才能实现
set global optimizer_switch='mrr=on,mrr_cost_based=off'
set global optimizer_switch='batched_key_access=on'
MRR和BKA之间的关系：
主键索引和唯一索引
1.主键就是聚集索引，每张表中有且仅有一个主键。
主键要满足三个条件：（1）主键值必须唯一（2）不能包含null值（3）一定要保证该值是自增属性------->提高存取效率
创建主键的语法：
alter table table_name add primary key(column)
创建唯一索引的语法：
alter table table_name add unique(column)
覆盖索引
MySQL只需要通过索引就可以返回查询所需要的数据，不必在查到索引之后再回表查询数据
普通索引中包含主键的值，相当于（name,id）索引
explain select id from t where name='name11'
前缀索引
这类索引主要是对于 BLOB，TEXT这些类型的，或者很长的VARCHAR类型的列，为他们的前几个字符建立索引----->前缀索引
缺点：
1.不能在order by中使用
2.不能在group by中使用
3.不能作为覆盖索引
联合索引
创建联合索引语法：create index idx_c1_c2 on t(c1,c2)
一定要满足的原则：必须要满足最左前缀原则，一般把选择性高的列放在前面。一条查询语句可以只使用索引的一部分，但是必须从最左侧开始。
哈希索引
1.采用哈希算法，把键值换算成新的哈希值，哈希值只能进行等值查询，不能进行排序，模糊查找，范围查询等等。
2.检索的时候，不需要像B+tree那样从根节点到叶子节点逐级查找，只需要一次哈希算法就可以定位到相应的位置。
例子：
select * from zs where city_id=100;
总结：
索引的优点：
（1）提高数据检索效率
（2）提高聚合函数效率
（3）提高排序效率
（4）使用覆盖索引可以避免回表
索引创建四不要：
（1）选择性低的字段不要创建索引（比如性别之类的）
（2）很少查询的列不要创建索引
（3）大数据类型的字段不要创建索引
（4）尽量避免不要使用NULL，应该指定列为NOT NULL
使用不到索引的情况：https://blog.csdn.net/liuxiang87/category_6517816.html
（1）通过索引扫描的记录数超过30%，优化器就不会走索引，而是变成全表的扫描
（2）联合索引中，第一个查询条件不是最左索引列
（3）联合索引中，第一个索引列使用范围查询，只能使用到部分索引，有ICP出现
（4）联合索引中，第一个查询条件不是最左前缀列
（5）模糊查询条件列------>最左以通配符%开始
（6）两个单列索引，一个用于检索；一个用于排序。可以建立联合索引
（7）查询字段上面有索引，但是使用了函数运算
查看索引的方式
使用show index from table_name来查看表中有哪些索引
主要操作流程如下：
（1）desc t
（2）select count（） from t
（3）explain select * from t where name='name11'
*针对explain命令生成的执行计划，查看的一般流程：
（1）type 类型，如果是all关键字，代表全表扫描**，后面的内容可以不用看了。
（2）再看key列，是否使用了索引，null表示没有使用
（3）再看row列，用来表示在SQL执行过程中被扫描的行数，数值越大表示扫描的行数越多，耗时就更长
（4）再看extra列，观察有没有filesort或者temporary出现，这些对性能影响比较大
优化SQL语句的正确思路：
（1）先看表的数据结构是否设计的合理，有没有遵守选取数据类型越简单越小的原则
（2）表中的碎片是否整理
（3）表的统计信息是否收集，只有统计信息尊去，执行计划才可以帮助我们优化SQL
（4）查看执行计划，检查索引的使用情况，没有用到索引，考虑创建
（5）在创建索引之前，还要看索引的选择性，来判断这个字段是否合适创建索引
（6）创建索引之后，再看一下执行计划，对比两次结果，看是否查询效率提高了
三个经常
1.经常被查询的列
2.经常用于表连接的列
3.经常排序分组的列
流程如下：
1.select count(distinct name)/ count(*) from t;
2.create index idx_name on t(name)
京公网安备 11010502036488号