参考：https://www.zhihu.com/question/26113830
B+ 树索引
索引就是一个数据结构，我们把表中的记录用一个适合高效查找的数据结构来表示，目的就是让查询变得更高效；
在mysql中使用最广泛的数据引擎是InnoDB 引擎，它里面用的是 B+ 树索引；
二叉查找树：
每个节点左边节点的值都小于该节点，右边节点的值都大于该节点，没有值相等的节点；
平衡二叉树：
首先也是一个二叉树，需要满足二叉树的所有条件，然后有所改进，规定了左右子树的高度差不能超过1，如果插入数据导致高度差超过了1则自动进行调整，回复到平衡状态；
B树：
B+树：
聚集索引和非聚集索引：
DB查询过程
默认方式:根据搜索条件进行全表扫描，遇到匹配条件的就加入搜索结果集合。
数据库存储结构:页->记录存在页里
1.各个数据页组成一个双向链表。
2.每页中的记录组成一个单向链表。
3.每页都会为存储在它里边儿的记录生成一个页目录:在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录;非主键作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录；
加索引后：
如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的行数，所以能明显增加查询的速度。
区别：
-无索引->遍历
-有索引->直接定位；（通过目录（索引）就可以很快地定位到对应的页上）
优点：
-唯一性：通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
-速度：加快数据的检索速度，这也是创建索引的最主要的原因。
缺点:
-创建：创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
-空间：索引需要占物理空间，如果建立聚簇索引，那么需要的空间就会更大。
-动态维护：对表中数据进行增删改时，索引也要动态的维护->降低了数据维护速度
简单总结：
（1）索引可以加快数据库的检索速度。
（2）索引会降低插入，删除，修改的速度。
（3）索引需要占用物理和数据空间。
（4）索引的最左匹配原则。
（5）索引的分类：聚集索引和非聚集索引。
（6）MySQL支持Hash索引（MEMORY引擎）和B+树索引。
添加索引原则
应该加：
（1）在经常需要搜索的列上，可以加快搜索的速度；
（2）在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；
（3）在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；
（4）在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，范围是连续的；
（5）在经常需要排序的列上创建索引，可以利用索引的排序，加快排序查询时间；
（6）在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。
不应该加：
（1）对于那些在查询中很少使用或者参考的列不应该创建索引。
（2）对于那些取值很少的列（如性别）也不应该增加索引。
（3）对于那些定义为text, image和bit数据类型的列（数据量大，取值少）不应该增加索引。
（4）当修改性能远远大于检索性能时，不应该创建索引。
这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。
哈希索引
参考：https://baijiahao.baidu.com/s?id=1647079867833965110&wfr=spider&for=pc
为什么不用Hash索引而使用B+树索引
1.（范围）Hash索引仅仅能满足"=","IN"查询，不能使用范围查询,因为经过相应的Hash算法处理之后的Hash值的大小关系，并不能保证和Hash运算前完全一样；
2.（排序）Hash索引无法被用来避免数据的排序操作，因为Hash值的大小关系并不一定和Hash运算前的键值完全一样；
3.（组合）Hash索引不能利用部分索引键查询，对于组合索引，Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，而不是单独计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用；
- 哈希索引也不支持多列联合索引的最左匹配规则；
5.（冲突,扫表） Hash索引在任何时候都不能避免表扫描，由于不同索引键存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要回表查询数据； - Hash索引遇到大量Hash值相等的情况后性能并不一定就会比B+树索引高。
索引失效
1、like 以%开头，索引无效；当like前缀没有%，后缀有%时，索引有效
2、当or左右查询字段只有一个是索引，该索引失效，只有当or左右查询字段均为索引时，才会生效
3、组合索引，不是使用第一列索引，索引失效（最左匹配原则）
4、数据类型出现隐式转化。如varchar不加单引号的话可能会自动转换为int型，使索引无效，产生全表扫描
数据库事务及4个特性
事务：由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元；
意义：通过将一组相关操作组合为一个要么全部成功要么全部失败的单元->简化错误恢复并使应用程序更加可靠；
4个特性：
1）原子性：事务包含的所有操作不可分割，要么全部成功，要么全部失败回滚
2）一致性：事务执行前后都保持一致性状态（例如：假设用户A和用户B两者的钱加起来一共是5000，那么不管A和B之间如何转账，转几次账，事务结束后两个用户的钱相加起来应该还得是5000）
3）隔离性：一个事务所做的修改在最终提交前，对其他事务可不见，多个并发事务互不影响
4）持久性：一旦事务提交，则其所做修改将会永远保存到数据库中
事务的隔离级别
未提交读Read Uncommitted：最低的隔离级别，什么都不需要做，一个事务可以读到另一个事务未提交的结果。所有的并发事务问题都会发生。存在“脏读”
Read Committed（读取提交内容）：只有在事务提交后，其更新结果才会被其他事务看见。可以解决脏读问题。
Repeated Read（可重复读）：在一个事务中，对于同一份数据的读取结果总是相同的，无论是否有其他事务对这份数据进行操作，以及这个事务是否提交。可以解决脏读、不可重复读。
Serialization（可串行化）：事务串行化执行，隔离级别最高，牺牲了系统的并发性。可以解决并发事务的所有问题。
mysql存储引擎
MySQL存储引擎最常用：InnoDB、Mylsam、Memory
- InnoDB：支持事务、行级锁、甚至间隙锁（避免幻读）、支持热备份，MVCC，在并发上占优势，系统资源占用多
- MyISAM：默认的存储引擎，不支持事务和行级锁，只支持表锁，某些场景性能很好：占用存储上优，查询速度上完胜（大概是InnoDB的3倍）系统资源占用少，独立于操作系统
- MEMORY引擎：支持哈希索引
1、InnoDB
事务型的存储引擎，有行级锁定和外键约束；提供了对数据库ACID事务的支持；实现了SQL标准的四种隔离级别；使用聚簇索引；
- 设计目标：处理大容量数据库系统（MySQL运行时Innodb会在内存中建立缓冲池，用于缓冲数据和索引）
- 锁：行级锁（粒度小），写操作不会锁定全表，在并发较高时，会提升效率（例外：执行SQL语句时，MySQL不确定要扫描的范围，InnoDB表同样会锁全表）
- 适用场景：
经常更新的表，适合处理多重并发的更新请求。
支持事务。
可以从灾难中恢复（通过bin-log日志等）。
外键约束。
支持自动增加列属性auto_increment。 - 索引结构：
使用聚簇索引（B+树实现）
2、Mylsam
- 适用场景：
不支持外键的表设计。
强调快速读取操作。
存储了表的行数，于是SELECT COUNT(*) FROM TABLE时只需要直接读取已经保存好的值而不需要进行全表扫描。 - 缺点：就是不能在表损坏后主动恢复数据。
- 索引结构：非聚簇索引（B+树）
3、InnoDB和Mylsam的区别：
1）事务：InnoDB类型支持事务及外部键等高级数据库功能；MyISAM类型不支持；
2）性能：MyISAM类型的表强调的是性能，其执行速度比InnoDB类型更快。
3）行数保存：InnoDB 中不保存表的具体行数，也就是说，执行select count() from table时，InnoDB要扫描一遍整个表来计算有多少行，但是MyISAM只要简单的读出保存好的行数即可。注意的是，当count()语句包含where条件时，两种表的操作是一样的。
4）外键：InnoDB支持外键，MyISAM不支持外键；
5）索引存储：对于AUTO_INCREMENT类型的字段，InnoDB中必须包含只有该字段的索引，但是在MyISAM表中，可以和其他字段一起建立联合索引。MyISAM支持全文索引（FULLTEXT）、压缩索引，InnoDB不支持。
MyISAM的索引和数据是分开的，并且索引是有压缩的，内存使用率就对应提高了不少。能加载更多索引，而Innodb是索引和数据是紧密捆绑的，没有使用压缩从而会造成Innodb比MyISAM体积庞大不小。
InnoDB存储引擎被完全与MySQL服务器整合，InnoDB存储引擎为在主内存中缓存数据和索引而维持它自己的缓冲池。InnoDB存储它的表＆索引在一个表空间中，表空间可以包含数个文件（或原始磁盘分区）。这与MyISAM表不同，比如在MyISAM表中每个表被存在分离的文件中。InnoDB 表可以是任何尺寸，即使在文件尺寸被限制为2GB的操作系统上。
InnoDB和MyISAM都支持B+树索引，InnoDB还支持自适应哈希索引；
6）锁的支持：InnoDB支持行级锁、表锁；MyISAM只支持表锁；但是InnoDB的行锁，只是在WHERE的主键是有效的，非主键的WHERE都会锁全表的。
7）存储空间：MyISAM实现了前缀压缩技术，占用存储空间更小（但会影响查找），InnoDB是原始数据存储，占用存储更大。
锁及粒度
- 共享锁/读锁：互不阻塞，优先级低
- 排他锁/写锁：阻塞其他锁，优先级高，即确保在一个事务写入时不受其他事务的影响。
- 锁粒度：锁定的数据量越少（粒度越小），并发程度越高，但相应的加锁、检测锁、释放锁用的系统开销也随之增大。
- 锁策略：锁开销与数据安全性之间的平衡
表锁：锁住整张表，读锁互不阻塞，写锁阻塞其他所有读写锁（相同表）。开销小。
行级锁：对每一行数据（记录）加锁，开销大，并发程度高。 - InnoDB对死锁的处理：多个事务互相持有对方所有要申请资源的锁不释放，造成环路死锁。 InnoDB引擎检测到死锁循环依赖后，回滚持有最少行级锁的事务。
sql优化
- 在经常性的检索列上，建立必要索引，以加快搜索速率，避免全表扫描（索引覆盖扫描）
- 多次查询同样的数据，可以考虑缓存该组数据
- 切分查询（大查询切分成为小查询，避免一次性锁住大量数据）
- 分解关联查询（单表查询，结果在应用程序中进行关联，可以减少处理过程中的锁争用）
参考资料：
https://www.cnblogs.com/wenxiaofei/p/9853682.html 汇总
https://blog.csdn.net/a_helloword/article/details/81592317 索引
