数据库索引底层数据结构之B+树MySQL中的页索引分类【纯理论干货，面试必备】

1、索引简介

1.1 什么是索引

1.2 使用索引的原因

2、索引中数据结构的设计 —— B+树

2.1 哈希

2.2 二叉搜索树

2.3 B树

2.4 最终选择之——B+树

2.4.1 B树与B+树的对比(面向索引)【面试题】

3、MySQL中的页

3.1 页的使用原因

3.2 页的结构

3.2.1 页文件头和页文件尾

3.2.2 页主体

3.2.3 页目录

3.2.4 数据页头

4、B+树在MySQL索引上的应用

4.1 三层树高的B+树的数据存储量(理论上)

5、索引的分类

5.1 主键索引

5.2 普通索引

5.3 唯一索引

5.4 全文索引（了解）

5.5 聚集索引

5.6 二级索引/非聚集索引

5.7 索引覆盖

1、索引简介

1.1 什么是索引

MySQL中的索引是一种数据结构，它可以高效快速的查询、更新相应数据，大大的提高开发效率。索引通过⼀定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度。

我们可以将索引理解为书中的目录，可以根据目录快速的锁定到我们要阅读的页数。

1.2 使用索引的原因

数据库之所以叫数据库，那么MySQL的设计必然需要满足两个需求：

安全
效率

显而易见，使用索引的原因只有一个：提高查询效率。

2、索引中数据结构的设计 —— B+树

索引的出现就是为了提高查找效率，那它底层到底使用的是哪种高效的数据结构呢？让我们继续探索。

2.1 哈希

说到高效查找，相比大家第一个想到的就是哈希表，因为它的时间复杂度可以达到O(1)级别，可谓是极其高效，正因为其高效的查找性能也使哈希成为最重要的数据结构，没有之一。但是由于哈希只能一个数据一个数据的查找，不具备范围查找的功能，故索引并没有使用哈希作为它的底层结构。

2.2 二叉搜索树

二叉搜索树中序遍历得到的是一个有序序列，这使得其具备范围查找的功能。

但是，二叉搜索树在极端情况下可能为退化成一棵单分支树，时间复杂度也会退化为O(N)。

并且在数据过多的情况下，无法控住树高，由于数据库上的数据是在磁盘上保存的，而每访问一个节点都会发生一次磁盘IO，磁盘的访问速度是很慢的，所以当搜索二叉树出现单分支形态时，将严重拉低数据库性能。

由此得出：磁盘IO是制约数据库性能的主要因素。【拓展】

故索引也没有使用二叉搜索树作为它的底层结构。

2.3 B树

B树仍具备中序遍历序列有序的特点，在B树中，每个节点可以有多个子节点(可以超过2个)。对于N阶B树(度/阶)，一般来说其子节点个数不可>=N个，当插入的节点为第N个孩子时，将开辟另一条分支。

由于其可以有多个孩子节点，故其可以有效的控制树高，时间复杂度也稳定为O(logN)，这也意味着将会降低磁盘IO开销，提升数据库性能。

2.4 最终选择之——B+树

上面提到B树不仅可以满足数据库范围查询的要求，而且可以降低IO开销，但是开发数据库的大佬并没有将B树作为索引的底层结构，因为他们发现了更加高效更加适合的数据结构——B+树。

B+树在满足B树可控树高、高效O(logN)查询、... 的优秀性能下，进一步做了优化。

2.4.1 B树与B+树的对比(面向索引)【面试题】

1.B+树的叶子节点间使用单链表连接，可以通过一个叶子节点找到它相邻的兄弟节点

且MySQL在组织叶子节点时，使用的是双向循环链表

2.B+树中，所有节点的值都包含在了叶子节点中

在MySQL中，非叶子节点只保留了对子结点的引用，并不保存真实数据，所有的真实数据都保存在叶子节点中。因此，对于B+树而言，在相同树高的情况下，查询任意元素的时间复杂度都是相同的，性能均衡。

3、MySQL中的页

3.1 页的使用原因

MySQL中，使用innodb存储引擎后生成的表空间文件后缀都为.ibd。而在.ibd文件中，最重要的结构体就是页(Page)，页是内存与磁盘交互的最小单元，默认大小为16KB。

show variables like 'innodb_page_size'; #查看页大小，单位字节

每次内存与磁盘的交互至少读取一页，所以在磁盘中每个页内部的地址都是连续的。之所以这样做有以下两点原因：

时间局部性：如果⼀个信息项正在被访问，那么在近期它很可能还会被再次访问
空间局部性：将来要使用的数据大概率与当前访问的数据在空间上是临近的

所以根据局部性原理，以⼀次从磁盘中读取一页的数据放入内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘I/O，提高性能。

注意：即使一个页中没有数据，也会使用16KB的存储空间。同时与索引的B+树中的节点对应，也就是说，索引树中的每一个节点，就对应一个页。

3.2 页的结构

在MySQL中有多种不同类型的页，最常用的就是用来存储数据和索引的"索引页"，也叫做"数据页"，但不论哪种类型的页都会包含页头(File Header)和页尾(File Trailer)，页的主体信息使用数据"行"进行填充。

每创建一个表，生成一个保存数据的文件，即.ibd文件，也称为独立表空间文件。

上文说到，一个.ibd文件中，最重要的结构就是页，接下来，让我们一起探讨页的组成结构。

3.2.1 页文件头和页文件尾

页文件头和页文件尾中，包含了当前文件的主要信息：

这⾥我们只关注，上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来（通过页号和页大小，可以计算出上一页和下一页在磁盘上的偏移量），形成⼀个双向循环链表。

3.2.2 页主体

页主体部分是保存真实数据的主要区域，每当创建⼀个新页，都会自动分配两个行。

⼀个是页内最小行 Infimun
⼀个是页内最大行 Supremun

这两个行并不存储任何真实信息，而是作为数据行链表的头和尾。

并且，每一个数据行有一个记录下一行的地址偏移量的区域：next_record，故此，页内所有数据行组成了⼀个单向链表。

当向⼀个新页插入数据时，将 Infimun 连接第一个数据行，最后一行真实数据行连接 Supremun ，这样数据行就构建成了一个单向链表，更多的行数据插入后，会按照主键从小到大的顺序进行链接，自动排序。

也就是说，所有数据行间形成单向链表：最小化Infimun始终为链表的头，最大行Supremun始终为链表的尾。

3.2.3 页目录

上文提到，页中的每个数据行间形成了一个单向链表，但是单链表的时间复杂度为O(N)，无法满足高效查询，为了提高查询效率，InnoDB采用二分查找，以加入页目录的结构来解决查询效率问题。

页目录实现形式：将页内包括头行(最小行Infimun )、尾行(最大行Supremun )在内的所有行进行分组。具体实现如下：

最小行单独为一组
其他每个组最多8条数据，超过8条数据时会开辟出一个新的分组
最大行永远在最后一个分组中
每创建一个分组，页目录就会创建一个槽，即槽的数量与组的数量是一致的，且每个分组与槽都一一对应
槽中记录了其对应分组的最后一条记录的地址，同时记录这条记录的主键值

经过分组和槽的创建，查找操作时就能够以二分查找性能快速定位到要目标数据，大大提高了查找效率。

例如，我们要查找某一条存在的记录：

第一步，通过索引树找到该记录所在页。
第二步，通过槽找到该记录所在分组。(每个槽都记录了该分组最后一条记录的主键值和地址，因为页中所有数据行通过主键有序排列，通过比较槽中的主键值，可快速定位到目标记录所在分组)
第三点，遍历该分组的单链表(最多只有8条数据)，查找成功。

注意：页与页(节点与节点)间的遍历是从磁盘中加载数据的，要想查询页中的的内容需要先通过磁盘IO把页从磁盘加载到内存中（先加载后访问）。

3.2.4 数据页头

数据页头记录了当前页保存数据相关的信息。

4、B+树在MySQL索引上的应用

在索引的B+树的叶子节点和非叶子节点中：

非叶子节点和叶子节点均为页，称为索引页/数据页。
非叶子节点只记录索引信息。在索引页中保存的是主键值和叶子节点的引用。
叶子节点存储的是真实的数据。数据页保存的是具体的数据。
最后一层的叶子节点中，页与页之间通过页号建立起关联关系(页号信息在页头中存储)，最终形成了一个双向循环链表。

例如查找id为5的记录：

判断B+树根节点的索引记录，5<7，进入左孩子节点，找到索引页2
判断索引页2的索引记录，找到与5相等的记录，命中
进入数据页3

故以上过程共经过3次IO过程：加载索引页1-->加载索引页2-->加载数据页3

4.1 三层树高的B+树的数据存储量(理论上)

上文已说明，一个页的大小为16KB。

第一层：根节点（索引页）

一个索引页存储的是主键值和子节点的引用。假设主键值占8Byte，地址占6Byte，故一条索引记录的大小为8+6=14Byte。故一个索引页可保存16*1024/14=1170条索引记录。故B+树的根节点可保存1170条索引记录，即可指向1170个子节点。

第二层：非叶子节点（索引页）

同样，第二层的每个索引页可指向1170个子节点(数据页)。

第三层：叶子结点（数据页）

算上页中页头、页尾、页主体....等结构空间的占比，假设一个页中最多可以保存16条记录。故，三层树高的B+树一共可存储 1170*1170*16=21,902,400条记录。

综上，三层树高的B+树一共可存储 1170*1170*16=21,902,400条记录，而在存储这么多数据的情况下，只需要经过3次IO就可以查询到目标数据（加载索引页1-->加载索引页2-->加载数据页3），可以说是极其高效。

而且，如果将索引页1、索引页2加载到内存中进行缓存，那么只需一次IO就可以查询成功，效率极高。

5、索引的分类

5.1 主键索引

主键索引也叫做聚集索引、聚簇索引
当在表中定义一个主键(PRIMARY KEY)时，将自动创建主键索引，索引中的值就是主键列的值
故推荐为每一个表定义一个主键。

5.2 普通索引

普通索引是需要手动创建的索引。
最基本、最常用的索引类型，没有唯一性限制。
为了提升查询效率，工作中通常为查询频繁的列创建索引。
可以为多个列创建组合索引，称为复合索引或组合索引。
创建索引的前提是：列的值重复性不高。例如：gender(性别)列，该列值要么为1(男)，要么为2(女)，就没有必要创建索引。
创建索引之后都会生成一棵索引树，创建多少索引就会生成多少棵索引树。

注意：

创建索引所生成的索引树也是会占用磁盘空间的。

所以，在创建索引时，一定要慎重考虑需不需要创建。

索引树越多，对增、删、改的效率影响越大，将会拉低数据库性能。

所以没有必要创建冗余索引(如上文的gender列)。

5.3 唯一索引

当表中定义有UNIQUE唯一键时，将自动创建唯一索引。
与普通索引类型，但唯一索引的列不允许有重复值。

5.4 全文索引（了解）

基于文本列(CHAR、VARCHAR或TEXT列)上创建，以加快对这些列中包含的数据查询和DML操作
用于全文搜索，仅MyISAM和InnoDB引擎支持。

5.5 聚集索引

即上文提到的主键索引。
如果表中没有定义主键(PRIMARY KEY)，innoDB将使用第一个UNIQUE和NOT NULL的列作为聚集索引（聚集索引可以标识数据行的唯一性）
如果表中没有主键或者唯一非空列作为合适的聚集索引时，innoDB会自动新增ROW_ID列，ROW_ID单调递增，并使用ROW_ID作为索引。（ROW_ID为数据行中的隐藏列之一，我们查询不到，也使用不了）

5.6 二级索引/非聚集索引

聚集索引以外的索引称为非聚集索引或二级索引
二级索引中的每条记录都包含了该行的主键列（默认包含的），以及二级索引指定的列（一列或多个列）。
要查询的列，没有被索引完全包含（索引中的列不够），这时InnoDB通过二级索引的索引树查询到主键值，再利用主键值通过主键索引树查询相关记录，这个过程称为回表查询(普通索引树 --> 主键索引树)。
如果要查询的列，在二级索引中刚好就有（二级索引包含了要查询的列），那么此时不需要回表查询，可以直接从二级索引树中把数据返回给用户，这种情况称为索引覆盖。
创建复合索引时，如果name列在sn列的前面，则使用where条件时，也要先使用name再使用sn，也不能只使用sn(使用AND时，两列顺序不作要求)。如果只使用sn列，那么索引失效(不走索引)。如果非要使用sn列来条件查询，可以为sn单独创建一个索引。可以这样理解：查字典时，必须先找声母再找韵母，而不能先找韵母再找声母。