1. 数据库索引与B+树

  • 索引是一种数据结构用于在大量的数据中快速定位到我们想要的数据，mysql数据库中的索引主要有B+树索引、Hash索引和全文索引 ### 1.1 二叉搜索树和平衡树

  • B+树是由二叉搜索树和平衡树发展而来的，二叉搜索树是一种最简单的索引，但是在一定的条件下会退化成一个链表，造成索引的性能下降的问题，而平衡树可以解决这一问题，平衡树会根据一定的规则自适应地调整树的节点和高度，使得索引尽可能保持一个平衡的树形结构，常见的有AVL树、Splay树和红黑树等

    • 平衡树相比于普通的二叉搜索树查找效率更稳定，总体的查询速度也更快

  • 一般来说数据库中的数据规模都比较大，所以内存很容易放不下这么多数据和索引，因此通常会把索引和数据存储在磁盘之类的外围设备中，但是和内存相比，磁盘IO的效率非常低，并且是按block存取的，因此应该尽可能将要查询的数据放在一个磁盘中，也就是说要让树的节点多存放一些数据 ### 1.2 B树与B+树

  • B树相比于平衡二叉树，每个节点存储了更多的key和data，B+树相比于B树做出了一些改进，最重要的一点就是非叶节点不存储数据，而是只存储一系列的key用于索引，相比于B树磁盘IO的代价更低了。

    • 同时节点中还有类似于bucket的结构，用于容纳更多的数据

  • 这么做的原因是因为数据库中一个节点的大小被固定成了磁盘的一个block的大小，常见的一般是4096KB，这样一来一个节点可以存储非常多的数据，因此B+树的阶数也就非常大，ads中一般都是3阶或者4阶的B+树而数据库系统的索引模块构建的B+树很可能有几百阶和几千阶，因此需要磁盘IO的次数非常少

    • Mysql的InnoDB引擎中使用的就是B+树的索引

1.3 聚集索引和非聚集索引

  • 在MySQL中，B+树索引按照存储方式的不同分为聚集索引和非聚集索引
  • 聚集索引（聚簇索引）：以innodb作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中所有的数据。这种以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚集索引
    • 其实就是说B+树中如果叶节点存储了整条数据的，那就是聚集索引
    • innodb主要就是聚集索引
  • 非聚集索引（非聚簇索引）：以主键以外的列值作为键值构建的B+树索引，我们称之为非聚集索引。非聚集索引与聚集索引的区别在于非聚集索引的叶节点不存储表中的数据，而是存储对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。
    • 等于说非聚集索引需要配合聚集索引使用
    • Innodb中每个表一定会被创建一个聚集索引，就算建表的时候没有创建主键，也会自动创建一个然后建立聚集索引，非聚集索引需要用到聚集索引来帮助查找元素

2. 数据库范式

  • 数据库的范式是对数据库和数据表的设计原则，要求存储信息的时候没有不必要的冗余，使得信息检索的效率提高，常见的范式有第一范式和BCNF范式 ### 2.1 第一范式与第二范式

  • 第一范式是最简单的范式，要求数据表的设计具有原子性，不能再向下继续拆分

    • 第一范式存在冗余，并且数据的更新非常复杂，难以处理null-value #### 2.1.1 数据库的四种键

  • super key超键：能够唯一标识元组的属性集，即对于每一条关系而言超键的值是唯一的

    • 超键可以是多个属性的组合
    • 如果A是关系R的一个超键，那么(A, B)也是关系R的一个超键
    • 超键的“唯一标识”各个元组是可以有冗余信息的

  • candidate key候选键：不含多余属性的超键

    • 如果K是R的一个超键，而任何K的真子集不是R的一个超键，那么K就是R的一个候选键

  • primary key主键：

    • 数据库管理员指定的元组标识的一个候选键，不能是null值

  • foreign key外键：用来描述两个表之间的关系，可以有空值

    • 如果关系模式R1中的一个属性是另一个关系模式R2中的一个主键，那么这个属性就是R1的一个外键
      • a foreign key from r1 referencing r2 #### 2.1.2 函数依赖

  • 对于一个关系模式R，如果 并且 则函数依赖 定义在R上，当且仅当对于R的任意关系r(R)  当其中的任意两个元组t1和t2，如果他们的属性值相同可以推出他们的属性值也相同 #### 2.1.3 第二范式

  • 第二范式的定义：如果某个关系R属于第一范式，并且每个非主属性完全函数依赖于另一个候选键，那就是第二范式 ### 2.2 BC范式

  • BC范式的条件是：闭包中的所有函数依赖 至少满足下面的一条

    • 是平凡的(也就是β是α的子集)
    • α是关系模式R的一个超键，即

3. 数据库的锁与并发

3.1 普通锁

  • 普通锁分为共享锁和排他锁，共享锁S允许多个事务持有读取同一个记录的权限，排他锁X使得多个事务中每次只能有一个事务拥有对一条记录写和修改的权限

    • 这两种锁的作用是为了提高数据库的并发性
    • 当一条记录的排他锁被占用的时候，不能分配共享锁或者排他锁给其他的事务，即X与X和S都冲突，而共享锁可以在一段时间内分出去多个

  • 值得注意的是普通锁都是行级的，即对一条记录有效 ### 3.2 意向锁

  • InnoDB中有多种粒度的锁，普通锁是行级的，而意向锁是表级的，用来表明一个事务正在持有锁或者正在申请一个锁。

  • 共享意向锁（IS）：表示事务持有表中行的共享锁或者打算获取行的共享锁，事务在获取S锁之前必须要获取IS锁，即表明自己的意向，可以理解为投名状

  • 共享排他锁（IX）：表示事务持有表中行的排他锁或者打算获取行的排他锁，事务在获取X锁之前必须要或许IX锁 ### 3.3 记录锁

  • 记录锁是对索引记录的锁定，换句话说就是，记录锁只会锁定索引。每一个表必定会有一个主键索引（用户定义的主键、唯一索引、隐式生成），而该主键索引中的非叶子节点中的记录就是使用该记录锁进行锁定

  • InnoDB中还有二级索引，二级索引跟主键索引一样，在使用二级索引作为查询条件时，会将符合条件的二级索引的记录使用记录锁进行锁定，然后再回表将对应的主键索引也使用记录锁进行锁定 ### 3.4 间隙锁

  • 间隙锁（简称为 Gap）是对索引记录之间的间隙的锁定，或者是对第一条索引记录之前的间隙和对最后一条记录之后的间隙的锁。间隙锁是防止幻读的主要手段之一。

  • 其他的像是Next-Key锁、插入意向锁和AUTO-INC锁感觉比较冷门就先不管了。

4. 事务处理、日志与故障恢复

4.1 事务的特性

  • 数据库中的事务具有ACDI四个特性，分别是原子性，持久性，一致性和独立性
    • 原子性要求事务在处理的过程中不能被打断，要不就完成，要不就不执行事务
    • 持久性要求更新之后如果软硬件出了问题，数据也还是要存在
    • 一致性要求多个事务并发的时候数据要保持一致
    • 独立性要求事务的执行不能被其他的事务感知，必须独立执行，执行的过程对外隐藏
  • 事务的状态：
    • active 初始状态，执行中的事务都处于这个状态
    • partially committed 在最后一句指令被执行之后
    • failed 在发现执行失败之后
    • aborted 回滚结束，会选择是重新执行事务还是结束
    • committed 事务被完整的执行

4.2 日志与事务恢复

  • 数据库需要在发生故障的时候进行恢复，而恢复需要基于日志进行，日志需要写在稳定的存储中，比如磁盘，而一般事务开始需要写入start，进行操作修改值的时候需要写入修改的情况，结束或者中止的时候需要写入abort或者commit
    • 日志的写入需要比实际操作早，先写日志再进行实际的操作
  • 事务在恢复的过程中需要进行一系列的undo或者redo，undo就是将进行到一半的事务撤销，redo就是重复一次做过的事务

5. MySQL相关的概念

5.1 一致性读写的相关概念

  • 脏读：另一个事务修改了数据，但尚未提交并写到硬盘中，但是日志中已经有了修改记录，而本事务中会读到这些未被提交的数据
    • 也就是读了别人还没提交的数据
  • 不重复读：解决了脏读后，会遇到，同一个事务执行过程中，另外一个事务提交了新数据，因此本事务先后两次读到的数据结果会不一致
    • 多次读同一个数据的不同结果，脏读读取到的是未提交的数据，而不可重复度读到的是提交了的数据
  • 幻读：解决了不重复读，保证了同一个事务里，查询的结果都是事务开始时的状态（一致性）。但是，如果另一个事务同时提交了新数据，本事务再更新时，就会“惊奇的”发现了这些新数据，貌似之前读到的数据是“鬼影”一样的幻觉
    • 事务不独立执行的后果，一起修改导致发生幻觉
    • 比如两个事务同时执行，一个事务在修改表中的值，另一个事务直接插入了一条新的记录，这时候第一个事务会发现中间出现了一行自己没有修改过的记录，就好像发生了幻觉一样 ### 5.2 InnoDB的四个隔离级别
  • 未提交读（READ UNCOMMITTED）。另一个事务修改了数据，但尚未提交，而本事务中的SELECT会读到这些未被提交的数据（脏读）( 隔离级别最低，并发性能高 )
    • 即就算没有提交也要进行另一个可能涉及到这部分数据的事务。
    • 不能解决脏读、不可重复度和幻读的问题，但是并发性能很好
  • 提交读（READ COMMITTED）。保证本事务读取到的是最新的数据（一定是其他事务提交后的）。问题是，在同一个事务里，前后两次相同的SELECT会读到不同的结果（不重复读）。会出现不可重复读、幻读问题（锁定正在读取的行）
    • 可以防止脏读的发生
  • 可重复读（REPEATABLEREAD）。在同一个事务里，SELECT的结果是事务开始时时间点的状态，因此，同样的SELECT操作读到的结果会是一致的。但是，会有幻读现象
    • 可以防止脏读，不可重复读的发生
    • 每个事务在执行的过程中不允许其他事务update，但是允许进行insert
    • mysql默认的事务隔离级别就是可重复读
  • 串行化（SERIALIZABLE）。读操作会隐式获取共享锁，可以保证不同事务间的互斥（锁表）
    • 事务的并发性能最低

5.3 MySQL引擎特点

  • MySQL的引擎分为两种，早期用的是MyISAM，后来逐渐变成了InnoDB，二者的主要区别在于：
    • InnoDB支持事务，MyISAM不支持，对于InnoDB每一条SQL语言都默认封装成事务，自动提交，这样会影响速度，所以最好把多条SQL语言放在begin和commit之间，组成一个事务
    • InnoDB支持外键，而MyISAM不支持。对一个包含外键的InnoDB表转为MYISAM会失败；
    • InnoDB是聚集索引，使用B+Tree作为索引结构，数据文件是和（主键）索引绑在一起的（表数据文件本身就是按B+Tree组织的一个索引结构），必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大
      • Innodb的数据和索引是一起存储的
    • MyISAM是非聚集索引，也是使用B+Tree作为索引结构，索引和数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的
    • **InnoDB不保存表的具体行数，执行select count(*) from table时需要全表扫描。而MyISAM用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快（注意不能加有任何WHERE条件）**
    •  Innodb不支持全文索引，而MyISAM支持全文索引，在涉及全文索引领域的查询效率上MyISAM速度更快高；PS：5.7以后的InnoDB支持全文索引了
    • InnoDB支持表、行(默认)级锁，而MyISAM支持表级锁
    • InnoDB表必须有唯一索引（如主键）（用户没有指定的话会自己找/生产一个隐藏列Row_id来充当默认主键）