Mysql
B+树
二叉查找树：任意节点的左边小于右边。劣势：不平衡 深度过高，极端情况要查询的次数很多
平衡二叉树（AVL）： 在二叉树的基础上平衡化，降低深度。每个节点的左右子树高度相差不超过1
B树：
- B是Balance，也是平衡树
- 相比平衡二叉树，每个节点存储更多的数据，并且超过2个子节点(多叉树)
- 下图是3阶B树，表示每个节点都有3个子节点。同时，每个节点存储两个记录
- 因为每个节点存储更多的数据，以及有更多的子节点，所示B树会更加矮胖，查询的深度会减少，从而提高查找效率
假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：
- 先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。
- 将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。
- 将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。
B+树：
- 非叶节点不存储数据，今储存key。增大树的阶，降低深度，减少查询 B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。
另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。
-
叶节点存储数据，变成顺序的，适合范围查找、排序、去重 因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。
-
各层节点形成双向链表，叶节点内的数据是单链表
聚集索引/非聚集索引
区别在于B+树中的key和value是什么
- 聚集索引： 节点中的key是主键，叶节点中的数据是完整记录
- 非聚集索引 节点中的key是非主键的列，叶节点中的数据是主键
拓展：红黑树
延展路径：二叉搜索树 -> AVL树（平衡二叉树） -> 红黑树
由于AVL树的限制太严格，插入时有大量的旋转操作，太耗时，出现了红黑树这种不严格平衡的树，使插入的最坏情况为 O(logn)
- 每个节点非红即黑；
- 根节点是黑的；
- 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
- 如果一个节点是红的,那么它的两儿子都是黑的；
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
- 高度始终保持在h = logn
- 红黑树的查找、插入、删除的时间复杂度最坏为O(log n)
简述MySQL InnoDB引擎和MyISAM引擎的差异？
- InnoDB支持事物，而MyISAM不支持事物。
- InnoDB支持行级锁，而MyISAM支持表级锁。
- InnoDB支持MVCC, 而MyISAM不支持。
- InnoDB支持外键，而MyISAM不支持。
- InnoDB不支持全文索引，而MyISAM支持。
事务
事务是指要么一起成功，要么一起失败的一组操作，满足ACID的特性：
- A 原子性：要么一起成功，要么一起失败。
- 回滚可以用回滚日志（Undo Log）来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。
- C 一致性：在一致性状态下，所有事务对同一数据的读取结果是一样的
- I 隔离型：在事务commit之前，中间状态对其他事务不可见
- D 持久性：一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。
- 系统发生崩溃可以用重做日志（Redo Log）进行恢复，从而实现持久性。与回滚日志记录数据的逻辑修改不同，重做日志记录的是数据页的物理修改。
事务的隔离性很难得到保证，Mysql提供了四种隔离等级
-
未提交读——问题：脏读、不可重复读、幻读
-
已提交读——问题：不可重复度、幻读
-
可重复读（InnoDB默认隔离级别）——问题：幻读
-
串行化
-
脏读：读到别的事务还没有提交的数据
-
不可重复读：一个事务第一次读读到一个值，再次读却读到另一个。 select * from xxx where id = xx;
-
幻读：进行范围操作，同一事务两次范围选取结果不一样。 select count(1) from xxx where id between a and b;
-
还有一个问题：更新丢失。事务A和B同时对一行修改，A的修改覆盖了B的修改。
Mysql提供上面的隔离级别，为的是简化并发控制，避免所有情况下都要用户来使用锁控制。但是，隔离级别不能解决所有的问题，在某些场景下，还是需要使用锁的。
Mysql默认使用自动提交，如果不开启自动提交，则有如下的命令，来开启事务、回滚事务、提交事务。
START TRANSACTION
// ...
SAVEPOINT delete1
// ...
ROLLBACK TO delete1
// ...
COMMIT
MVCC多版本并发控制（实现已提交读/可重复读）
多版本并发控制（Multi-Version Concurrency Control, MVCC）是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式，用于实现提交读和可重复读这两种隔离级别。而未提交读隔离级别总是读取最新的数据行，要求很低，无需使用 MVCC。可串行化隔离级别需要对所有读取的行都加锁，单纯使用 MVCC 无法实现。
InnoDB存储引擎使用多版本来进行并发控制，避免所有的并发控制都依赖于加锁。加锁能解决多个事务同时执行时出现的并发一致性问题，但是对cpu消耗较大，而多版本的思想是：写操作更新最新的版本快照，而读操作去读旧版本快照，没有互斥关系，也就不用加锁了。
InnoDB使用MVCC实现可重复读：（目标就是读到小于等于当前事务版本的数据）。
- SELECT时，读取创建版本号<=当前事务版本号，删除版本号为空或>当前事务版本号。（已创建，未删除）
- INSERT时，保存当前事务版本号为行的创建版本号
- DELETE时，保存当前事务版本号为行的删除版本号
- UPDATE时，插入一条新纪录，保存当前事务版本号为行创建版本号，同时保存当前事务版本号到原来删除的行。UPADTE被认为是INSERT+DELETE
MVCC对普通select是不加锁的，对于更新（inert/update/delete）是加锁的。不加锁的操作是“快照读”，加锁的操作是“当前读”并使用最新数据。
快照读：就是select
- select * from table ….;
当前读：特殊的读操作，插入/更新/删除操作，属于当前读，处理的都是当前的数据，需要加锁。
- select * from table where ? lock in share mode;
- select * from table where ? for update;
- insert;
- update ;
- delete;
依托MVCC实现了可重复读，怎么解决幻读呢？
幻读是指在范围查询读到了该事务开始前不存在的行，即where条件为where a between x and x。
使用Next-key锁：是记录锁（行锁）和间隙锁的结合。
间隙锁的作用是锁住一个范围，禁止向这个范围内insert数据，从而解决幻读的问题。
对非索引字段增加netkey锁，将会锁定全部的行和间隙，导致表现得像表锁
数据库设计范式
- 1NF：属性不可再分
- 2NF：非主属性不部分依赖于主属性
- 3NF：非主属性不传递依赖于主属性（不存在非主属性决定其他非主属性的情况）
- BCNF：如果一个属性组 A 能决定任意属性 B，那么属性组 A 必然包含候选键（主属性 也不存在部分依赖和传递依赖）
分布式事务
上面谈到的事务都是在同一个db中的事务，如果是多个db，就存在分布式事务的问题，常见于分库分表
XA方案
两阶段提交方案
- 阶段一： prepare，但不commit
- 阶段二： 如果阶段一都成功了，则commit，不成功则都rollback
TCC方案
try-confirm-cancel
- try：锁定资源。冻结账户里的30元
- confirm：扣减资源。扣减已被冻结的30元
- cancel：恢复已扣减的资源。恢复上一步被扣减的30元
try成功则confirm一定会成功。
两者区别：
XA直接作用于DB，依赖DB的commit和rollback来做回滚 TCC则作用于服务层，意味着回滚逻辑需要写代码