B-Tree
1.核心特点:
- 多路，非二叉树
- 每个节点既保存索引，又保存数据
- 搜索时相当于二分查找
B+Tree
1.核心特点
- 多路非二叉
- 只有叶子节点保存数据
- 搜索时相当于二分查找
- 增加了相邻接点的指向指针。
B-Tree VS B+Tree
1.B+树查询时间复杂度固定是log n，B-树查询复杂度最好是 O(1)。
2.B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
3.B+树更适合外部存储，也就是磁盘存储。由于中间节点无data 域，每个节点能索引的范围更大更精确。
MySQL InnoDB
数据存储:
- 数据结构按照B+树存储，本身就是索引，又叫聚簇索引
- key为主键
- InnoDB要求表必须要有主键
- 若未显示指定，则自动选择唯一标识记录列为主键，若不存在则自动创建
普通索引:
- 叶子节点存放的主键，而不是行的物理地址
- 需要两次检索，（1）检索主键（2）根据主键检索数据
- 存主键好处：页分裂或数据移动时不需要变动
- 主键要设计的尽可能小，原因：每个索引都会存，过大浪费空间
- 主键最好有序，减少索引维护开销
MySQL InnoDB页大小:
SHOW VARIABLES LIKE 'innodb_page_size';
查找关键字=8的数据:
- 根页在表空间中位置固定。
- 根页装入内存，查找到指针P6
- P6指向的页装入内存
- 二分查找找到8
InnoDB中高度为3的B+树存放:
1.假设数据表中一行数据为1K。
2.假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共1占用14字节。
3.一个页中存放指针数目（索引个数）：
4.16KB（16*1024=16384 byte）16384/14=1170
5.高度为2的B+树，能存放1170*16=18720条数据记录。
6.高度为3的B+树，能存放：
7.1170（索引个数）*1170（索引个数）*16（每页行数）=21902400（2千万）条这样的记录
高性能索引策略:
1.独立的列：
1.索引列不能是表达式的一部分，也不能是函数的参数。
2.如：select x ,y,z from table where x+1 = 2;
3.假如x是索引，那上述sql无法利用索引，应写成：select x ,y,z from table where x = 1;
2.索引选择性：不重复的索引个数(X，X<=T)和数据表的记录总数（T）的比值，范围在 X/T 到 1 之间。索引的选择性越高则查询效率越高。唯一索引的X=T，其选择性为1，所以唯一索引的性能最好。
3.前缀索引：
1.对于TEXT或是VARCHAR类型的列，当这个列中的值长度很大又必须利用其进行查询时，就必须使用这个列的前几位值以作索引，即前缀索引，因为整个列的值当做索引时B+tree会占用非常大的空间，查找也不方便。
2.前缀索引的制定原则：前缀索引的选择性需要和整个列的选择性接近，这样性能不会影响太多，同时还不能太长而占用太多空间。
3.如何寻找最佳前缀索引？
1.假设：有一个表中的某一列，名为testcol，类型为varchar(100)
2.计算完整列的选择性: SELECT COUNT(DISTINCT testcol) / COUNT( * ) FROM table;
3.计算前缀长度为x的选择性:SELECT COUNT(DISTINCT LEFT( testcol, x )) / COUNT( * ) FROM table;
4.改变x的值来计算不同前缀的选择性，最后在多个值中，综合考虑选择性接近性和前缀长度的两个方面，可以选出一个较为合适的前缀索引。
4.多列索引
1.select x,y,z from table where x=1 and y=1;
2.在Mysql执行查询时，如果是使用多列索引key(x,y)，则会先查询符合第一列索引的数据集，然后再在这一部分数据集中查询出符合第二列的数据，以此类推，这样在不用扫描数据的情况下就能选出数据；
3.而如果一个多列索引拆分成多个单列索引(key(x),key(y))的话，Mysql在执行查询时，只会从中选出一个限制最严格的索引以供使用，其他的索引就浪费了，所以在上述情况中多列索引性能要好。
5.索引顺序
1.select x,y,z from table where x=1 and y=1;
2.x=1 and y = 1 还是 y=1 and x=1?
3.将选择性高的索引列放在前面；索引列按照选择性从高到低放置
6.覆盖索引
1.如果一个索引包含了所有需要查询的字段的值，就称之为“覆盖索引”
2.InnoDB存储引擎使用聚簇索引，覆盖索引可避免回表查询。因为InnoDB的二级索引的B-Tree的叶结点存储的是对应的一级索引，所以如果二级索引覆盖了所要查询的值则会少一次利用一级索引查询，提升效率。
3.当发起一个索引覆盖查询时，在执行计划的Extra列中可见“Using index”的信息。
7.索引冗余
1.当存在key (a, b)索引时，如果再创建一个key (a)就是多余的，因为它只是多列索引的前缀而已。
2.但是当创建key (b)时，就不属于冗余索引了，因为上述的多列索引是无法单独使用b作索引查询
8.索引相关问题
1.索引越多越好? 数据更新时需要维护索引，带来开销，按需创建。
2.**哪些列适合建索引？**选择性较高的列，一些常量和枚举的字段（如：性别）不适合建索引，选择性较低还增加维护成本，得不偿失。
3.**索引字段类型？**自增字段，表比较大时，uuid等没有规律的字段不太适合作为主键
MySQL执行计划
1.select_type
2.type
3.possible_keys: 可能使用的索引，注意不一定会使用。查询涉及到的字段上若存在索引，则该索引将被列出来。当该列为 NULL时就要考虑当前的SQL是否需要优化了。
4.key
1.显示MySQL在查询中实际使用的索引，若没有使用索引，显示为NULL。
2.TIPS: 查询中若使用了覆盖索引(覆盖索引：索引的数据覆盖了需要查询的所有数据)，则该索引仅出现在key列表中。
3.select_type为index_merge时，这里可能出现两个以上的索引，其他的select_type这里只会出现一个
5.key_length：索引字段长度
1.char()、varchar()索引长度的计算公式：
(Character Set：utf8mb4=4,utf8=3,gbk=2,latin1=1) * 列长度 + 1(允许null) + 2(变长列)
2.int索引长度的计算公式：4+ 1(允许null)
6.extra: extra的信息非常丰富，常见的有：
1.Using index 使用覆盖索引
2.Using where 使用了用where子句来过滤结果集
3.Using filesort 使用文件排序，使用非索引列进行排序时出现，非常消耗性能，尽量优化。
4.Using temporary 使用了临时表。
sql优化建议
1.SQL语句不要写的太复杂：一个SQL语句要尽量简单，不要嵌套太多层。
2.使用『临时表』缓存中间结果：简化SQL语句的重要方法就是采用临时表暂存中间结果，这样可以避免程序中多次扫描主表，也大大减少了阻塞，提高了并发性能。
3.使用like的时候要注意是否会导致全表扫描：有的时候会需要进行一些模糊查询比如select id from table where username like ‘%abc%’。关键词%abc%，由于abc前面用到了“%”，因此该查询会使用全表扫描，除非必要，否则不要在关键词前加%，
4.尽量避免使用 not in,!=或<>操作符：在where语句中使用not in,!=或<>，引擎将放弃使用索引而进行全表扫描。
5.尽量避免使用 or 来连接条件：
1.用 or 分割开的条件， 如果 or 前的条件中的列有索引， 而后面的列中没有索
引， 那么涉及到的索引都不会被用到。
2.应尽量避免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描，如： 假设num1有索引，num2没有索引，查询语句select id from t where num1=10 or num2=20会放弃使用索引，可以改为这样查询： select id from t where num1=10 union all select id from t where num2=20，这样虽然num2没有使用索引，但至少num1会使用索引，提高效率
6.尽量使用数字型字段：若只含数值信息的字段尽量不要设计为字符型，这会降低查询和连接的性能，并会增加存储开销。
7.尽量不要让字段的默认值为NULL：
1.在MySQL中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。
2.索引不会包含有NULL值的列，只要列中包含有NULL值都将不会被包含在索引中，复合索引中只要有一列含有NULL值，那么这一列对于此复合索引就是无效的。
3.所以我们在数据库设计时尽量不要让字段的默认值为NULL，应该指定列为NOT NULL，除非你想存储NULL。你应该用0、一个特殊的值或者一个空串代替空值。
8.如果列类型是字符串，那么一定记得在 where 条件中把字符常量值用引号引起来，否则的话即便这个列上有索引，MySQL 也不会用到的，因为MySQL 默认把输入的常量值进行转换以后才进行检索。如：select * from t_student where std_name = 3;
9.慎用insert into select。
1.语句：insert into tableA select * from tableB where date_time > ‘2020- 07-31’
2.问题分析：该语句会导致tableB逐步被锁定，其他操作无法进行的问题。
3.解决方案：data_time字段添加索引
10.索引null值问题
1.唯一索引null值
1.唯一索引中允许存在多行值为NULL的数据存在
2.2联合唯一索引中存在null值，将丢失唯一性，如unique key(email,phone)，若phone为空将导致email相同的多条记录存在
3.对 NULL 值的检索只能使用 is null / is not null / <=>，不能使用=,<,>这样的运算符
2.普通索引null值：null值存在仍然可以走索引
