当前位置：首页 > news >正文

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

news 文章来源：https://blog.csdn.net/2401_83595513/article/details/142215472 2025/5/17 6:58:16

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单独创建一个索引。可以这样理解：查字典时，必须先找声母再找韵母，而不能先找韵母再找声母。

5.7 索引覆盖

当一个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列，这时就可以直接返回数据，而不用回表查询，这样的现象称为索引覆盖
通过索引查找的列，包含在索引中，不需要回表查询，这种情况就是索引覆盖。

END