数据库是文件的集合，是依照某种数据模型组织起来并存放于二级存储器中的数据集合。
数据库实例是程序，是位于用户与操作系统之间的一层数据管理软件，用户对数据库数据的任何操作，都是在数据库实例下进行的。

集群情况下可能存在一个数据库被多个数据库实例使用的情况。

存储引擎是基于表的，而不是数据库

存储引擎分类：

• InnoDB存储引擎
  事务安全，行锁设计，支持MVCC，支持外键，提供一致性非锁定读，同时被用来最有效地利用以及使用内存和CPU。主要面向OLTP应用。
• MyISAM存储引擎
  不支持事务、表锁设计，支持全文索引。主要面向OLAP数据库应用。
• NDB存储引擎
• Memory存储引擎
• Archive存储引擎
• Federated存储引擎
• Maria存储引擎
• 其他存储引擎

连接MySql方式

• TPC/IP
• 命名管道和共享内存
• UNIX域套接字

---

InnoDB体系结构

1、后台线程

• Mater Thread
• IO Thread
• Purge Thread

2、内存

2.1 缓冲池

为了协调CPU速度与磁盘速度的鸿沟

2.1.1结构

• 数据页
• 索引页
• 插入缓冲
• 锁信息
• 自适应哈希索引
• 数据字典信息

2.1.2 LRU List、Free List、Flush List

LRU（最近最少使用），使用最频繁的页在LUR列表的前端，最少使用的页在LRU列表的尾端。当缓冲池不能存放新读取的页的时候，将首先释放LRU列表中尾端的页。
InnoDB引擎优化了LRU，加入了midpoint位置。即新读取到的页，并不是直接放入LRU前端，而是放到midpoint位置。默认为LRU列表长度的5/8处。（可以修改）
可以有效防止热点数据被刷出。
InnoDB中还有innodb_old_blocks_time参数来控制读取到mid位置后需要等待多久才会被加入到LRU列表的前端。

数据库刚启动时，LRU中为空，页都存放在Free List中。使用时首先查找Free列中是否有可用空闲页，若有则从Free列中删除，放入LRU列中。否则，淘汰LRU列表末尾的页，新的页放入LRU列表中。

在LRU列表中的页被修改后，该页被称为脏页。数据库通过checkpoint机制将脏页刷新回磁盘。

Flush列表中的页即为脏页列表。（脏页既存在于LRU列表中，也存在于Flush列表中）

2.2 重做日志缓冲

• Mster Thread每一秒，将重做日志缓冲刷新到重做日志文件
• 每个事务提交时，将重做日志缓冲刷新到重做日志文件
• 重做日志缓冲池剩余空间小于1/2时，将重做日志缓冲刷新到重做日志文件

2.3 额外的内存池

3、CheckPoint技术

为了避免发生数据丢失的问题，当前事务数据库系统普遍采用了Write Ahead Log策略。当事务提交时，先写重做日志，再修改页。

CheckPoint技术解决：

1. 缩短数据库的恢复时间
   CheckPoint之前的页都已经刷新到磁盘

2. 缓冲池不够用时，将脏页刷新到磁盘
   LUR算法溢出最近最少使用的页，若此页为脏页，强制执行CheckPoint

3. 重做日志不够用时，刷新脏页
   重做日志没有可以被重用的部分，强制执行CheckPoint，将缓冲池中的页至少刷新到当前重做日志的位置。

• Sharp CheckPoint
  将所有脏页刷新到磁盘。用于数据库关闭时。若运行时使用会导致可用性降低。
• Fuzzy CheckPoint
  只刷新一部分脏页到磁盘。

  • Master Thread CheckPoint
    Master Thread每秒或每10秒舒心一定比例的脏页。异步的，用户查询线程不受影响。

  • FLUSH_LRU_LIST CheckPoint
    需要保证LRU中有100个空闲页。若不足100个，将列表尾端页移除。若被移除页存在脏页，需要进行CheckPoint。

  • Async/Sync Flush CheckPoint

  • Dirty Page too much CheckPoint

---

InnoDB关键特性

• 插入缓冲
• 两次写
• 自适应哈希索引
• 异步IO
• 刷新临接页

插入缓冲（性能上的提升）

Inert Buffer

对于非聚集索引的插入或更新操作，不是每一次直接插入到索引页中，而是先判断插入的非聚集索引页是否在缓冲池中，若在，则直接插入；若不在，则先放入一个Insert Buffer对象中。然后再以一定的频率和情况进行Insert Buffer和辅助索引页子节点的merge操作，这时通常能将多个插入合并到一个操作中。

使用Inser Buffer必须满足：

• 索引是辅助索引
• 索引不是唯一的（因为不能去数据库中查找）

缺点：
在写密集的情况下，插入缓冲会占用过多的缓冲池内存，默认最大可占用1/2。

Change Buffer

Inert Buffer的升级
INSERT、DELETE、UPDATE均可以进行缓冲，对应
Insert Buffer、Delete Buffer、Purge Buffer

必须满足

• 索引是辅助索引
• 索引不是唯一的（因为不能去数据库中查找）

例如对UPDATE操作：

1. 将记录标记为已删除
2. 真正将记录删除

Insert Buffer内部实现

Insert Buffer是一棵B+树。
MysSQL4.1之前每个表都有一棵Insert Buffer B+树
现在全局只有一棵Insert Buffer B+树，放在共享表空间中。

两次写（可靠性的提升）

简单来说，就是在写数据页之前，先把这个数据页写到一块独立的物理文件位置（ibdata），然后再写到数据页。这样在宕机重启时，如果出现数据页损坏，那么在应用redo log之前，需要通过该页的副本来还原该页，然后再进行redo log重做，这就是double write

在对缓冲池的脏页进行刷新时，并不直接写磁盘，而是通过memcpy函数将脏页先复制到内存中的doublewrite buffer，之后通过doublewrite buffer分两次，每次1MB的顺序写入共享表空间的物理磁盘上。
然后马上调用fsync函数，同步磁盘。

image.png

自适应哈希索引

InnoDB存储引擎会监控对表上各索引页的查询。如果观察到建立哈希索引可以带来速度提升，则建立哈希索引，成为自适应哈希索引（AHI）

image.png

建立自适应哈希索引条件

• 访问模式相同
• 以该模式访问了100次
• 页通过该模式访问了N次，其中N=页中记录*1/16

缺陷
1、hash自适应索引会占用innodb buffer pool；
2、自适应hash索引只适合搜索等值的查询，如select * from table where index_col='xxx'，而对于其他查找类型，如范围查找，是不能使用的；
3、极端情况下，自适应hash索引才有比较大的意义，可以降低逻辑读。

异步IO（提高磁盘操作性能）（AIO）

用户在发出一个IO请求后可以立即再发出另一个IO请求，当全部IO请求发送完毕后，等待所有IO操作的完成。
（另一个优势是可以进行IO Merge操作，将多个IO操作合并为1个）

刷新临接页

当刷新一个脏页时，会检测该页所在区的所有页，如果是脏页，那么一起进行刷新。
（可以通过AIO将多个IO写入合并为一个IO操作，在传统机械硬盘下有显著优势）

• 是不是可能将不怎么脏的页进行了写入，而该页之后很快变为脏页
• 固态硬盘有着很高的IOPS，是否还需要这个特性。

---

日志文件

• 错误日志
• 二进制日志
  记录了对MySQL数据库执行更改的所有操作（不包括Select和Show）
  主要作用：
  • 恢复：某些数据的恢复需要二进制文件
  • 复制：
  • 审计：用户可以通过二进制日志中的信息来进行审计，判断时候有对数据库进行注入的攻击
• 慢查询日志
• 查询日志

二进制文件与重做日志文件不同：

• 记录的内容不同：
  二进制文件记录的是一个事务的具体操作内容，是逻辑日志
  重做事务文件记录的是关于每个页的更改的物理情况
• 写入的时间不同
  二进制文件仅在事务提交前进行提交，只写磁盘一次，不论该事务多大。
  重做日志文件在事务进行的过程中，不断有重做日志条目被写入到重做日志文件中

重做日志文件写入前需要先写入重做日志缓冲。从重做日志日志缓冲写入磁盘时，按照512字节（即一个扇区）。因为扇区是写入的最小单位，因此可以保证写入必定成功。因此重做日志的写入不需要double write。

---

---

定义默认主键时原则：

• 首先判断表中是否有非空的唯一索引，如果有，则该列为主键
• 如果不符合上述条件，则InnoDB将自动创建一个6字节大小的指针

（存在多个非空唯一索引时，取第一个定义 的）
InnoDB逻辑存储结构

• 表空间tablespace
• 段segment
• 区extent
• 页page
• 行row

---

数据完整性约束

• 实体完整性保证表中有一个主键
  • 使用Primary Key或Unique Key约束来保证实体的完整性
  • 用户可以通过编写一个触发器来保证数据完整性
• 域完整性保证数据每列的值满足特定的条件
  • 选择合适的数据类型确保一个数据值满足条件
  • 外键约束
  • 编写触发器
  • 考虑用DEFAULT约束作为强制域完整性的一个方面
• 参照完整性保证两张表之间的关系
  • 可以通过外键
  • 编写触发器

---

MySQL支持的分区类型为水平分区，不支持垂直分区
水平分区：同一表中不同行记录在不同物理文件中
垂直分区：同一表中不同列记录在不同物理文件中

MySQL的分区是局部分区索引，即一个分区中既存放了数据又存放了索引。
全局分区是数据存放在各个分区中，但所有数据的索引存放在一个对象中。
目前MySQL还不支持全局分区

分区类型：

• RANGE分区。根据给定连续区间分区。
• LIST分区。与RANGE分区类似，只不过是面向离散值。
• HASH分区。根据用户自定义的表达式返回值分区，返回值不能为负数。
• KEY分区。根据MySQL数据库提供的哈希函数分区。
  上面分区条件是数据必须是整型

*COLUMNS分区。可以看做是RANGE和LIST的进化。可以直接使用非整型数据进行分区。

子分区（或复合分区）
MySQL允许在RANGE和LIST的分区上再进行HASH或KEY的子分区

• OLTP（在线事务处理）
  分区应该非常小心。对于一张大表，B+树只需要2~3次IO，不需要分区帮助。

• OLAP（在线分析处理）
  分区可以很好地提高查询性能。

索引与算法

InnoDB支持以下常见的索引：

• B+树索引
• 全文索引
• 哈希索引（系统自适应生成，不能人为干预）

B+树索引并不能找到一个给定键值得具体行，B+树索引只能找到被查找数据所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

平衡二叉树：
首先符合二叉查找树的定义，
其次必须满足任意一个节点的两个子树的高度最大差为1

平衡二叉树的查找性能是比较高的，但不是最高的。（最好的性能需要建立最优二叉树）
左旋

20180722220546910 .gif

右旋

20180722222413303.gif

一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都至少包含ceil(m / 2)个孩子，最多有m个孩子。

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

image.png

B+树相对B-树的优势：

1. IO次数更少
   B+树的中间节点不存储具体数据，同样大小的磁盘页可以容纳更多数量的节点。即数据量相同的情况下，B+树比B-树更“矮胖”。查询时IO数也更小。
2. 查询性能更稳定
   B-树查询时找到匹配元素即可，而B+树必须查找到最终的叶子节点。查询性能更稳定。
3. 范围查询简便
   B-树只能靠繁琐的中序遍历进行范围查询。B+树只需要在叶子节点的链表上做遍历即可。

B+树索引可以分为聚集索引和辅助索引

聚集索引

聚集索引就是按照每张表的主键构建一棵B+树，叶子节点中存放的是整张表的行记录数据，叶子节点也称为数据页。

由于实际的数据页只能按照一棵B+树排序，因此每张表只能拥有一个聚集索引。
（查询优化器倾向于采用聚集索引，因为聚集索引可以在叶子节点上直接查找到数据）

辅助索引（非聚集索引）

辅助索引的叶子节点并不包含行记录的全部数据，每个叶子节点的索引行中包含了一个书签，该书签是相应行数据的聚集索引。
当通过辅助索引来查找数据时，InnoDB引擎会遍历辅助索引并通过叶级别的指针获得指向聚集索引的主键，然后再通过聚集索引来找到一个完整的行记录。

---

InnoDB存储引擎使用哈希算法来对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列方式。

锁

InnoDB不需要锁升级，因为一个锁和多个锁的开销是相同的

InnoDB行级锁

• 共享锁（S Lock），允许事务读一行数据
• 排他锁（X Lock），允许事务删除或更新一行数据

InnoDB意向锁

• 意向共享锁（IS Lock），事务想要获得一张表中某几行的共享锁
• 意向排他锁（IX Lock），事务想要获得一张表中某几行的排他锁

行锁的三种算法：

• Record Lock：单个行记录上的锁
• Gap Lock：间隙锁，锁定一个范围，但不包含记录本身
• Next-Key Lock：Gap Lock + Record Lock，锁定一个范围，并且锁定记录本身。（目的是为了解决Phantom Problem）

（不可重复读）Phantom Problem是指在同一事务下，连续执行两次同样的SQL语句可能导致不同的结果，第二次的SQL语句可能会返回之前不存在的行。

因为事务隔离性的要求，锁只会带来三种问题：
1、脏读
脏数据是指事务对缓冲池中行记录的修改，并且还没有被提交。（与脏页不同，脏页符合数据一致性）
2、不可重复读
不可重复读是指在一个事务内多次读取同一数据集合。在这个事务还没有结束时，另外一个事务也访问该同一数据集合，并做了一些DML操作。

不可重复读和脏读的区别是：脏读是读到未提交的数据，而不可重复读读到的是已经提交的数据，但是违反了数据库事务一致性的要求。
3、丢失更新
简单来说就是一个事务的更新操作会被另一个事务的更新操作所覆盖。
要避免丢失更新发生，需要让事务在这种情况下的操作编程串行化，而不是并行化操作。即事务A的读取就加一个排他X锁（select for update），事务B的读取也加一个排他X锁（select for update）

InnoDB存储引擎不存在锁升级。因为其不是根据每个记录产生行锁的，相反，其根据每个事务访问的每个页对锁进行管理，采用的是位图的方式。因此不管一个事务锁住页中一个记录还是多个记录，其开销通常都是一致的。

事务

• 原子性（atomicity）
  要么都做，要么都不做
• 一致性（consistency）
  在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏
• 隔离性（isolation）
  该事务提交前对其他事务都不可见
• 持久性（durability）事务一旦提交，其结果就是永久性的

事务可以分为以下几类：

• 扁平事务
  要么都执行，要么都回滚
• 带有保存点的扁平事务
  允许在事务执行过程中回滚到同一事务中较早的一个状态，事务能够回到保存点当时的状态。
  带有保存点的扁平事务，当发生系统崩溃时，所有的保存点都将消失，因为其保存点是易失的，而非持久的。这意味着当进行恢复时，事务需要从开始处重新执行，而不能从最近的保存点继续执行。
• 链事务
  在提交一个事务时，将必要的处理上下文隐式地传给下一个要开始的事务。这意味着下一个事务将看到上一个事务的结果，就好像在一个事务中运行的一样。
• 嵌套事务
  任何事务都在顶层事务提交后才真正的提交
  树中的任何一个事务的回滚会引起其他所有子事务一起回滚
• 分布式事务

事务隔离性：由锁来保证
事务原子性和持久性：由redo log来保证
事务一致性：由undo log来保证

事务的隔离级别：
Read UnCommitted，读未提交
Read Committed，不可重复读
Repeatable Read，可重复读
Serializable，串行化

image.png

InnoDB默认隔离级别是Repeatable Read。
隔离级别越低，事务请求的锁越少或保持锁的时间就越短。

分布式事务：
InnoDB通过XA事务来支持分布式事务的实现。
XA事务由一个或多个资源管理器、一个事务管理器以及一个应用程序组成

image.png

分布式事务使用两阶段提交的方式。