Mysql索引原理导读.pdf

Mysql索引原理

Mysql

MySQL
属于CS结构即客⼾端/服务端，Client、Server。其中server层包含连接层、SQL层、存储引擎

层

存储引擎：

MySQL
::
MySQL
8.0
Reference
Manual
::
15.4
InnoDB
Architecture

Buffer
Pool

MySQL
::
MySQL
8.0
Reference
Manual
::
15.5.1
Buffer
Pool

为了提⾼⼤容量读取操作的效率，缓冲池被划分为可能包含多⾏的⻚。为了提⾼缓存管理的效率，缓

冲池实现为⻚⾯的链接列表;很少使⽤的数据使⽤最近最少使⽤的
（LRU）
算法的变体从缓存中⽼化。

InnoDB存储引擎将所有数据逻辑地存放在⼀个空间，我们称之为表空间（tablespace）。表空间由段

（segment）、区（extent）、⻚（page）组成，⼤致存储结构如下图所⽰：

•段：常⻅的段有数据段（B+树⻚节点）、索引段（B+树⾮⻚节点，索引节点）、回滚段等。

•区：区是由64个连续的⻚组成的，每个⻚⼤⼩为16KB，即每个区⼤约为1MB。

•⻚：⻚是innodb磁盘管理最⼩的单位，innodb每个⻚的⼤⼩是16K，且不可更改。常⻅的⻚有数

据⻚、Undo⻚、事务数据⻚、系统⻚等

InnoDB⻚类型为B-tree
node类型，存放的实际就是⾏数据了，File
Header⽤于记录Page的头信息，

其中⽐较重要的就是Fil_PAGE_PREV和FIL_PAGE_NEXT字段，通过这两个字段可以找到该⻚的上⼀⻚

和下⼀⻚，实际上通过这两个字段将形成⼀个双向链表。Page
Header⽤来记录Page状态信息。接下

来Infimum和Supremum是两个伪⾏记录，Infimum（下确界）记录⽐该⻚中任何主键值都要⼩的

值，Supremum
（上确界）记录⽐该⻚中任何主键值都要⼤的值，这个伪记录分别构成了⻚中记录的

边界。UserRecords中存放的就是数据⾏记录。Free
Space存放的是空闲空间，被删除的⾏会被记录

成空闲空间。Page

Directory记录着与⼆叉查找相关的信息。File
Trailer存储⽤于检测数据完整性的校

验。

索引是什么

定义

数据库中，索引的定义就是帮助存储引擎快速获取数据的⼀种数据结构，形象的说就是索引是数据的

⽬录。
InnoDB
是在
MySQL
5.5
之后成为默认的存储引擎。

下图是
MySQL
的结构图，索引和数据就是位于存储引擎中：

分类

•按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。

•按「物理存储」分类：聚簇索引（主键索引）、⼆级索引（辅助索引）。

•按「字段特性」分类：主键索引、唯⼀索引、普通索引、前缀索引。

•按「字段个数」分类：单列索引、联合索引。

在创建表时，InnoDB
存储引擎会根据不同的场景选择不同的列作为索引：

•如果有主键，默认会使⽤主键作为聚簇索引的索引键（key）；

•如果没有主键，就选择第⼀个不包含
NULL
值的唯⼀列作为聚簇索引的索引键（key）；

•在上⾯两个都没有的情况下，InnoDB
将⾃动⽣成⼀个隐式⾃增
id
列作为聚簇索引的索引键

（key）；

数据结构

B树

MySQL
中索引的数据结构就是采⽤了
B+
树，B+
树结构如下图：

B+
树与
B
树差异的点，主要是以下这⼏点：

•⼦节点（最底部的节点）才会存放实际数据（索引+记录），⾮⼦节点只会存放索引；

•所有索引都会在⼦节点出现，⼦节点之间构成⼀个有序链表；

•⾮⼦节点的索引也会同时存在在⼦节点中，并且是在⼦节点中所有索引的最⼤（或最⼩）。

•⾮⼦节点中有多少个⼦节点，就有多少个索引；

•B+
树的⾮⼦节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相⽐存储即

存索引⼜存记录的
B
树，B+树的⾮⼦节点可以存放更多的索引，因此
B+
树可以⽐
B
树更「矮

胖」，查询底层节点的磁盘
I/O次数会更少。

•B+
树有⼤量的冗余节点（所有⾮⼦节点都是冗余索引），这些冗余索引让
B+
树在插⼊、删除的

效率都更⾼，⽐如删除根节点的时候，不会像
B
树那样会发⽣复杂的树的变化；

•B+
树⼦节点之间⽤链表连接了起来，有利于范查询，⽽
B
树要实现范查询，因此只能通过

树的遍历来完成范查询