老生常谈：如何在MySQL中查找数据

页的组成部分

数据库中表的数据被划分为若各个页(page),每个页中又存储了很多行记录，而我们往MySQL中插入的每行记录就放到页当中的行记录中,InnoDB的页分为以下几个部分

InnoDB的页被划分为了7个部分，有的部分大小是确定的，有的部分不确定，各个部分说明如下

File Header，表⽰页的⼀些通⽤信息，占固定的38字节。
Page Header，表⽰数据页专有的⼀些信息，占固定的56个字节。
Infimum + Supremum，两个虚拟的伪记录，分别表⽰页中的最⼩和最⼤记录，占固定的26个字节。
User Records：真实存储我们插⼊的记录的部分，⼤⼩不固定。
Free Space：页中尚未使⽤的部分，⼤⼩不确定。
Page Directory：页中的某些记录相对位置，也就是各个槽在页⾯中的地址偏移量，⼤⼩不固定，插⼊的记录越多，这个部分占⽤的空间越多。
File Trailer：⽤于检验页是否完整的部分，占⽤固定的8个字节。

在页的7个组成部分中，我们⾃⼰存储的记录会按照我们指定的⾏格式存储到User Records部分。但是在⼀开始⽣成页的时候，其实并没有User Records这个部分，每当我们插⼊⼀条记录，都会从Free Space部分，也就是尚未使⽤的存储空间中申请⼀个记录⼤⼩的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使⽤完了，如果还有新的记录插⼊的话，就需要去申请新的页了。

我们往User Records部分插入记录的时候，是直接在现有行的末尾(在顶部可用空间部分)或者删除行留下空间的任何地方插入，而并不是按照主键顺序插入新行(设计到大量数据的移动)。

删除一条数据的时候mysql并不会马上将其中的数据回收，而是将这条记录置为已删除，下次插入新数据的时候就会重用这部分空间
但是为了更好的管理页中的记录,MySQL保证了页中的记录在逻辑上是有序的，这是如何做到的呢？

行记录格式中有一个next_record字段,它表⽰从当前记录的真实数据到下⼀条记录的真实数据的地址偏移量。⽐⽅说第⼀条记录的next_record值为32，意味着从第⼀条记录的真实数据的地址处向后找32个字节便是下⼀条记录的真实数据。

关于行格式可以参见我的上一篇文章

如果你熟悉数据结构的话，就⽴即明⽩了，这其实是个链表，可以通过⼀条记录找到它的下⼀条记录。但是需要注意注意再注意的⼀点是，下⼀条记录指得并不是按照我们插⼊顺序的下⼀条记录，⽽是按照主键值由⼩到⼤的顺序的下⼀条记录。

⽽且规定 Infimum记录（也就是最⼩记录）的下⼀条记录就是本页中主键值最⼩的⽤户记录，⽽本页中主键值最⼤的⽤户记录的下⼀条记录就是 Supremum记录（也就是最⼤记录），为了更形象的表⽰⼀下这个next_record起到的作⽤，我们⽤箭头来替代⼀下next_record中的地址偏移量

同时无论增删改任何一个操作，mysql都会保证这个链表的数据是自增的。

页目录

当我们在一个页中查询数据的时候只用从最小记录开始往后遍历就能找到我们需要的记录了，但是如果一个页中记录数少还好，如果数据比较多，这样查找下来就比较耗费性能了，mysql当然不会这么干。

我们平常想从⼀本书中查找某个内容的时候，⼀般会先看⽬录，找到需要查找的内容对应的书的页码，然后到对应的页码查看内容。InnoDB为我们的记录也制作了⼀个类似的⽬录，他们的制作过程是这样的

将所有正常的记录（包括最⼤和最⼩记录，不包括标记为已删除的记录）划分为⼏个组
每个组的最后⼀条记录（也就是组内最⼤的那条记录）的头信息中的n_owned属性表⽰该记录拥有多少条记录，也就是该组内共有⼏条记录。
将每个组的最后⼀条记录的地址偏移量单独提取出来按顺序存储到靠近⻚的尾部的地⽅

这个地⽅就是所谓的Page Directory，也就是⻚⽬录（此时应该返回头看看页⾯各个部分的图）。页⾯⽬录中的这些地址偏移量被称为槽（英⽂名：Slot）或者目录槽，所以这个页⾯⽬录就是由槽组成的。

从这个图中我们需要注意这么⼏点：

现在⻚⽬录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是112，代表最⼤记录的地址偏移量（就是从页⾯的0字节开始数，数112个字节；槽0中的值是99，代表最⼩记录的地址偏移量。
注意最⼩和最⼤记录的头信息中的n_owned属性最⼩记录的n_owned值为1，这就代表着以最⼩记录结尾的这个分组中只有1条记录，也就是最⼩记录本⾝。最⼤记录的n_owned值为5，这就代表着以最⼤记录结尾的这个分组中只有5条记录，包括最⼤记录本⾝还有我们⾃⼰插⼊的4条记录。

现在我们就可以二分法查找页中的记录了。

比如我想查id=4的数据,怎么查呢？现在有2个slot,分别是0和1,所以设 low = 0, high = 1。

mid = (low + high) /2, 此时mid=0,查看 slot0对应记录的主键值是最小值，所以 high不变，low = 1
按照第一步公式重新计算mid=1,此时查看slot1对应主键值为supremum,大于我们要查找的主键4,因此数据肯定在slot1这个分组中
现在我们只需要从slot1中最小的记录开始遍历链表即可找到我们要的那条数据了。由于slot都是挨着的，所以slot0的下一条数据就是slot1中最小的那条数据，我们就从这条数据开始遍历就行了。

为了效率，每个slot组中的记录数并不会太多，关于分组，innodb有这样的规则

对于最⼩记录所在的分组只能有 1 条记录，最⼤记录所在的分组拥有的记录条数只能在1到8条之间，剩下的分组中记录的条数范围只能在4到8条之间。

所以分组是按照下边的步骤进⾏的：初始情况下⼀个数据页⾥只有最⼩记录和最⼤记录两条记录，它们分属于两个分组。之后每插⼊⼀条记录，都会从⻚⽬录中找到主键值⽐本记录的主键值⼤并且差值最⼩的槽，然后把该槽对应的记录的n_owned值加1，表⽰本组内又添加了⼀条记录，直到该组中的记录数等于8个。

在⼀个组中的记录数等于8个后再插⼊⼀条记录时，会将组中的记录拆分成两个组，⼀个组中4条记录，另⼀个5条记录。这个过程会在⻚⽬录中新增⼀个槽来记录这个新增分组中最⼤的那条记录的偏移量。

为了能得到⼀个数据页中存储的记录的状态信息，⽐如本页中已经存储了多少条记录，第⼀条记录的地址是什么，页⽬录中存储了多少个槽等等，特意在页中定义了⼀个叫Page Header的部分，它是⻚结构的第⼆部分，这个部分占⽤固定的56个字节，专门存储各种状态信息，包括但不限于以下内容

页目录中槽数量
还未使⽤的空间最⼩地址，也就是说从该地址之后就是Free Space
本页中的记录的数量（包括最⼩和最⼤记录以及标记为删除的记录）
第⼀个已经标记为删除的记录地址（各个已删除的记录通过next_record也会组成⼀个单链表，这个单链表中的记录可以被重新利⽤）
已删除记录占⽤的字节数
最后插⼊记录的位置
该页中记录的数量（不包括最⼩和最⼤记录以及被标记为删除的记录）
当前页在B+树中所处的层级
索引ID，表⽰当前页属于哪个索引

从这些记录的内容可以看出来，页中的状态值以及属性值还是蛮多的，它们占用固定的大小，可见为了充分利用内存，大佬们费了多少心。

File Header(文件头部)

File Header针对各种类型的页都通⽤，也就是说不同类型的页都会以File Header作为第⼀个组成部分，它描述了⼀些针对各种页都通⽤的⼀些信息，⽐⽅说这个页的编号是多少，它的上⼀个页、下⼀个页是谁等等。

页的校验和
当前页页号(InnoDB通过页号来可以唯⼀定位⼀个⻚)
上一个页页号
下一个页页号
页面被最后修改时对应的日志序列位置(Log Sequence Number)
页类型
属于哪个表空间

页类型分很多种，比如undo日志页，系统页，索引页，blob页等，我们存放记录的数据页的类型就是所谓的索引⻚。

而通过上一页，下一页,存储数据的页就形成了一个双向链表了。

需要注意的是当一个页已经满了之后，新插入的记录就需要插入到新的页中，由于必须满足下⼀个数据页中⽤户记录的主键值必须⼤于上⼀个页中⽤户记录的主键值的要求，所以插入的过程就会伴随着数据的移动。

假设页A只能插入3条数据(注意实际上能插入很多),分别是1,3,5。现在要插入一条数据4，由于页A已经满了，所以需要将数据插入页B中，由于下一个数据页的主键值必须大于上一页的主键值，所以要现在5这条数据移动到页B中，然后再把4这条数据插入到页A中。

File Trailer(文件尾部)

InnoDB存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以⻚为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了⼀半的时候中断电了咋办，这不是莫名尴尬么？

为了检测⼀个页是否完整（也就是在同步的时候有没有发⽣只同步⼀半的尴尬情况），File Trailer应运而生，这个部分由8个字节组成，可以分成2个⼩部分：

前4个字节代表页的校验和这个部分是和File Header中的校验和相对应的。每当⼀个页⾯在内存中修改了，在同步之前就要把它的校验和算出来，因为File Header在页⾯的前边，所以校验和会被⾸先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的⾸部和尾部的校验和应该是⼀致的。
如果写了⼀半⼉断电了，那么在File Header中的校验和就代表着已经修改过的页，⽽在File Trialer中的校验和代表着原先的页，⼆者不同则意味着同步中间出了错。

后4个字节代表页⾯被最后修改时对应的⽇志序列位置（LSN）这个部分也是为了校验页的完整性的，只不过我们⽬前还没说LSN是个什么意思，所以⼤家可以先不⽤管这个属性。
这个File Trailer与File Header类似，都是所有类型的页通⽤的。

索引

现在我们知道了如何在一个页中快速查找某一条数据,但是如果我们的数据量很大，分散在很多页中，那应该如何查找呢？只能一页一页进行遍历吗？

当然不是，我们同样可以借鉴书本目录的做法，给数据页建立一个索引目录结构。

从图中可以看出来，我们新分配了⼀个编号为30的页来专门存储⽬录项记录。这⾥再次强调⼀遍⽬录项记录和普通的⽤户记录的不同点：

⽬录项记录的record_type值是1，⽽普通⽤户记录的record_type值是0。
⽬录项记录只有主键值和页的编号两个列，⽽普通的⽤户记录的列是⽤户⾃⼰定义的，可能包含很多列，另外还有InnoDB⾃⼰添加的隐藏列。

上面的图中为了简单，隐藏了最大最小记录，没有画出来并不代表没有哈。

虽然说⽬录项记录中只存储主键值和对应的页号，⽐⽤户记录需要的存储空间⼩多了，但是不论怎么说⼀个页只有16KB⼤⼩，能存放的⽬录项记录也是有限的，那如果表中的数据太多，以⾄于⼀个数据页不
⾜以存放所有的⽬录项记录，该咋办呢？当然是再多整⼀个存储⽬录项记录的页

当我们存储的记录越多，那么目录项记录也就越多，存储目录项的页也就越多，好像这就又回到了最初的问题，那又怎么解决呢？还是同样的解法，给这些目录项的页生成一个更高层的目录就行了，就如下图

这样当我们要查询某个值的时候，直接从最顶层开始过滤，然后沿着这个目录结构过滤就行了。

你看看这个结构是不是很熟悉，就是一颗咱们熟悉的树嘛，这个数据结构叫B+树。

不论是存放⽤户记录的数据页，还是存放⽬录项记录的数据页，我们都把它们存放到B+树这个数据结构中了，所以我们也称这些数据页为节点。从图中可以看出来，我们的实际⽤户记录其实都存放在
B+树的最底层的节点上，这些节点也被称为叶⼦节点或叶节点，其余⽤来存放⽬录项的节点称为⾮叶⼦节点或者内节点，其中B+树最上边的那个节点也称为根节点。

上面建立的索引有两个特点

所有数据(包括隐藏列)都存储在叶子节点中(最底层节点)
无论是页内的记录还是页都是按照主键进行排序的

我们把具有这两种特性的B+树称为聚簇索引，所有完整的⽤户记录都存放在这个聚簇索引的叶⼦节点处。InnoDB存储引擎会⾃动的为我们创建聚簇索引。

二级索引

上面的聚簇索引，只有搜索条件是主键的时候才能发挥作用，因为B+树中数据是按照主键进行排序的。如果我有下面的表,给a建立了一个索引，应该如何处理？

CREATE TABLE `test` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a` int(11) NOT NULL,
  `b` char(1) NOT NULL,
  PRIMARY KEY (`id`),
  KEY idx_a(a),
  KEY idx_a_b(a,b)
)

在InnoDB中，会为每个索引都创建一个B+树，排序规则则是按照索引列进行排序的，比如我们根据a建立了一个索引，那么这颗B+树就长这样

这个B+树和上面聚簇索引有几点不同。

页内的记录是按照列a的⼤⼩顺序排成⼀个单向链表。
各个存放⽤户记录的页也是根据页中记录的列a⼤⼩顺序排成⼀个双向链表。
存放⽬录项记录的页分为不同的层次，在同⼀层次中的页也是根据页中⽬录项记录的列a⼤⼩顺序排成⼀个双向链表。
B+树的叶⼦节点存储的并不是完整的⽤户记录，⽽只是列a+主键这两个列的值
⽬录项记录中不再是主键+⻚号的搭配，⽽变成了列a+主键id+⻚号的搭配

目录项记录为什么是列a+主键id+页号，而不是列a+页号呢？

假设我们目录项记录是列a+页号，当我们在插入一条数据（13,4,8)的时候，这条数据应该放入到页36还是页37呢？这两个页中都有a=4的数据呢，innodb也不知道，所以为了为了让新插⼊记录能找到⾃⼰在那个页⾥，我们需要保证在B+树的同⼀层节点的⽬录项记录除⻚号这个字段以外是唯⼀的。因此目录项记录是列a+id+页号。

我们再插⼊记录(13, 4, 8)时，由于⻚35中存储的⽬录项记录是由列a + 主键 + ⻚号的值构成的，可以先把新记录的列a的值和⻚35中各⽬录项记录的列a的值作⽐较，如果列a的值相同的话，可以
接着⽐较主键值，因为B+树同⼀层中不同⽬录项记录的列a + 主键的值肯定是不⼀样的，所以最后肯定能定位唯⼀的⼀条⽬录项记录，在本例中最后确定新记录应该被插⼊到⻚37中。

现在B+树有了，那么我们应该怎么搜索呢？

以查找列a的值为4的记录为例，查找过程如下：

确定⽬录项记录页,根据根⻚⾯，也就是⻚35，可以快速定位到⽬录项记录所在的页为⻚37。
通过⽬录项记录页确定⽤户记录真实所在的页。
在⻚37中可以快速定位到实际存储⽤户记录的页，但是由于列a并没有唯⼀性约束，所以列a值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储⽤户记录的页在⻚36和⻚
37中。
在真实存储⽤户记录的页中定位到具体的记录。到⻚36和⻚37中定位到具体的记录。
但是这个B+树的叶⼦节点中的记录只存储了a和id（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找⼀遍完整的⽤户记录。

根据这个以列a⼤⼩排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据列a的值查找到完整的⽤户记录的话，仍然需要到聚簇索引中再查⼀遍，这个过程也被称为回表。
也就是根据列a的值查询⼀条完整的⽤户记录需要使⽤到2棵B+树！！！

为什么我们还需要⼀次回表操作呢？直接把完整的⽤户记录放到叶⼦节点不就好了么？你说的对，如果把完整的⽤户记录放到叶⼦节点是可以不⽤回表，但是太占地⽅了呀～相当于每建⽴⼀棵B+树都需要把
所有的⽤户记录再都拷贝⼀遍，这就有点太浪费存储空间了。因为这种按照⾮主键列建⽴的B+树需要⼀次回表操作才可以定位到完整的⽤户记录，所以这种B+树也被称为⼆级索引（英⽂名secondary
index），或者辅助索引。

联合索引

当然也可以同时以多个列的⼤⼩作为排序规则，也就是同时为多个列建⽴索引，⽐⽅说我们想让B+树按照a和b列的⼤⼩进⾏排序，这个包含两层含义：

先把各个记录和页按照a列进⾏排序。
在记录的a列相同的情况下，采⽤b列进⾏排序
为a和b列建⽴的索引的⽰意图如下：

联合索引本质也是个二级索引

B+树根页面

每当为某个表创建⼀个B+树索引（聚簇索引不是⼈为创建的，默认就有）的时候，都会为这个索引创建⼀个根节点页⾯。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有⽤户记录，
也没有⽬录项记录。
随后向表中插⼊⽤户记录时，先把⽤户记录存储到这个根节点中。
当根节点中的可⽤空间⽤完时继续插⼊记录，此时会将根节点中的所有记录复制到⼀个新分配的页，⽐如⻚a中，然后对这个新页进⾏⻚分裂的操作，得到另⼀个新页，⽐如⻚b。这时新插⼊的记录根据
键值（也就是聚簇索引中的主键值，⼆级索引中对应的索引列的值）的⼤⼩就会被分配到⻚a或者⻚b中，⽽根节点便升级为存储⽬录项记录的页。

这个过程需要⼤家特别注意的是：⼀个B+树索引的根节点⾃诞⽣之⽇起，便不会再移动。这样只要我们对某个表建⽴⼀个索引，那么它的根节点的页号便会被记录到某个地⽅，然后凡是InnoDB存储引擎需
要⽤到这个索引的时候，都会从那个固定的地⽅取出根节点的页号，从⽽来访问这个索引。

这个固定的地方就是我们之前提到过的数据字典信息

我们平时是以记录为单位来向表中插⼊数据的，这些记录在磁盘上的存放⽅式也被称为⾏格式或者记录格式。InnoDB有4种不同类型的⾏格式，分别是Compact、Redundant、Dynamic和Compressed⾏格式，随着时间的推移，他们可能会设计出更多的⾏格式，但是不管怎么变，在原理上⼤体都是相同的。

MyIsam

InnoDB中聚簇索引叶子节点会包含所有数据，MyISAM索引方案虽然也是使用的树形结果，但是其数据和索引是分开的。

MyISAM将表中的记录按照记录的插⼊顺序单独存储在⼀个⽂件中，称之为数据⽂件。这个⽂件并不划分为若⼲个数据页，有多少记录就往这个⽂件中塞多少记录就成了。我们可以通过⾏号⽽快速访问到⼀
条记录.

myisam行记录格式是static(定长)时，可以通过行号找到数据，如果是变长记录格式时，那么MyISAM会直接在索引叶⼦节点处存储该条记录在数据⽂件中的地址偏移量，可以直接通过这个偏移量找到文件中的数据

由于在插⼊数据的时候并没有刻意按照主键⼤⼩排序，所以我们并不能在这些数据上使⽤⼆分法进⾏查找。
使⽤MyISAM存储引擎的表会把索引信息另外存储到⼀个称为索引⽂件的另⼀个⽂件中。MyISAM会单独为表的主键创建⼀个索引，只不过在索引的叶⼦节点中存储的不是完整的⽤户记录，⽽是主键值 + ⾏号的组合。也就是先通过索引找到对应的⾏号，再通过⾏号去找对应的记录！

这⼀点和InnoDB是完全不相同的，在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进⾏⼀次查找就能找到对应的记录，⽽在MyISAM中却需要进⾏⼀次回表操作，意味着MyISAM中建⽴的索引相
当于全部都是⼆级索引！

如果有需要的话，我们也可以对其它的列分别建⽴索引或者建⽴联合索引，原理和InnoDB中的索引差不多，不过在叶⼦节点处存储的是相应的列 + ⾏号。这些索引也全部都是⼆级索引。

Zhu.Yang