B-树，B+树

B树：每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null。
B+树：只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。所有非终端节点看成是索引，节点中仅含有其子树根节点最大（或最小）的关键字，不包含查找的有效信息。B+树中所有叶子节点都是通过指针连接在一起。
存储结构
内存中存储的数据是有限的，当需要在磁盘中进行查找时就涉及到了磁盘的 I/O 操作。当磁盘驱动器执行读/写功能时。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读/写头(又叫磁头) 下通过时，就可以进行数据的读 / 写了。磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间。
索引查找时产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小，I/O次数越少。平衡树的高度过深进行多次磁盘IO，导致查询效率低下，而B树和B+树树中每个结点最多含有m个孩子，所以相对平衡树B树和B+树的高度比较低。
总结：为什么使用B+树？
1.文件很大，不可能全部存储在内存中，故要存储到磁盘上
2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数
3. 局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数，（在许多操作系统中，页得大小通常为4k）
4. 数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O 就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性。
为什么B+树比B树更适合做索引？
1.B+树磁盘读写代价更低
B+的内部结点并没有指向关键字具体信息的指针，即内部节点不存储数据。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2.B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

1、读锁（共享锁）是读取操作创建的锁。其他用户可以并发读取数据，但任何事务都不能对数据进行修改（获取数据上的排他锁），直到已释放所有共享锁。
如果事务T对数据A加上共享锁后，则其他事务只能对A再加共享锁，不能加排他锁。获准共享锁的事务只能读数据，不能修改数据。
2、写锁（排他锁）如果事务T对数据A加上排他锁后，则其他事务不能再对A加任任何类型的封锁。获准排他锁的事务既能读数据，又能修改数据。
3、事务可以通过以下语句给sql加共享锁和排他锁：
共享锁：select …… lock in share mode;
排他锁：select …… for update;

ACID
事务指"一个被视为单一的工作单元的操作序列"。一个良好的事务处理系统，必须具备四个标准特性，即ACID：
原子性（Atomicity）：一个事务必须被视为一个不可分割的最小工作单元，整个事务中的所有操作要么全部提交成功，要么全部失败回滚，对于一个事务来说，不可能只执行其中的一部分操作。
一致性（Consistency）：数据库总是从一个一致性的状态转换到另一个一致性的状态。
隔离性（Isolation）：通常来说，一个事务所做的修改在最终提交以前，对其他事务是不可见的。针对不同的业务需求，隔离性分为4个级别：读未提交、读已提交、可重复读、串行化。见下。
持久性（Durability）：通常来说，一旦事务提交，则其所做的修改会永久保存到数据库（即使系统崩溃，修改的数据也不会丢失）。
隔离性的4个级别
包括读未提交（Read Uncommitted）、读已提交（Read Committed）、可重复读（Repeatable Read）、可序列化（Serializable）；及其对应的问题，包括脏读（Dirty Read）、不可重复读（Nonrepeatble Read）、幻读（Phantom Read）。
读未提交：
读未提交是数据库应保证的最低的隔离性级别：事务中的修改，即使没有提交，对其他事务也都是可见的。读未提交面临脏读的问题：事务可以读取未提交的数据，而该数据可能在未来因回滚而消失。从性能上来说，读未提交不会比其他的级别好太多，但却缺乏其他级别的很多好处。除非真的有非常必要的理由，在实际应用中很少使用。

读已提交：
读已提交满足前面提到的隔离性的简单定义：一个事务所做的修改在最终提交以前，对其他事务是不可见的。换句话说，一旦提交，该事务所作的修改对其他正在进行中的事务就是可见的。狭义上，读已提交解决了脏读的问题。这个级别有时候叫做不可重复读，面临不可重复读的问题：两次执行同样的查询，如果第二次读到了其他事务提交的结果，则会得到不一样的结果。

可重复读：
在读已提交的基础上，可重复读解决了部分不可重复的问题：同一个事务中多次读取同样记录结果是一致的。记录指具体的数据行。未能解决的那部分称为幻读：当某个事务在读取目标范围内的记录时，另一个事务又在该范围内插入了新的记录，当之前的事务再次读取该范围的记录时，会产生第一次读取范围时不存在的幻行（Phantom Row）。需要注意的是，只有插入会产生幻行。

MySQL的默认隔离级别是可重复读，有幻读问题。

可序列化：
可序列化是最高的隔离级别：强制事务序列化执行。可序列化解决了幻读问题。简单来说，可序列化会在目标范围加独占锁，将并发读写相同范围数据的请求序列化。可序列化会导致大量的超时和锁争用问题，因此，实际应用中很少用到这个隔离级别，只有在非常需要确保数据的一致性而且可以接受没有并发的情况下，才考虑采用该级别。

原理
讨论基于锁的并发控制中，4种隔离性级别的实现原理。重点关注读锁（read lock）、写锁（write lock，或称排它锁）、范围锁（range lock）、锁的持有时间等概念。
读未提交
读未提交的实现：读锁、写锁都在一个原子操作（如select、insert等）完成后立即释放。换句话说，事务作出更新后，不管是否提交，由于已经释放了目标记录的写锁，更新对其他事务就是可见的。
区分目标记录与目标范围（见后文可重复读的实现原理）：
目标记录指一个具体的数据行；读锁、写锁只针对目标记录。
目标范围指一个where语句描述的范围；范围锁针对目标范围，见后。
读已提交
出现脏读的原因是写锁的持有时间过短。读已提交针对这一问题作出了优化：读锁仍然在一个原子操作完成后立即释放；写锁从写操作开始持有，事务提交后释放。事务作出更新前，会先申请目标记录的写锁，并持续持有至事务提交后，释放锁后，更新对其他事务才是可见的。
可重复读
解决不可重复读可以使用两种方法：1.悲观策略：串行化2.乐观策略：多版本 + 冲突检测
1.悲观策略：串行化
“串行化”不需要解释，放弃并发、串行执行当然不存在任何问题。
“串行化”的可重复读实现是：读锁、写锁从读、写操作开始持有，事务提交后释放。与读已提交的实现相比，可重复读延长读锁的持有时间直到事务提交后，在此期间，目标记录无法被修改。
对于读已提交中的操作序列，操作2发生时，事务1开始持有目标记录的读锁，导致事务2的操作4会陷入阻塞，直到事务1提交释放锁。

2.乐观策略：多版本 + 冲突检测
“多版本 + 冲突检测”是更常见的实现方案：多个事务采用多个版本，最后提交时检测是否与当前数据版本冲突，如果冲突则报错提醒，否则成功提交。
“多版本 + 冲突检测”的可重复读实现是：事务开始时持有当前数据的快照，读写均不冲突，提交时检测修改的快照与当前数据是否冲突。使用乐观的冲突检测策略代替悲观的锁策略，在中低程度的并发情况下性能更好。

对于读已提交中的操作序列，事务1、2各自持有不同版本的快照，在操作4修改自己版本的目标记录后，操作5提交事务2，检测不冲突（假设没有其他事务），合并到当前数据，当前数据完成修改；然后操作6继续修改自己版本的目标记录，操作7提交事务1，发现与当前数据冲突，给出报错。

可序列化
对于基于锁的“串行化”方案，可序列化实现：从各操作开始前持有读锁、写锁、范围锁，直到事务提交后释放。对于“多版本 + 冲突检测”方案，可序列化基于更严格的写冲突检测来实现，详见“快照隔离”技术。
范围锁如何解决幻读问题呢？
范围锁是一个逻辑概念上的锁，事务从读、写操作（带显式或隐式where）开始前持有范围锁，直到事务提交后释放。忽略读、写锁，对可重复读中操作序列的影响如下：操作2中事务1获取了目标范围上的范围锁，操作4发现目标范围被锁，陷入阻塞，直到操作7事务提交。

隔离性级别的总结
各隔离级别解决了不同的问题。”Y”说明存在问题，”-“说明不存在：

在基于锁的并发控制中，依靠不同的锁持有时间实现各隔离级别。锁均从操作前开始持有，”S”表示操作结束后释放，”C”表示事务提交后释放：

MySQL的默认隔离级别是可重复读，解决了脏读、部分不可重复读问题，有幻读问题。

MVCC
1、MVCC(全称Multi-Version Concurrent Control)是一种多版本并发控制机制。利用MVCC解决幻读问题，让同一个事务内多次执行的查询sql都能获取相同的数据集合。MVCC不加锁，提高访问效率。
2、MVCC只是工作在两种事务级别底下：(a) Read Committed (b) Repeatable Read;
因为其他两种：
©READ UNCOMMITTED：总是读取最新的数据，不符合当前事务版本的数据行。
(d)Serializable则会对所有的行加锁。
这两种都不需要MVCC；
3、MVCC 具体实现
Innodb的MVCC是通过在每行记录后面保存两个隐藏的列来实现的。这两个列，一个保存了这个行的创建时间，另一个保存的是行的删除时间。这里存储的并不是实际的时间值，而是系统版本号，每开始一个新的事务，系统版本号就会自动递增，事务开始时刻的系统版本号会作为事务的ID。

间隙锁
行锁（Record Lock）:锁直接加在索引记录上面，锁住的是key。
间隙锁（Gap Lock）:锁定索引记录间隙，确保索引记录的间隙不变。间隙锁是针对事务隔离级别为可重复读或以上级别而已的。基于非唯一索引。
间隙锁的目的是为了防止幻读，其主要通过两个方面实现这个目的：
（1）防止间隙内有新数据被插入
（2）防止已存在的数据，更新成间隙内的数据（例如防止numer=3的记录通过update变成number=5）
Next-Key Lock ：行锁和间隙锁组合起来就叫Next-Key Lock。通过临建锁可以解决幻读的问题。 每个数据行上的非唯一索引列上都会存在一把临键锁，当某个事务持有该数据行的临键锁时，会锁住一段左开右闭区间的数据。需要强调的一点是，InnoDB 中行级锁是基于索引实现的，临键锁只与非唯一索引列有关，在唯一索引列（包括主键列）上不存在临键锁。

默认情况下，InnoDB工作在
可重复读(Repeatable Read)隔离级别下，并且会以Next-Key Lock的方式对数据行进行加锁，这样可以有效防止幻读的发生。Next-Key Lock是行锁和间隙锁的组合，当InnoDB扫描索引记录的时候，会首先对索引记录加上行锁（Record Lock），再对索引记录两边的间隙加上间隙锁（Gap Lock）。加上间隙锁之后，其他事务就不能在这个间隙修改或者插入记录。
read committed隔离级别下，Gap Lock在InnoDB的唯一作用就是防止其他事务的插入操作，以此防止幻读的发生。

间隙锁在InnoDB的唯一作用就是防止其它事务的插入操作，以此来达到防止幻读的发生，所以间隙锁不分什么共享锁与排它锁。默认情况下，InnoDB工作在Repeatable Read隔离级别下，并且以Next-Key Lock的方式对数据行进行加锁，这样可以有效防止幻读的发生。Next-Key Lock是行锁与间隙锁的组合，当对数据进行条件，范围检索时，对其范围内也许并存在的值进行加锁！当查询的索引含有唯一属性（唯一索引，主键索引）时，Innodb存储引擎会对next-key lock进行优化，将其降为record lock,即仅锁住索引本身，而不是范围！若是普通辅助索引，则会使用传统的next-key lock进行范围锁定！要禁止间隙锁的话，可以把隔离级别降为Read Committed，或者开启参数innodb_locks_unsafe_for_binlog。

在MVCC并发控制中，读操作可以分成两类：快照读 (snapshot read)与当前读 (current read)。
快照读，读取的是记录的可见版本 (有可能是历史版本)，不用加锁。
当前读，读取的是记录的最新版本，并且，当前读返回的记录，都会加上锁，保证其他事务不会再并发修改这条记录。
在一个支持MVCC并发控制的系统中，哪些读操作是快照读？哪些操作又是当前读呢？以MySQL InnoDB为例：
快照读：简单的select操作，属于快照读，不加锁。(当然，也有例外，下面会分析)
select * from table where ?;
当前读：特殊的读操作，插入/更新/删除操作，属于当前读，需要加锁。
select * from table where ? lock in share mode;
select * from table where ? for update;
insert into table values (…);
update table set ? where ?;
delete from table where ?;
所有以上的语句，都属于当前读，读取记录的最新版本。并且，读取之后，还需要保证其他并发事务不能修改当前记录，对读取记录加锁。其中，除了第一条语句，对读取记录加S锁 (共享锁)外，其他的操作，都加的是X锁 (排它锁)。