【MySQL索引：B+树与页的深度剖析】

MySQL索引：B+树与页的深度剖析

在MySQL数据库中，索引扮演着至关告急的脚色，它作为一种数据结构，极大地助力了数据库在查询、存储及更新数据时的高效运作。鉴于在数据库利用里，查询的频率远远高于增编削的频率，索引的焦点作用便在于提升数据检索的服从。
1. 索引利用的数据结构——B+树

1.1 B+树先容

B+树是一种在数据库与文件体系等范畴广泛应用的平衡查找树。以下是一个3阶B+树的示例图：

1.2 B+树的特点

联合上述图示，我们可以或许归纳出B+树具备以下特点：

• 数据有序性与利用复杂度：B+树可以或许维持数据的稳固有序，无论是插入照旧修改利用，其时间复杂度均保持同等。
  
• 节点存储特性：非叶子节点仅负担索引功能，并不存储现实数据，而全部的叶子节点则负责生存真实的数据。
  
• 叶子节点链表结构：全部的叶子节点共同构成了一个有序链表，借助这一链表，可以依据排序序次依次遍历全部数据。
  

1.3 B+树和B树的对比

B树的结构如下图所示：

通过与B树对比，我们可以明了B+树所具有的独特特点：

• 节点值包罗关系：在B+树中，非叶子节点的值涵盖于叶子节点之中。
  
• 叶子节点数据一连性：B+树的叶子节点数据出现一连且相互链接的状态，这一特性使得区间查找与搜索更为便捷。
  
• 性能平衡性：在树高雷同的条件下，B+树查找恣意元素的时间复杂度恒定，性能体现更为平衡。
  

2. MySQL中的页

2.1 页的先容

• 数据存储位置：数据库中的数据存储于磁盘之上。
  
• 页本所在一连性：磁盘中每个页内部的所在是一连的。
  
• 页的作用与巨细：页是内存与磁盘交互的最小单位，默认巨细为16KB。即便某一页没有数据，也会占用16KB的存储空间，而且页与索引的B+树节点相对应。
  

在MySQL中存在多种范例的页，此中最常用的便是用于存储数据和索引的“数据页”或“索引页”。无论何种范例的页，都具备“页头”与“页尾”，页的主体信息则由“数据行”添补。
“数据页”的根本结构如下图所示：

由于页头包罗上一页和下一页的页号，借助这两个属性，可以或许将页与页毗连起来，形成一个双向链表。
2.2 页主体

每当创建一个新页时，体系会自动分配两行，一行代表页内最小行，另一行代表页内最大行。这两行并不存储现实信息，而是作为数据行链表的起始与竣事标记。

当插入数据时，数据会被插入到最小行与最大行之间，并按照主键从小到大的次序举行链接。

2.3 页目次

当一个页中存储的数据量过多时，查找数据会变得繁琐。为提升查找服从，InnoDB接纳二分查找的方式来办理这一标题。
具体实现方式为创建一个页目次，将页内全部行举行分组，分组规则如下：

• 头行（最小行）单独作为一组。
  
• 别的行按照次序分组，每组最多8条数据。
  

页目次中的一个槽对应一个分组，每组的末了一行所在会被记载在槽中。云云一来，在查找某行数据时，可先通过二分查找确定对应的槽，再在槽所对应的组中举行遍历，从而明显进步查询服从。

2.4 B+树在MySQL索引中的应用

在MySQL索引中，B+树的非叶子节点生存索引数据，叶子节点生存真实数据，如下表所示：

以下以查找“主键 = 3”为例，扼要论述其查找过程：

• 在索引页1中：由于3 < 7，以是进入索引页2。
  
• 在索引页2中：由于3 <= 3 < 5，进而进入数据页2。
  
• 在数据页中实行二分查找（依据分组的槽），确定对应的槽。
  
• 在对应的组中举行遍历，终极获取到数据。