快速查询的秘密武器B+树索引-Part2(聚簇索引、二级索引、联合索引及相关注意事项)

聚簇索引

有两个特点

1. 使用主键值大小进行纪录和页的排序
   包含三个方面

   • 页内的所有纪录(包含使用者纪录与目录项纪录)按照主键值大小形成一个单向链结串列，纪录被划分成多组，且每组主键最大的纪录偏移量会被取出当作槽依序放在页目录中，让我们可以在页目录中快速透过二分法定位到我们要找的指定纪录。
   • 存放使用者纪录的页也是根据纪录主键值大小顺序排成一个双向链结串列
   • 存放目录项纪录的页在同一个阶层也是根据纪录主键值大小顺序排成一个双向链结串列

2. B+树的叶子节点储存的是完整的使用者纪录。所谓的完整使用者纪录就是指这个纪录储存了所有列的值(包含隐藏列)
   这边额外补充说明一下什麽是隐藏列(跟前文无关，知道的人可以略过)。就要提到Innodb的主键生成策略，它会优先使用使用者自订的主键作为主键，如果使用者没有定义主键，则选取一个不允许NULL的UNIQUE值作主键，如果连不允许NULL的UNIQUE值都没有定义，则Innodb会为表预设增加一个名为row_id的隐藏列作为主键。

我们把具有这两个特点的B+树称为聚簇索引，所有完整的使用者纪录都存放在这个聚簇索引的叶子节点。聚簇索引不需要我们在Mysql叙述中显性的使用INDEX叙述去创建（这边不懂没关系，後面会在介绍），Innodb储存引擎会自动替我们创建聚簇索引。

二级索引

大家是否发现，聚簇索引只能在搜寻条件是主键值时发挥作用，原因是B+树中的资料都是按照主键排序的。那如果我们想以别的列作为搜寻条件该怎麽办呢？难道只能从头到尾沿着链结串列依次历遍纪录吗？
当然不是！做法是我们可以多建几棵B+树，不同的B+树采用不同的排序规则。

举个例子：
我们可以只用c2列数值做资料页
那这个B+树跟前面聚簇索引的B+树有那些不同呢？

1. 变成使用c2列的大小进行纪录和页的排序
   包含三个方面

   • 页内的所有纪录(包含使用者纪录与目录项纪录)按照c2列的大小形成一个单向链结串列，纪录被划分成多组，且每组c2列最大的纪录其偏移量会被取出当作槽依序放在页目录中，让我们可以在页目录中快速透过二分法定位到我们要找的c2列等於某个值的纪录。
   • 存放使用者纪录的页也是根据纪录c2列大小顺序排成一个双向链结串列
   • 存放目录项纪录的页在同一个阶层也是根据纪录c2列大小顺序排成一个双向链结串列

2. B+树的叶子节点储存的并不是完整的使用者纪录。只有c2列+c1列(主键)这两个列的值

3. 目录项纪录不再是主键+页号的搭配，而是c2列+页号

这边搜寻的流程也会有些许的不同：

假设我们要找寻纪录c2=4
我们由上而下透过c2=4，使用二分法先定位到目录项，再定位到使用者纪录。
发现使用者纪录内只有c2列跟主键的值，并不是完整的使用者纪录。
所以我们必须再拿主键值回到聚簇索引内去查询完整的使用者纪录，这个过程又叫做回表。

此外由於c2列的值并没有唯一性(主键才有唯一性)，可能会有很多笔纪录符合c2=4，所以我们会从找到的第一笔纪录(c2=4)开始沿着单向链结串列往下找，每找到一笔就进行回表操作。重复这个过程直到不满足c2=4条件停止。

就是因为这种以非主键列的大小排序建立的B+树需要执行回表操作才可以定位到完整的使用者纪录，所以这种B+树才称为二级索引(辅助索引)。

联合索引

我们也可以用多列作排序，就是为多个列建立索引。
比如我们想让B+树按照c2和c3列的大小进行排序，这里面包含两层含义：

1. 先把各纪录和页照c2列排序
2. 在c2列相同的情况下，再采用c3列排序

这棵树每笔目录项纪录就会是由c2列、c3列、页号3个部分组成。
(补充说明一下：前面二级索引是c2列+页号，一样画葫芦，就是c2列、c3列、页号)
而使用者纪录(叶子节点)是由c2列、c3列、c1列(主键)3个部分组成。
这样的B+树就称为联合索引，也称复合索引或多列索引。本质上也是个二级索引。

要特别注意的是
以c2和c3列为排序建立联合索引和分别为c2和c3列建立索引是不同的概念唷！
不同点为
建立联合索引是建立一棵B+树(先按照c2排序，c2相同再用c3排序)
而分别为c2和c3列建立索引，则会分别以c2和c3列为排序建立两棵B+树

Innodb中B+树索引的相关注意事项

1. 根页面是万年不动的
   当我们为某表创建B+树索引时，都会为索引创建一个根节点页。最开始根节点没有任何资料。
   之後开始插入使用者纪录会先把其储存到根节点，当根节点的可用空间用完时，如还要继续插入新纪录，这时会把先根节点内的所有纪录复制到新页A，然後对这个页面进行页分裂(如果不清楚可以回前一篇复习)操作，得到另一个新页B。然後再往下继续插入，新纪录会根据键值(聚簇索引中的主键值，或二级索引中对应索引列的值)大小插入到页A或页B中。此时根节点便升级为储存目录项纪录的页(还记得第一层是使用者纪录层，第二层含以上都是目录项纪录层唷)，此时也需把页A和页B对应的目录项纪录插入到根节点中。
   这边要注意的是B+树索引根节点自创建日便再也不移动(页号再也不改变)。

2. 内节点中目录项纪录的唯一性
   我们知道搜寻非主键值以外的列时，我们会建立二级索引，而二级索引的目录项纪录是索引列(c2)加页号，但这样会有问题。
   举个例子：
   有一目录项页面，内有2笔目录项纪录( [c2:1,页号:1] 跟 [c2:1,页号:2] )，c2的值都为1，分别对应到第1页与第2页。
   这时欲插入一笔新纪录[c2:1]
   原先我们透过二分法，用c2=1去查询属於那一目录项，进而知道要插入到那页(第1页或第2页)
   但现在发现c2的值与原先的2笔纪录一样@@，我们就不知道要插入到那一页了...
   因此为了让新插入的纪录能找到自己属於那一页，我们就需要保证B+树同一层内节点的目录项纪录，除了页号这个栏位以外是唯一的。
   二级索引内节点的目录项纪录从原先的索引列(c2)加页号，追加主键值变成索引列(c2)加c1(主键值)加页号
   这样即可确保搜寻到唯一一笔目录项纪录。

耶！take a break
接下来我们会具体说明该如何使用B+树索引，敬请期待