学习《MySQL是怎样运行的》，感谢作者！
概述 #
数据页由7个组成部分，各个数据页可以组成一个双向链表，每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。每个数据页都会为它里面的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。页和记录的关系
页a，页b 可以不在物理结构上相连，只要通过双向链表相关联即可
没有索引时进行查找 #
假设我们要搜索某个列等于某个常数的情况：SELECT [查询列表] FROM 表名 WHERE 列名 = xxx
在一个页中查找 #
假设记录极少，所有记录可以存放到一个页中
- 以主键位搜索条件：页目录中使用二分法快速定位到对应的槽，然后在遍历槽对应分组中的记录，即可快速找到指定记录
- 其他列作为搜索条件：对于非主键，数据页没有为非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。只能从Infimum依次遍历单向链表中的每条记录，然后对比，效率极低
在很多页中查找 #
两个步骤：
- 定位到记录所在的页
- 从所在页内查找相应的记录
没有索引情况下，不能快速定位到所在页，只能从第一页沿着双向链表一直往下找，而如果是主键，每一页则可以在页目录二分查找。
不过由于要遍历所有页，所以超级耗时
索引 #
#例子
mysql> CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY(c1)
) ROW_FORMAT=COMPACT;
完整的行格式
简化的行格式
- record_type：记录头信息的一项属性，表示记录的类型。0：普通记录，2：Infimum记录，3：Supremum记录，1还没用过等会再说
- next_record：记录头信息的一项属性，表示从当前记录的真实数据到下一条记录真实数据的距离
- 各个列的值：这里只展示在index_demo表中的3个列，分别是c1、c2、c3
- 其他信息：包括隐藏列及记录的额外信息
改为竖着查看：
上面图6-4的箭头其实有一点点出入，应该是指向z真实数据第1列那个位置，如下
一个简单的索引方案 #
思考：在根据某个条件查找一些记录，为什么要遍历所有的数据页呢？因为各个页中的记录没有规律，不知道搜索条件会匹配哪些页
思路：为快速定位记录所在的数据页而建立一个别的目录
有序 #
下一个数据页中用户记录的主键值必须大于上一页用户记录的主键值
假设一页只能存放3条记录
#插入3条记录
mysql> INSERT INTO index_demo VALUES(1,4,'u'),(3,9,'d'),(5,3,'y');
Query OK, 3 rows affected (0.02 sec)
Records: 3 Duplicates: 0 Warnings: 0
此时页的情况
记录组成了单链表
再插入一条记录
mysql> INSERT INTO index_demo VALUES(4,4,'a');
Query OK, 1 row affected (0.01 sec)
(注意，页之间可能不是连续的)
由于页10中最大记录是5，而页28中有一条记录是4，因为5>4，不符合下一个数据页中用户记录的主键值必须大于上一页中用户记录的主键值，所以在插入主键值为4的记录时需要伴随着一次记录移动，也就是把5的记录移动到页28中，再把主键值4的记录插入到页10中
这个过程表明，在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程也可以称为页分裂。
给所有的页建立一个目录项 #
前提：index_demo表中有多条记录的效果
1页有16KB，这些页在磁盘上可能并不连续，要想从这么多页中根据主键值快速定位某些记录所在的页，需要给他们编制一个目录，每个页对应一个目录项，每个目录项包括两部分：
- 页的用户记录中最小的主键值，用key表示
- 页号，page_no表示
假设我们此时把目录项在物理存储器上连续存储，比如放到数组中，此时就可以根据主键值快速查找某条记录
先用二分法快速定位主键20的记录在目录项3中（因为12<20<209)，对应页是9
根据前面说的方式在页9中定位具体记录
先在页目录中二分查找，找到对应的组后沿链表遍历
这个目录项的别名：索引
InnoDB中的索引方案 #
上述方案的问题 #
- InnoDB使用页作为管理存储空间的基本单位，即只能保证16KB的连续存储空间，如果记录非常多，则需要的连续存储空间就非常大
- 增删改是很频繁的，如果页28的记录全部移除，那么目录项2就没有出现的必要，即要删除目录项2，那么所有的目录项都需要左移/或者不移动，作为冗余放到目录项列表中，浪费空间
方案 #
复用之前存储用户记录的数据页来存储目录项，用了和用户记录进行区分，把这些用来表示目录项的记录称为目录项记录。如何区分一条记录是普通用户记录，还是目录项记录：使用记录头信息中的record_type属性
- 0：普通用户记录
- 1：目录项记录
- 2：Infimum记录
- 3：Supremum记录
将目录项放到数据页中
新分配了一个编号为30的页来专门存储目录项记录
目录项记录和普通的用户记录的不同点
目录项记录的record_type值为1，普通用户记录record_type值为0
目录项记录只有主键值和页的编号这两个列，而普通用户记录的列是用户自己定义的，可能包含许多列，另外还有InnoDB自己添加的隐藏列
记录头信息中有一个名为min_rec_flag的属性，只有目录项记录的min_rec_flag属性才可能为1，普通记录的min_rec_flag属性都是0
B+ 树中每层非叶子节点中的最小的目录项记录都会添加该标记
其他：
它们用的是一样的数据页(页面类型都是Ox45BF ，这个属性在File Header 中)；页的组成结构也是一样的〈就是我们前面介绍过的7 个部分)；都会为主键值生成Page Directory（页目录）从而在按照主键值进行查找时可以使用
二分法来加快查询速度。
举例 #
单个 目录项记录页 #
其中，页30中存储的主键值分别为1，5，12，209
假设我们现在要查找主键值为20的记录：
- 先到存储目录项记录的页（这里是页30）中，（由于有页目录）通过二分法快速定位到对应的目录项记录，因为12<20<209，所以定位到对应的用户记录所在的页就是页9
- 再到存储用户记录的页9中根据二分法（由于有页目录））快速定位到主键值为20的用户记录
目录项记录中只存储主键值和对应的页号，存储空间极小，但一个页只有16KB，存放的目录项记录有限。如果表中数据太多（页太多），以至于一个数据页不足以存放所有的目录项记录
多个 目录项记录的页 #
解决方案：新增一个存储目录项记录的页
此时再进行查找
- 确定存储目录项记录的页
现在存储目录项记录的页有2个，即页30和页32。又因为页30表示的目录项记录主键值范围是**[1，320)，页32表示的目录项记录主键值范围 > 320。所以确定主键值为20的记录对应的目录项记录**在页30中 - 按照单个 目录项记录页的方案查找
多个目录项记录页 #
如果数据再增加，则再生成存储更高级目录项记录的数据页
无论是存放用户记录的数据页，还是存放目录项记录的数据页，都放到B+树数据结构中，我们也将这些数据页称为B+树的节点
如图，我们真正的用户记录其实都存放在B+树最底层的节点上，这些节点也称为叶子节点或页节点，其余用来存放目录项记录的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点
这里我们规定，最下面那层（存放用户记录的那层）为0层，之后层级依次往上加。
这里我们假设所有存放用户记录的叶子节点所代表的数据页可以存放100条用户记录（16KB=16 * 1024 ≈10000 字节，差不多一条记录100字节），假设所有存放目录项记录的内节点所代表的数据页可以存放1000条目录项记录（10000字节，假设1个目录项10字节），那么如果
- 如果B+树有1层，那么只有一个用于存放用户记录的节点，那么能存放100条用户记录（1百）
- 如果B+树有2层，那么能存放 1000 * 100=100,000条用户记录(10万)
- 如果B+树有3层，那么能存放 1000 * 1000 * 100=100,000,000条用户记录(1亿)
- 如果B+树有4层，那么能存放 1000 * 1000 * 1000 * 100=100,000,000,000条用户记录 (1000亿)
所以一般情况下，我们用到的B+树不会超过4层。
当我们要通过主键值查找**某条记录 **
- 最多只需要进行4个页面内的查找（查找3个存储目录项记录的页和1个存储用户记录的页）
- 每个页面内存在PageDirectory（页目录），所以在页面内也可以通过二分法快速定位记录
PageHeader中，有一个名为PAGE_LEVEL的属性，代表着这个数据页作为节点在B+树中的层级
聚簇索引 #
前面介绍的B+树本身就是一个记录，或者说本身就是一个索引，有以下两个特点
- 使用记录主键值的大小进行记录和页的排序
- 页（包括叶子节点和内节点）内的记录，按照主键大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中主键值最大的记录在页内的偏移量会被当作槽一次存放在页目录中（Supremum记录比任何用户记录都大）之后可以在页目录中通过二分法快速定位到主键列等于某个值的记录
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
- 存放目录项记录的页分为不同的层级，在同一层级中也是根据页目录项记录的主键大小顺序排成一个双向链表
- B+树的叶子节点存储的是完整的用户记录（指的是这个记录中存储了所有列的值（包括隐藏列））
具有上面两个特点的B+树称为聚簇索引。所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引，不需要我们在MySQL语句中显示使用INDEX语句去创建，InnoDB会自动为我们创建聚簇索引
InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点）。索引即数据，数据即索引
二级索引 #
聚簇索引只能在搜索条件是主键值时才发挥作用，如果要以别的列作为搜索条件，可以多建几颗B+树，而且不同B+树中的数据，采用不同的排序规则
比如用c2列的大小作为数据页、页中记录的排序规则，再建一颗B+树
“前言：c1已经是主键了”
#例子 mysql> CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1) ) ROW_FORMAT=COMPACT;
下面是聚簇索引特点：
二级索引说明：
- 使用记录c2列的大小进行记录和页的排序
- 页（包括叶子节点和内节点）内的记录，按照c2列大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中c2列值最大的记录在页内的偏移量会被当作槽一次存放在页目录中（Supremum记录比任何用户记录都大）之后可以在页目录中通过二分法快速定位到c2列值等于某个值的记录
- 各个存放用户记录的页也是根据页中用户记录的c2列大小顺序排成一个双向链表
- 存放目录项记录的页分为不同的层级，在同一层级中也是根据页目录项记录的c2列大小顺序排成一个双向链表
- B+树的叶子节点存储的是并不是完整的用户记录，而只是c2列+主键这两个列的值
- 目录项记录中不再是主键+页号的匹配，而变成了c2列+页号的搭配
B+树如下
举例 #
假设要查找c2=4的记录，可以使用上面的B+树。由于c2没有唯一性约束，所以可能会有很多条：我们只需要在该B+树的叶子节点处定位到第一条满足搜索条件c2=4的那条，然后由记录组成的单向链表一直向后扫描即可。另外，各个叶子节点组成了双向链表，搜索完了本页面的记录后可以顺利跳到下一个页面中的第一条记录，然后沿着记录组成的单向链表向后扫描
查找过程 #
确定第一条符合c2=4条件的目录项记录所在的页
根据**根页面（44）**可以快速定位到第一条符合c2=4条件的目录项记录所在页为页42（因为2<4<9)
通过第一条符合c2=4条件的目录项记录所在的页面确定第一条符合c2=4条件的用户记录所在的页
根据页42可以快速定位（通过页目录）到第一条符合条件的用户记录所在页为34或35，因为2<4<=4
在真正存储第一条符合c2=4条件的用户记录的页中定位到具体的记录
页34和页35中定位到具体的用户记录（如果页34使用页目录定位到第一条符合条件的用户记录，就不需要再到35中去再定位，因为直接一直往后查找到不等的记录即可）
由于这个B+树的叶子节点的记录只存储了c2和c1（即主键）两个列。在叶子节点定位到第一条符合条件的那条用户记录之后，我们需要根据该纪录中的主键信息，到聚簇索引中查找到完整的用户记录，这个通过携带主键信息到聚簇索引中重新定位完整的用户记录的过程也称为回表 。
然后再返回到这棵B+ 树的叶子节点处，找到刚才定位到的符合条件的那条用户记录，并沿着记录组成的单向链表向后继续搜索其他也满足c2=4的记录**，每找到一条的话就继续进行回表操作。重复这个过程，直到下一条记录不满足c2 =4**的这个条件为止.
如果把完整的用户记录放到叶子节点是可以不用回表，但是太占地方了
因为这种以非主键列的大小为排序规则而建立的B+ 树需要执行回表操作才可以定位到完整的用户记录，所以这种B+ 树也称为二级索引(Secondary Index) 或辅助索引。由于我们是以c2 列的大小作为B+ 树的排序规则，所以我们也称这棵B+ 树为为c2 列建立的索引，把c2列称为索引列。二级索引记录和聚簇索引记录使用的是一样的记录行格式，只不过二级索引记录存储的列不像聚簇索引记录那么完整。
把聚簇索引或者二级索引的叶子节点中的记录称为用户记录。为了区分，也把聚簇索引叶子节点中的记录称为完整的用户记录，把二级索引叶子节点中的记录称为不完整的用户记录
如果为一个存储字符串的列建立索引，别忘了前面说的字符集和比较规则，字符串也是可以比较大小的
联合索引 #
同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，含义：
- 先把各个记录和页按照c2列进行排序
- 记录的c2列相同的情况下，再采用c3进行排序
每条目录项记录都由c2列、c3列、页号这3个部分组成。各条记录先按照c2列的值进行排序。如果记录的c2列相同，则按照c3列的值进行排序
这里说的是极特殊的情况，也就是c2列相同的记录有很多很多条，导致好几个页都有c2 = x的记录，而且其中c3列的值还不同，那么就会出现目录项记录页中的目录项c2相同而c3不相同
B+树叶子节点处的用户记录由c2列、c3列、和主键c1列组成
以c2 和c3 列的大小为排序规则建立的B+ 树称为联合索引，也称为复合索 引或多列索引。它本质上也是一个二级索引，它的索引列包括c2、c3.需要注意的是"以c2和c3列的大小为排序规则建立联合索引“和”分别为c2和d 列建立索引" 的表述是不同的， 不同点如下：
- 建立联合索引只会建立如图6-15 所示的一棵B+ 树
- 为c2 和c3 列分别建立索引时，则会分别以c2 和c3 列的大小为排序规则建立两棵B+ 树
Inno中B+树索引的注意事项 #
根页面万年不动窝 #
前面为了理解方便，我们先把存储用户记录的叶子节点都画出来，然后再画出存储目录项记录的内节点。而实际上是这样的：
- 每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就存在）时，都会为这个索引创建一个根节点页面。
一开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录 - 随后向表中插入用户记录时，先把用户记录存储到这个根节点中
- 当根节点可用空间用完时，继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页（比如页a）中，然后对这个新页进行页分裂操作，得到另一个新页（比如页b）[因为一个页放不下，所以还要这个新页]。这时新插入的记录会根据键值（也就是聚簇索引中的主键值，或者二级索引中对应的索引列的值）的大小分配到页a或者页b。根节点此时，便升级为存储目录项记录的页，也就需要把页a和页b对应的目录项记录插入到根节点中
在这个过程中，需要特别注意的是， 一个B+ 树索引的根节点自创建之日起便不会再移动(也就是页号不再改变)。
由于这个特性，只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，后续凡是InnoDB引擎需要用到这个索引，会从那个固定的地方取出根节点的页号，从而访问这个索引
“存储某个索引的根节点在哪个页面中”，就是传说中的数据字典中的一项信息
这里还有一个问题，书上没说，就是根节点作为a，b页的存储目录项记录的页，一旦后面页越来越多，根节点放不下了，接下来
我猜是这样的，也是再新分配一个页X，然后对页X页分裂，得到页Y。把根节点此时的所有目录项全复制到页X，然后新插入的目录项记录根据键值分配到页X，或Y，然后根节点又变为存储目录项记录的页
内节点中目录项记录的唯一性 #
目前为止，我们说B+树索引的内节点中，目录项记录的内容是索引列加页号的搭配，但是这个搭配对二级索引来说有点儿不太严谨。以下面这个表为例（c1是主键，c2是二级索引）
| c1 | c2 | c3 |
|---|---|---|
| 1 | 1 | ‘u’ |
| 3 | 1 | ’d' |
| 5 | 1 | ‘y’ |
| 7 | 1 | ‘a’ |
如果二级索引中，目录项记录的内容只是索引列+页号的匹配，那么为c2列建立索引后的B+树如下图6-16
如果此时再插入一条记录 c1=9，c2=1，c3=‘c’，那么在修改为c2列建立的二级索引对应的B+树时：由于页3中存储的目录项记录由c2列+页号构成，页3中两条目录项记录对应的c2列都是1，而新插入的这条记录中，c2列也是1，那么这条新插入的记录应该放在页4还是页5？
为了保证B+树同一层内节点的目录项记录除了页号这个字段以外是唯一，所以二级索引的内节点的目录项记录内容实际上由3部分构成： 索引列的值，主键值，页号 ，如上图6-17
插入记录（9，1，’c’）时，由于页3 中存储的目录项记录是由c2 列+ 主键+页号构成的， 因此可以先把新记录的c2 列的值和页3 中各目录项记录的c2 列的值进行比较， 如果c2 列的值相同，可以接着比较主键值。因为B+ 树同一层中不同目录项记录的c2 列+主键的值肯定是不一样的，所以最后肯定能定位到唯一的一条目录项记录。 在本例中， 最后确定新记录应该插入到页5 中
对于二级索引，先按照二级索引列的值进行排序，如果相同，再按照主键值进行排序。所以，为c2列建立索引，相当于为（c2，c1）列建立了一个联合索引。另外，对于唯一二级索引来说（当我们为某个列或列组合声明UNIQUE属性时，便会为这个列或组合建立唯一索引），也可能出现多条记录键值相同的情况（1. 声明为UNIQUE的列可能存储多个NULL 2. 后面要讲的MVCC服务），唯一二级索引的内节点的目录项记录也会包含记录的主键值
注意，书上没有讲到删除的情况，也就是假设有一种情形：索引值1的行被删了，后面又重新添加了。我的理解是不会出现两条索引值一样的记录在树上（根据前面记录行的delete_flag，有可能重复，但是我猜会覆盖掉，所以这里没讲到那个情况，暂时没找到资料证明）
一个页面至少容纳2条记录 #
如果一个大的目录中只存放一个子目录，那么目录层级会非常多，而且最后那个存放真正数据的目录中只能存放一条记录
如果让B+树的叶子节点只存储一条记录，让内节点存储多条记录，也还是可以发挥B+树作用的。为了避免B+树的层级增长过高，要求所有数据页都至少可以容纳2条记录（也就是说，会极力避免因为列值过大、或者过多导致容纳不了2条记录）
InnoDB对列的数量有所限制，而如果在最大限制下，结合04章的结论：
如果一条记录的某个列中存储的数据占用字节数非常多，导致一个页没有办法存储两条记录，该列就可能会成为溢出列
MyISAM中的索引方案简介 #
为了内容完整性，介绍一下MyISAM存储引擎中的索引方案
InnoDB中，索引即数据，也就是聚簇索引的那颗B+树的叶子节点中包含了完整的用户记录。MyISAM虽然也是树形，但是索引和数据是分开的
数据文件 #
表中的记录按照记录的插入顺序单独存储在一个文件中（称之为数据文件）
该文件不划分若干个数据页，有多少记录就往文件中塞多少。通过行号快速访问到一条记录
MyISAM记录需要记录头信息来存储额外数据，以index_demo表为例，看一下这个表在使用MyISAM作为存储引擎时，它的记录如何在存储空间表示
由于是按插入顺序，没有按主键大小排序，所以不能在这些数据上使用二分法
索引 #
MyISAM存储引擎会把索引信息单独存储到另一个文件中（即索引文件）
MyISAM会为表的主键单独创建一个索引，只不过在索引的叶子节点中存储的不是完整用户记录，而是主键值与行号的结合。即先通过索引找到对应的行号，再通过行号去找对应的记录
与InnoDB不同，InnoDB存储隐情中，只需根据主键值对聚簇索引进行依次查找就能找到对应记录，而MyISAM中却需要进行一次回表操作。意味着MyISAM中建立的索引相当于都是二级索引
其他索引 #
可以为其他列分别建立索引或者建立联合索引，原理与InnoDB差不多，只不过叶子节点存储的是相应的列+行号（InnoDB中存储的则是主键）。这些索引也都是二级索引。
MyISAM行格式有定长记录格式Static、变长记录格式Dynamic、压缩记录格式 Compressed。图6-18就是定长记录格式，即一条记录占用的存储空间是固定的，这样就可以使用行号轻松算出某条记录在数据文件中的地址偏移量，但是变长记录格式就不行乐，MyISAM会直接在索引叶子节点处存储该记录在数据文件中的偏移量。==> MyISAM回表快速，因为是拿着地址偏移量直接到文件中取数据。而InnoDB则是获取主键后，再去从聚簇索引中查找。
总结 #
InnoDB：索引即数据
MyISAM：索引是索引，数据是数据
MySQL中创建和删除索引的语句 #
InnoDB会自动为主键或者**带有UNIQUE **属性的列建立索引
InnoDB不会自动为每个列创建索引，因为每建立一个索引都会建立一颗B+树，且增删改都要维护各个记录、数据页的排序关系，费性能和存储空间
#语法
CREATE TABLE 表名(
各个列的信息...,
(KEY|INDEX) 索引名 (需要被索引的单个列或多个列);
)
#修改表结构
ALTER TABLE 表名 ADD (INDEX|KEY) 索引名 (需要被索引的单个列或多个列);
#修改表结构的时候删除索引
ALTER TABLE 表名 DROP (INDEX|KEY) 索引名;
实例：
mysql> CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY (c1),
INDEX idx_c2_c3 (c2,c3)
);
#查看建表语句
mysql> SHOW CREATE TABLE index_demo;
+------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table |
+------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| index_demo | CREATE TABLE `index_demo` (
`c1` int(11) NOT NULL,
`c2` int(11) DEFAULT NULL,
`c3` char(1) DEFAULT NULL,
PRIMARY KEY (`c1`),
KEY `idx_c2_c3` (`c2`,`c3`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 |
+------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)