一、索引
在MySQL中，主要有四种类型的索引，分别为：B-Tree索引，Hash索引，Fulltext索引(MyISAM 表)和R-Tree索引
Mysql索引主要有两种结构：B+Tree索引和Hash索引
(a) Inodb存储引擎 默认是 B+Tree索引
(b) MyISAM 存储引擎 默认是Fulltext索引；
(c)Memory 存储引擎 默认 Hash索引；
Hash索引
mysql中，只有Memory(Memory表只存在内存中，断电会消失，适用于临时表)存储引擎显示支持Hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。Hash索引把数据以hash形式组织起来，因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能。
b+树索引
B+Tree是mysql使用最频繁的一个索引数据结构，是Inodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎。毕竟不可能只对数据库进行单条记录的操作。
带顺序访问指针的B+Tree
B+Tree所有索引数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。
这样做是为了提高区间效率，例如查询key为从18到49的所有数据记录，当找到18后，只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点，极大提高了区间查询效率。
大大减少磁盘I/O读取
数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点需要一次I/O就可以完全载入。
为什么不用红黑树和平衡二叉树
索引是存在于索引文件中，是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。
注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。
而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。
红黑树没能充分利用磁盘预读功能
红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
也就是说，使用红黑树（平衡二叉树）结构的话，每次磁盘预读中的很多数据是用不上的数据。因此，它没能利用好磁盘预读的提供的数据。然后又由于深度大（较B树而言），所以进行的磁盘IO操作更多。
B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字，树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少，更多的是在内存中对读取进来的数据进行查找。
B树的查询，主要发生在内存中，而平衡二叉树的查询，则是发生在磁盘读取中。因此，虽然B树查询查询的次数不比平衡二叉树的次数少，但是相比起磁盘IO速度，内存中比较的耗时就可以忽略不计了。因此，B树更适合作为索引。
B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。
数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。
B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
跳表
https://www.cnblogs.com/lfri/p/9991925.html
https://zhuanlan.zhihu.com/p/68516038
LSM树
https://zhuanlan.zhihu.com/p/181498475
https://www.jianshu.com/p/5c846e205f5f
InnoDB使用了B+树索引模型，
假设k上加了索引
基于主键索引和普通索引的查询有什么区别？
如果语句是select *fromT where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；
如果语句是select *fromT where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID
的值为500，再到ID索引树搜索一次。这个过程称为回表。
由于查询结果所需要的数据只在主键索引上有，所以不得不回表。那么，有没有
可能经过索引优化，避免回表过程呢？
二、锁
全局锁
顾名思义，全局锁就是对整个数据库实例加锁。MySQL提供了一个加全局读锁的方法，命令是
Flush tables with read lock (FTWRL)。当你需要让整个库处于只读状态的时候，可以使用这个命
令，之后其他线程的以下语句会被阻塞：数据更新语句（数据的增删改）、数据定义语句（包括
建表、修改表结构等）和更新类事务的提交语句。
全局锁的典型使用场景是，做全库逻辑备份。也就是把整库每个表都select出来存成文本。
注意，在备份过程中整个库完全处于只读状态。
如果你在主库上备份，那么在备份期间都不能执行更新，业务基本上就得停摆；
如果你在从库上备份，那么备份期间从库不能执行主库同步过来的binlog，会导致主从延迟。
set global readonly=true 也可以只读
但有两个原因：
一是，在有些系统中，readonly的值会被用来做其他逻辑，比如用来判断一个库是主库还是备
库。因此，修改global变量的方式影响面更大，我不建议你使用。
二是，在异常处理机制上有差异。如果执行FTWRL命令之后由于客户端发生异常断开，那么
MySQL会自动释放这个全局锁，整个库回到可以正常更新的状态。而将整个库设置为
readonly之后，如果客户端发生异常，则数据库就会一直保持readonly状态，这样会导致整个
库长时间处于不可写状态，风险较高。
表锁
MySQL里面表级别的锁有两种：一种是表锁，一种是元数据锁（meta data lock，MDL)。
表锁的语法是 lock tables …read/write。与FTWRL类似，可以用unlock tables主动释放锁，
也可以在客户端断开的时候自动释放。需要注意，lock tables语法除了会限制别的线程的读写
外，也限定了本线程接下来的操作对象
另一类表级的锁是MDL（metadata lock)。MDL不需要显式使用，在访问一个表的时候会被
自动加上。MDL的作用是，保证读写的正确性。你可以想象一下，如果一个查询正在遍历一个
表中的数据，而执行期间另一个线程对这个表结构做变更，删了一列，那么查询线程拿到的结果
跟表结构对不上，肯定是不行的。
因此，在MySQL 5.5版本中引入了MDL，当对一个表做增删改查操作的时候，加MDL读锁；当
要对表做结构变更操作的时候，加MDL写锁。
所有对表的增删改查操作都需要先申请MDL读锁
行锁
行锁就是针对数据表中行记录的锁。这很好理解，比如事务A更新了一行，而这时候
事务B也要更新同一行，则必须等事务A的操作完成后才能进行更新。
MySQL的行锁是在引擎层由各个引擎自己实现的。但并不是所有的引擎都支持行锁，比如
MyISAM引擎就不支持行锁。不支持行锁意味着并发控制只能使用表锁，对于这种引擎的表，同
一张表上任何时刻只能有一个更新在执行，这就会影响到业务并发度。InnoDB是支持行锁的，
这也是MyISAM被InnoDB替代的重要原因之一。
在InnoDB事务中，行锁是在需要的时候才加上的，但并不是不需要了就立刻释放，而是要等到事务结束时才释放。这个就是两阶段锁协议。
所以如果你的事务中需要锁多个行，要把最可能造成锁冲突、最可能影响并发度的锁尽量往后放。
gap lock 间隙锁
为了解决幻读问题，InnoDB引入了间隙锁，锁的就是两个值之间的空隙
CREATE TABLE `t` (
`id` int(11) NOT NULL,
`c` int(11) DEFAULT NULL,
`d` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `c` (`c`)
) ENGINE=InnoDB;
insert into t values(0,0,0),(5,5,5),
(10,10,10),(15,15,15),(20,20,20),(25,25,25);
当执行select * from t where d=5 for update的时候，就不止是给数据库中已有的6个记录加上了行锁，还同时加了7个间隙锁。这样就确保了无法再插入新的记录
间隙锁和行锁合称next-key lock，每个next-key lock是前开后闭区间。表t初始化以后，如果用select * from t for update要把整个表所有记录锁起来，就形成了7个next-key lock分别是(-∞,0]、(0,5]、(5,10]、(10,15]、(15,20]、(20, 25]、(25, +supremum]。因为+∞是开区间，在实现上，InnoDB给每个索引加了一个不存在的最大值supremum，这样才符合都是前开后闭区间
但引入了间隙锁会导致一些困扰：
间隙锁的引入可能会导致同样的语句锁住更大的范围，这其实是影响并发度的
在读提交隔离级别下，不存在间隙锁
next-key lock
CREATE TABLE `t` (
`id` int(11) NOT NULL,
`c` int(11) DEFAULT NULL,
`d` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `c` (`c`)
) ENGINE=InnoDB;
insert into t values(0,0,0),(5,5,5),
(10,10,10),(15,15,15),(20,20,20),(25,25,25);
原则1：加锁的基本单位是next-key lock，next-key lock是前开后闭区间
原则2：查找过程中访问到的对象才会加锁
优化1：索引上的等值查询，给唯一索引加锁的时候，next-key lock退化为行锁
优化2：索引上的等值查询，向右遍历时且最后一个值不满足等值条件的时候，next-key lock退化为间隙锁
一个bug：唯一索引上的范围查询会访问到不满足条件的第一个值为止
