索引和InnoDB数据存储结构

索引

  • 概述：索引是帮忙MySQL高效获取数据的数据结构。

索引的本质：

  • 索引是数据结构。可以简单理解为“排好序的快速查找数据结构”，满足特点查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高效查找算法

优点：

  • 提高数据检索的效率，降低数据库的IO成本

  • 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性

  • 在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了CPU的消耗

缺点

  • 创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加
  • 索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间
  • 除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引结构

聚簇索引

  • Innodb的聚簇索引，数据即索引。

  • record_type：记录头信息的一项属性，表示记录的类型，

    • 0表示普通记录
    • 1目录项记录
    • 2表示最小记录
    • 3表示最大记录

  • next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量

  • 各个列的值

  • 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息

  • 目录项记录的 record_type 值是1，而普通用户记录的 record_type 值是0

  • 目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含 很多列

  • 记录头信息还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的1页中的主键值最小的目录项记录 的 min_rec_mask 的值为1，其他别的记录的 min_rec_mask 值都是0

  • Innodb的B+ Tree

    • 一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放用户记录的那层为第0层，之后依次往上加

常见的索引概念

  • 分为聚簇索引和非聚簇索引

    • 聚簇索引

      • 特点

        • 使用记录主键值的大小进行记录和页的排序

        • 页内的记录是按照主键的大小顺序排成一个单向链表

        • 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个双向链表

        • 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表

        • B+树的 叶子节点 存储的是完整的用户记录

      • 优点

        • 数据访问更快，因为聚簇索引将索引和数据保存在同一个 B+ 树中，因此聚簇索引中获取数据比非聚簇索引更快
        • 聚簇索引对于主键的排序查找和范围查找速度非常快
        • 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的IO操作

      • 缺点

        • 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于innoDB表，我们一般都会定义一个自增的ID列为主键
        • 更新主键的代价很高，因为将会导致被更新的行移动。一般定义主键不可更新
        • 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

    • 二级索引

      • 二级索引的B+树的叶子节点存放的是该记录的主键值，根据主键值再去聚簇索引里查找该条记录。这个过程称为回表

    • 联合索引

      • 可以同时将多个列的大小作为排序规则，也就是同时为多个列建立索引。
        • 先把各个记录和页按照第一个索引列进行排序
        • 在第一个索引列相同的情况下，在根据第二个索引列进行排序，依次递归，直到所有的列
      • 联合索引本质也是二级索引。只会产生1棵B+树

InnoDB的B+树索引的注意事项

  1. 根页面位置万年不动。以下是B+树的形成过程：

    1. 每当为某个表创建一个 B+树索引（聚簇索引默认就有），都会为这个索引创建一个 根节点 页面。最开始表中没有数据的时候，每个 B+树索引对应的根节点中既没有用户记录，也没有目录项记录

    2. 随后向表中插入用户记录时，先把用户记录存储到这个根节点中

    3. 当根节点中的空间用完时，会将根节点中的所有记录复制到一个新分配的页中，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值的大小会被分配到 页a 或者 页b中，而根节点便升级为存储目录项记录的页

  2. 内节点中目录项记录的唯一性

    • 需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的
      • 索引列的值
      • 主键值
      • 页号

3.. 一个页面最少存储2条记录

  • MyISAM中的索引方案

    • 用B+Tree作为索引结构，叶子节点的data域存放的是 数据记录的地址
    • 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为 数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中赛多少记录。由于在插入数据的时候并 没有刻意按照主键大小排序，所以并不在这些数据上使用二分法进行查找
    • 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点存储的不是完整的用户记录，而是 主键值 + 数据记录地址 的组合
    • MyISAM的索引文件仅仅保存数据记录的地址。在 MyISAM中，主键索引和二级索引在结构上没有任何区别，只是主键索引要求 key 是唯一的，而二级索引的key 可以重复。

  • MyISAM 与 InnoDB 对比

    • MyISAM的索引方式都是“非聚簇”的，与 InnoDB包含1个聚簇索引是不同的。
    1. 在InnoDB中，只需要根据主键值 对 聚簇索引 进行一次查找 就能找到对应的记录，而在 MyISAM 中 却需要进行一次 回表 操作，意味着 MyISAM 中建立的索引相当于 全都是 二级索引
    2. InnoDB 的数据文件本身是索引文件，而MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址
    3. InnoDB 的 非聚簇索引 data域 存储相应记录 主键的值，而 MyISAM索引记录的地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域
    4. MyISAM的 回表操作是十分快速的，因为是通过地址偏移量 直接到 文件中取数据的，反观 InnoDB 是通过获取逐渐之后再去聚簇索引里找记录，比不上通过地址偏移量去找。
    5. InnoDB 要求表 必须要有主键 (MyISAM 可以没有)。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

索引的代价

空间上的代价

  • 每建立一个索引都要为它建立一颗B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一颗很大的B+树由许多数据页组成，那就是很大的一片存储空间

时间上的代价

  • 每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。B+树每层节点之间都是按照从小到大的顺序排序而组成了双向列表。而节点中的记录都是按照索引列的值从小到大的顺序而形成了一个单项列表。而增、删、改操作可能会对节点和记录的排序造成破坏。所以存储引擎需要额外的时间进行一些记录移位，页面分裂，页面回收 等操作来维护好节点和记录的排序。如果建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

MySQL数据结构

B-Tree

一个M阶的B树(M > 2) 有以下的特性

  1. 根节点的二子树的范围是 [2,M]
  2. 每个中间节点包含 k-1 个关键字 和 k 个孩子，孩子的数量 = 关键字的数量 + 1，k的取值范围 [ceil (M /2 ),]
  3. 叶子叶节节点包括 k-1 个关键字（叶子节点没有孩子），k的取值范围为 [ ceil(M/2),M]
  4. 假设中间节点的关键字升序排列，此时 k-1 个关键字相当于 划分了 k 个范围，也就是对应着k个指针
  5. 所有叶子节点位于同一层

B+Tree

B+树和B树的差异

  1. 有k个孩子的节点就有k个关键字。也就是孩子数量 = 关键字数，而B树中，孩子数量 = 关键字数量 + 1
  2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大(或最小值)
  3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而B树中，非叶子节点即保存索引，也保存数据记录
  4. 所有关键字都在叶子节点出现，叶子节点构成一个有序列表，而且叶子节点本身按照关键字的大小从小到大顺序链接

InnoDB数据存储结构

数据库的存储结构：页

磁盘与内存交互基本单位：页

  • InnoDB将数据划分为若干个页，InnoDB中页的大小默认为16KB
  • 以页作为磁盘和内存之间交互的基本单位，也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。数据库管理存储空间的基本单位是页(Page)，数据库I/O操作的最小单位是页

页的大小

  • 不同的数据库管理系统(简称DBMS)的页大小不同。比如在MySQL的InnoDB存储引擎中，默认页的大小是16KB
SHOW VARIABLES LIKE '%innodb_page_size%';

页的上层结构

  • 另外在数据库中，还存在着区(Extent)、段(Segment)和表空间(Tablespace)的概念。
    • 区(Extent)是比页大一级的存储结构，在InnoDB存储引擎中，一个区会分配64个连续的页。因为InnoDB中的页大小默认是16KB，所以一个区的大小是 64*16KB = 1MB
      • .B+树的每一层中的页都会形成一个双向链表，如果以页为单位来分配存储空间的话，双向链表相邻的两个页之间的物理位置可能离得非常远。为了避免随机IO，引入区的概念，一个区就是在物理位置上连续的64个页
    • 段(Segment) 由一个或多个区组成，区在文件系统是一个连续分配的空间(在InnoDB中是连续的64个页)，不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。
      • 对B+树的叶子节点和非叶子节点进行区别对待，方便管理
    • 表空间(Tablespace)是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等
      • 表空间是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属于一个表空间。

页的内部结构

  • 按类型划分
    • 数据页、系统页、Undo页和事务数据页
    • 数据页的大小通常16KB，分为7个部分
      • 文件头 (File Header) 38字节
        • 描述页的信息
      • 页头 (Page Header) 56字节
        • 页的状态信息
      • 最大最小记录 （Infimum+supremun） 26字节
        • 最大和最小记录，这是两个虚拟的行记录
      • 用户记录 （User Records） 不确定
        • 存储行记录内容
      • 空闲空间 （Free Space）不确定
        • 页中还没有被使用的空间
      • 页目录 （Page DIrectory）不确定
        • 存储用户记录的相对位置
      • 文件尾 （File Tailer） 8字节
        • 检验页是否完整

FIle Header （文件头部）

  • 作用：描述各种页的通用信息。（比如页的编号、其上一页、下一页是谁等）

  • 大小：38字节

  • 构成

类型名称十六进制描述
FIL_PAGE_SPACE_OR_CHKSUM4字节页的校验和(checksum值)
FIL_PAGE_OFFSET4字节页号
FIL_PAGE_PREV4字节上一个页的页号
FIL_PAGE_NEXT4字节下一个页的页号
FIL_PAGE_LSN8字节页面被最后修改时对应的日志序列位置（英文名：Log Sequence Number）
FIL_PAGE_TYPE2字节该页的类型
FIL_PAGE_FILE_FLUSH_LSN8字节仅在系统表空间的一个页中定义，代表文件至少被刷新到了对应的LSN值
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID4字节页属于哪个表空间
FIL_PAGE_OFFSET
  • 每一个页都有一个单独的页号
FIL_PAGE_TYPE
类型名称十六进制描述
FIL_PAGE_TYPE_ALLOCATED0*0000最新分配，还没使用
FIL_PAGE_UNDO_LOG0*0002Undo日志页
FIL_PAGE_INODE0*0003段信息节点
FIL_PAGE_IBUF_FREE_LIST0*0004Insert Buffer空闲列表
FIL_PAGE_IBUF_BITMAP0*0005Insert Buffer位图
FIL_PAGE_TYPE_SYS0*0006系统页
FIL_PAGE_TYPE_TRX_SYS0*0007事务系统数据
FIL_PAGE_TYPE_FSP_HDR0*0008表空间头部信息
FIL_PAGE_TYPE_XDES0*0009扩展描述页
FIL_PAGE_TYPE_BLOB0*000A溢出页
FIL_PAGE_INDEX0*45BF索引页
FIL_PAGE_SPACE_OR_CHKSUM
  • 代表当前页面的校验和
  • 作用
    • 以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候断电了，造成了该页传输的不完整。通过判断文件头的校验和和文件尾的校验和做对比，如果两个值不相等，则证明页的传输有问题，需要重新进行传输，否则认为页的传输已经完成

File Trailer（文件尾部）（8字节）

  • 前4个字节代表页的校验和：这个部分和File Header中的校验和相对应的
  • 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）：这个部分也是为了校验页的完整性的，如果首部和尾部的LSN值校验不成功的话，就说明同步过程出现了问题

Free Space（空闲空间）

  • 存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，并没有User Records这个部分，每当插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要区申请新的页

User Recodes（用户记录）

  • User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。
指定行格式语法
CREATE TABLE 表名(列的信息) ROW_FORMAT=行格式名称
ALTER TABLE 表名 ROW_FORMAT=行格式名称
行格式

  • COMPACT行格式

  • 一条完整的记录可以被分为记录的额外信息和记录的真实数据两大部分

    • 记录的额外信息
      • 变长字段长度列表
      • NULL值列表
      • 记录头信息
    • 记录的真实数据
      • 记录的真实数据除了自己定义的列的数据以外，还会有三个隐藏列
    列名是否必须占用空间描述
    row_id否6字节行ID，唯一标识一条记录
    transaction_id是6字节事务ID
    roll_pointer是7字节回滚指针
    • 这几个列的真正名称是：DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR

  • 一个表没有手动定义主键，则会选取一个Unique键作为主键，如果连Unique键都没有定义的话，则会为表默认添加一个名为row_id的隐藏列作为主键。

  • 变长字段长度列表

    • MySQL支持一些变长的数据类型，在Compact行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表（存储的变长长度和字段顺序是反过来的）

  • NULL值列表

    • 数据是需要对齐的，如果没有标注出来NULL值的位置，就有可能在查询数据的时候出现混乱。因此，提前准备一个NULL值列表，用于表示当前那条数据哪些列是NULL
      • 二进制为1时，值为NULL
      • 二进制为0时，值不为NULL

  • 记录头信息

名称大小（单位：bit）描述
预留位11没有使用
预留位21没有使用
delete_mask1标记该记录是否被删除
min_rec_mask1B+树的每层非叶子节点中的最小记录都会添加该标记
n_owned4表示当前记录拥有的记录数
heap_no13表示当前记录在记录堆的位置信息
record_type3表示当前记录的类型，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录
next_record16表示吓一条记录的相对位置
  • delete_mask
    • 值为0：代表记录并没有被删除
    • 值为1：代表记录被删除掉了
    • 被删除的记录为何要在页中存储呢？
      • 删除记录之后的记录会在磁盘中重新排列，这会导致性能消耗。所以只是打一个删除标记而已
      • 后面新增的记录覆盖删除的记录即可
  • min_rec_mask
    • B+树的每层非叶子节点中的最小记录都会添加该标记，min_rec_mask值为1
    • 自己插入的min_rec_mask值都是0，意味着它们都不是B+树的非叶子节点中的最小记录
  • record_type
    • 0：表示普通记录
    • 1：表示B+树非叶节点记录
    • 2：表示最小记录
    • 3：表示最大记录
  • heap_no
    • 这个属性表示当前记录在本页中的位置
    • MySQL会自动给每个页里加了两个记录，由于这两个记录并不是自己插入的，所以这两个记录有时候也称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。最小记录和最大记录的heap_no值分别是0和1。
  • n_owned
    • 页目录中每个组最后一条记录的头信息会存储该组一共有多少条记录，作为n_owned字段
  • next_record
    • 记录头信息里该属性非常重要，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量
  • 行溢出
    • 一个VARCHAR类型的最多存储的字节数量应该是65535-2-1=65532个字节的数据，因为变长字段的长度占用2个字节，NULL值标识需要占用1个字节
    • 一个页16KB，也就是16387字节，而VARCHAR最多可以存储65533个字节，这时候就会把剩余数据分散存储在几个其他的页中进行分页存储，然后记录的真实数据处用20个字节存储指向这些页的地址
  • Dynamic和Compressed行格式
    • Compressed和Dynamic两种记录格式对于存放在BLOB中的数据采用完全的行溢出的方式
    • Compact和Redundant两种格式会在记录的真实数据处存储一部分数据
    • Compressed行格式会进行zlib算法压缩

Infimum+Supremum（最小最大记录）

  • InnoDB 规定的最小记录与最大记录这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的。

Page Directory(页目录)

  • 为什么需要页目录？
    • 在页中，记录是以单向链表的形式进行存储的。单向链表的特点是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索
    • 将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为"已删除"的记录
      • 第1组，也就是最小记录所在的分组只有1个记录，最后一组，就是最大记录所在的分组，会有1-8条记录；其余的组记录数量在4-8条之间。这样做的好处是其余组的记录数会尽量平分
    • 每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_owned字段
    • 页目录用来存储每组最后一条记录的地址偏移量

Page Header (页面头部)

名称占用空间大小描述
PAGE_N_DIR_SLOTS2字节在页目录中的槽数量
PAGE_HEAP_TOP2字节还未使用的空间最小地址，也就是说该地址之后就是Free Space
PAGE_N_HEAP2字节本页中的记录的梳理（包括最小和最大记录以及标记为删除的记录）
PAGE_FREE2字节第一个标记为删除的记录地址（各个已删除的记录通过next_record组成一个单链表，这个单链表中的记录可以被重新利用）
PAGE_GARBAGE2字节已删除记录占用的字节数
PAGE_LAST_INSERT2字节最后插入记录的位置
PAGE_N_DIRECTION2字节记录插入的方向
PAGE_N_RECS2字节该页中记录的数量（不包括最小和最大记录以及被标记为删除的记录）
PAGE_MAX_TRX_ID8字节修改当前页中的最大事务ID,该值仅在二级索引中定义
PAGE_LEVEL2字节当前页在B+树中所处的层级
PAGE_INDEX_ID8字节索引ID，表示当前页属于哪个索引
PAGE_BTR_SEG_LEAF10字节B+树叶子段的头部信息，仅在B+树的Root页定义
PAGE_BTR_SEG_TOP10字节B+树非叶子段的头部信息，仅在B+树的Root页定义