7、索引

0

数据行

最小主键=1

字段

2

id=4

最小主键=4

指针

数据页

索引的物理存储结构，采用跟数据页一样的页结构来存储，一个索引就是很多页组成的一颗B+树

链表指针

联合索引的运行原理也是一样的，只不过是建立一颗独立的B+树，叶子节点的数据页里放了id+name+age，然后默认按照name排序，name一样就按照age排序，不同数据页之间的name+age值的排序也如此

id=1

页分裂过程

索引页35

id=6

索引页60

比如插入数据的时候一方面把数据插入到聚簇索引的叶子节点的数据页中，同时维护好聚簇索引另一方面会为其他字段建立的索引，重新再建立一颗B+树

name

id=2

id=3

最小主键=58

索引页59

索引页88

id=5

数据页8

索引页号=20

查询：1、先根据非主键索引字段值在其索引B+树中找2、找到叶子节点，也就是对应的主键值3、回表，查询所有字段

页号=2

数据页2

最小name值

页号=8

页号=65

槽位

如果一颗大的B+树索引数据结构里，叶子节点就是数据页自己本身，那么此时就可以称这颗B+树索引为聚簇索引最下层的索引页都是会有指针指向引用的数据页一个层级内的索引页互相之间都是基于指针组成双向链表所有的索引页+数据页组成的B+树就是聚簇索引

索引页20

下图 第一个数据页里有1、5、6三条数据，第二个数据页里有2、3、4三条数据明显第二个数据页里的数据的主键值比第一个数据页里的5和6两个主键都小

主键

每个数据页里都会有一个页目录页目录里面根据数据行的主键存放了一个目录，同时数据行是被分散存储到不同的槽位里去的故每个数据页的目录里，就是这个页里每个主键跟所在槽位的映射关系

基于主键的索引是如何设计的

上述总结：1、在InnoDB存储引擎里，对数据增删改，就是直接把数据页放在聚簇索引里的，聚簇索引就包含了数据2、如果数据页进行页分裂，此时会调整各个数据页内部的行数据，保证数据页内的主键值都是有顺序的，下一个数据页的所有主键值大于上一个数据页的所有主键值3、在页分裂的时候，会维护上层索引数据结构，在上层索引页里维护索引条目，不同的数据页和最小主键值4、如果数据页越来越多，一个索引页放不下，此时就会再拉出新的索引页，同时再弄一个上层的索引页，上层索引页里存放的索引条目就是下层索引页页号和最小主键值5、以此类推，若数据量越大，此时可能就会多出更多的索引页层级来，不过一般索引页里可以放很多索引条目，所以通常而言，即使是亿级的大表，基本上大表里建的索引的层级也就三四层而已6、聚簇索引默认是按照主键来组织的，所以在增删改数据的时候，一方面会更新数据页，一方面会自动维护B+树结构的聚簇索引，新增和更新索引页，聚簇索引是默认就会建立的

索引页28

非聚簇索引二级索引

索引页46

当数据有几百万、几千万等大量数据时，会有大量的数据页，此时也会有很多索引页就会增加索引层级，在更高阶的索引层级保存每隔索引页和索引页中的最小主键值

最小主键=57

索引页号=28

为表的主键建立起来索引之后，其实这个主键的索引就是一颗B+树，然后当要根据主键来查数据的时候，直接就是从B+树的顶层开始二分查找，一层一层往下定位，最终一直定位到一个数据页里，在数据页内部的目录里二分查找，找到那条数据

主键目录（索引页）

指向

页目录

数据进入数据页中，在数据页内部会组成一个单向链表第一行是起始行，行类型为2，表示最小的一行；然后有一个指针指向下一行数据；每一行数据都有自己每个字段的值。普通数据行的类型为0最后一行的类型为3

针对其他字段建立索引，比如name、age之类的字段，原理相同

根据name字段的索引B+树找到主键之后，还要根据主键去聚簇索引里找，所以一般把这种普通字段的索引称之为二级索引，一级索引就是聚簇索引，这就是普通字段的索引的运行原理

类似select * from table where name='xx这种查询语句回表：需要根据主键值，再到聚簇索引里从根节点开始，一路找到叶子节点的数据页，定位到主键对应的完整数据行

若最顶层的那个索引页里存放的下层索引页的页号也太多了此时可以再次分裂，再加一层索引页

假设要查找id=46的数据1、直接先到最顶层的索引页35里去找2、通过二分查找可以定位到下一步应该到索引页20里去找3、到索引页20里通过二分查找定位，定位到数据应该在数据页2里4、进入数据页2里，就可以找到id=46的那行数据了

页号=58

最小主键=70

以name字段建索引为例

叶子节点数据页，但是数据页里仅仅放主键字段和name字段

如何根据主键索引查询根据主键目录去搜索比如要找id=3的数据，此时就会跟每个数据页的最小主键来比，首先id=3大于数据页2里的最小主键值1，小于了数据页8里的最小主键值4。所以直接就可以定位到id=3的数据一定是在数据页2里的假设有很多的数据页，在主键目录里就会有很多的数据页和最小主键值，此时完全可以根据二分查找的方式来找id到底在哪个数据页里

索引的页存储物理结构，是如何用B+树来实现的

索引页中存放的是下一层页号和最小name字段的值

3

假设不停的在表里插入数据，那么就不停的在一个数据页插入数据，数据越来越多，此时就要再弄一个数据页索引运作的一个核心基础就是要求后一个数据页的主键值都大于前面一个数据页的主键值（如果主键是自增的，可以保证这一点，但有的主键并不是自增长的，所以可能会出现后一个数据页的主键值里，有的主键是小于前一个数据页的主键值的）会出现一个过程叫做页分裂，在增加一个新的数据页的时候，实际上会把前一个数据页里主键值较大的，挪动到新的数据页里来，然后把新插入的主键值较小的数据挪动到上一个数据页里去，保证新数据页里的主键值一定都比上一个数据页里的主键值大。

聚簇索引

把每个数据页的页号和数据页里最小的主键值放在一起，组成一个索引的目录

包含页目录

进行页分裂的行为把新数据页里的两条数据挪动到上一个数据页上一个数据页里挪两条数据到新数据页里去