多版本并发控制

mysql的大多数事务型存储引擎实现的都不是简单的行级锁。基于提升并发性能的考虑，它们一般都同时实现了多版本并发控制。

可以认为MVCC是行级锁的一种变种，但是它很多情况下避免了加锁操作，因为开销更低。

InnoDB的MVCC，是通过在每行记录最后保存的两个隐藏的列来实现，这两个列，一个保存了行的创建时间，一个保存行的过期时间（或删除时间），当然存储的并不是实际的时间值，而是系统版本好。每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来查询到的每行版本号进行比较。

REPEATABLE READ隔离级别下，MVCC的实现：

• SELECT

• InnoDB之查找版本早于当前事务版本号的数据行，这样可以确保事务读取的行，要么是在事务开始前已经存在，要么是事务自身插入或者修改过的。

• 行的删除版本要么未定义，要么大于当前事务版本号，这可以确保事务读取到的行在事务开始之前未被删除。

• INSERT

• InnoDB为新插入的每一行保存当前系统版本号作为行版本号。

• DELETE

• InnoDB为删除的每一行保存当前系统版本号作为行删除标识。

• UPDATE

• InnoDB为插入一航新记录，保存当前系统版本号作为行版本号，同时保存当前系统版本号到原来的行作为行删除版本号。

MVCC只在REPEATABLE READ跟READ COMMITED两个隔离级别工作。其他两个隔离级别都和MVCC不兼容。因为READ UNCOMMITED总是读取最新的数据行，而不是符合当前事务版本的数据行。而SERIALIZABLE则会对所有读取的数据的行都加锁。

存储引擎

InnoDB存储引擎

InnoDB是MYSQL的默认事务型引擎，也是最重要、使用最广泛的存储引擎。除非有非常特别的原因需要使用其他的存储引擎，否则应该优先考虑InnoDB引擎。

InnoDB采用MVCC来支持高并发，并且实现了四个标准的隔离级别。默认级别是REPEATABLE READ（可重复读），并且通过间隙锁+MVCC策略防止幻读的实现，间隙锁使得InnoDB不仅仅锁定查询设计的行，还会对索引中的间隙进行锁定，以防止幻影行的插入。

间隙锁：当我们用范围条件而不是相等条件检索数据，并请求共享或排他锁时，InnoDB会给符合条件的已有数据记录的索引项加锁；对于键值在条件范围内但并不存在的记录，叫做“间隙（GAP)”，InnoDB也会对这个“间隙”加锁，这种锁机制就是所谓的间隙锁（Next-Key锁）。
参考：间隙锁（Next-Key锁）

主索引是聚簇索引，在索引中保存了数据，从而避免直接读取磁盘，因此对查询性能有很大的提升。

InnoDB内部做了很多优化，包括从磁盘读取数据时采用的可预测性预读，能够自动在内存中创建hash索引以加速度操作的自适应哈希索引，以及能够加速插入操作的插入缓冲区等。

MyISAM存储引擎

在mysql5.1以及之前的版本，MyISAM是默认的存储引擎。MyISAM提供了大量的特性，包括全文索引、压缩、空间函数等，但是不支持事务和行级锁，而且有一个毫无疑问的缺陷是崩溃之后无法安全恢复。

对于只读的数据、或者表比较小、可以忍受修复操作，则依然可以使用MyISAM引擎。

创建MyISAM表的时候，如果指定了DELAY_KEY_WRITE选项，在每次修改执行完成时，不会立刻将修改的索引数据写入磁盘，而是会写到内存中的键缓冲区，只有在清理键缓冲区或者关闭表的时候才会将对应的索引块写入到磁盘。这种方式可以极大地提升写入性能，但是在数据库或者主机崩溃时会造成索引损坏，需要执行修复操作。

比较

• 事务：InnoDB支持事务，MyISAM不支持事务。

• 锁粒度：InnoDB支持表级锁跟行级锁，而MyISAM只支持表级锁。

• 外键：InnoDB支持外键。

• 备份：InnoDB支持热备份，但需要工具。

• 崩溃恢复：MyISAM崩溃后发生损坏的概率比InnoDB高很多，而且恢复的速度也比较慢。

• 其他特性：MyISAM支持全文索引、压缩、空间函数等特性。

备份的类型

• 冷备（cold backup）：需要关mysql服务，读写请求均不允许状态下进行；

• 温备（warm backup）： 服务在线，但仅支持读请求，不允许写请求；

• 热备（hot backup）：备份的同时，业务不受影响。

索引

索引（也叫做“键(key)”）是存储引擎用于快速查找记录中的一种数据结构。

B-Tree索引

大多数mysql引擎都支持这种索引。

虽然使用术语“B-Tree"，但是不同的存储引擎可能使用不同的存储结构，NDB集群存储引擎内部实际用的是T-Tree，InnoDB则使用B+Tree。

B-Tree索引能够加快访问数据的速度，因为存储引擎不需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始搜索，因此查找速度会快很多。

B-Tree对索引列是顺序组织存储的，很适合查找范围数据。因为索引树是有序的，所以除了用户查找，还可以用来排序和分组。

可以指定多个列作为索引列，多个索引列共同组成索引键。B-Tree索引适用于全键值、键值范围或键前缀查找，其中键前缀查找只适用与根据最左前缀查找。查找一定得按照索引的最左列开始。

B-Tree索引的数据结构

B-Tree

为了描述B-Tree，首先定义一条数据记录为二元组[key,data]，key作为记录的键值，对于不同数据记录，key是互不相同的，data为数据记录除key外的数据。

• 所有节点具有相同的深度，也就是说B-Tree是平衡的。

• 一个节点中的key从左到右非递减排列。

• 如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。

查找算法：首先在根节点进行二分查找，如果找到则返回对应节点的data，否则在相应区间的指针指向的节点递归进行查找。

由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、旋转等操作以保持 B-Tree 性质。

B+Tree

与B-Tree相比，B+Tree有以下特点：

• 每个节点的指针上限为2d而不是2d+1（d为B-Tree的度）。

• 内节点不存储data，只存储key；外节点不存储指针。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

这个优化的目的是为了提供区间访问的性能，例如图中如果要查询key为18到49的所有记录。

优势

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用B-Tree作为索引结构，主要有以下两个原因：

• 更好的检索次数：平衡树检索数据的时间复杂度等于树高h，而树高大致为O(h) = O(logN)，其中d为每个节点的出度。红黑树的出度为2，而B-Tree的出度一般都很大，红黑树的树高h明显比B-Tree打非常多，因此检索次数也就更多。B+Tree相比较B-Tree更合适外存索引，因为B+Tree内节点去掉了data域，因此可以拥有更大的出度，检索效率会更高。

• 利用计算机预读特性：为了减少磁盘 I/O，磁盘往往不是严格按需读取，而是每次都会预读。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，因此速度会非常快。操作系统一般将内存和磁盘分割成固态大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点，并且可以利用预读特性，相邻的节点也能够被预先载入。

参考：MySQL索引背后的数据结构及算法原理

哈希索引

InnoDB引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用得非常频繁，会在B+Tree索引之上再创建一个哈希索引，这样就让B+Tree索引具有哈希索引的一些优点，比如快速的哈希查找。

哈希索引能在O(1)时间进行查找，但是失去了有序性，它具有以下限制：

• 哈希索引只包含哈希值跟行指针，而不存储字段值，所以不能使用索引中的值来I避免都去行。

• 无法用于排序与分组。

• 只支持精确查找，无法用于部分查找与范围查找。

• 当出现哈希冲