一、InnoDB 体系结构

1.1、各个存储引擎比较

  1. Engine            |Support|Comment                                                       |Transactions|XA |Savepoints|
  2. ------------------+-------+--------------------------------------------------------------+------------+---+----------+
  3. FEDERATED         |NO     |Federated MySQL storage engine                                |            |   |          |
  4. MEMORY            |YES    |Hash based, stored in memory, useful for temporary tables     |NO          |NO |NO        |
  5. InnoDB            |DEFAULT|Supports transactions, row-level locking, and foreign keys    |YES         |YES|YES       |
  6. PERFORMANCE_SCHEMA|YES    |Performance Schema                                            |NO          |NO |NO        |
  7. MyISAM            |YES    |MyISAM storage engine                                         |NO          |NO |NO        |
  8. MRG_MYISAM        |YES    |Collection of identical MyISAM tables                         |NO          |NO |NO        |
  9. BLACKHOLE         |YES    |/dev/null storage engine (anything you write to it disappears)|NO          |NO |NO        |
  10. CSV               |YES    |CSV storage engine                                            |NO          |NO |NO        |
  11. ARCHIVE           |YES    |Archive storage engine                                        |NO          |NO |NO        |

1.2、体系结构图示

image.png

  • 后台线程
    • 4 个 IO 线程
    • 1 个 master 线程
    • 1个 Lock 监控线程
    • 1个 错误监控线程
  • 内存
    • 缓冲池 (Buffer Pool)
    • 重做日志缓冲池 (redo log buffer)
    • 额外的内存池 (additional memory pool )

1.3、内存结构图示

image.png

二、InnoDB 存储结构

2.1、InnoDB 逻辑存储结构

  • 表空间图示

image.png

  • 表空间组成
    • 由各个段组成
  • 段 (segment)
    • 每个段由多个区组成
    • 数据段
    • 索引段
    • 回滚段
  • 区（extent）
    • 由64个连续的页组成，每个页16k，一个区1M
  • 页（page）
    • 数据页 (B-Tree Node)
    • Undo 页 (Undo Log Page)
    • 系统页 (System Page)
    • 事物数据页 (Transaction system Page)
    • 插入缓冲位图页(Insert Buffer Bitmap)
    • 插入缓冲空闲列表页(Insert Buffer Free List)
    • 未压缩的二进制大对象页（Uncompressed BloB Page）
    • 压缩的二进制大对象页（Compressed BLOB Page）

  • 行

    2.2、InnoDB 物理存储结构

  • 表空间文件 .ibd

  • 表结构定义文件 .frm

2.3、InnoDB 行记录格式

2.3.1、格式

  • Compact
  • Redundant

2.3.2、Compact 格式

Compact 行记录是 MySQL 5.0 时引入的，其设计目的时为了高效存放数据
image.png

  • 变长字段长度列表（2字节）
    • 按照列的顺序逆序放置的
    • 当列的长度不超过255时，使用 1 个字节表示，超过255字节时，使用 2 个字节表示
    • 长度最大不可以超过2个字节
  • NULL 标志位（1 字节）
  • 记录头信息 （recorder header ）5 字节
    • 固定占用5个字节(40位)

image.png

  • 隐藏列 （13 字节）
    • 事务 id 列 （6字节）
    • 回滚指针列 （7字节）
  • RowId（6字节，没有指定主键的情况下）

2.3.3、Redundant 格式

  • 图示

image.png

  • 变长字段长度列表（2字节）
    • 按照列的顺序逆序放置的
    • 当列的长度不超过255时，使用 1 个字节表示，超过255字节时，使用 2 个字节表示
    • 长度最大不可以超过2个字节
  • 记录头信息 （recorder header ）6 字节
    • 固定占用6个字节(48位)
    • 图示

image.png

  • 隐藏列 （13 字节）
    • 事务 id 列 （6字节）
    • 回滚指针列 （7字节）
  • RowId（6字节，没有指定主键的情况下）

2.4、InnoDB 数据页结构

image.png

2.4.1、组成

  • File Header (文件头)
  • Page Header (页头)
  • Infimun + Supremum Records
  • User Records （用户记录，行记录）
  • Free Space （空闲空间）
  • Page Directory （页目录）
  • File Trailer （文件结尾信息）

2.4.2、File Header

  • 组成部分

image.png

  • Page 类型

image.png

2.4.3、Page Header

用于记录数据页的状态信息
image.png

2.4.4、Infimum 和 Supremum 记录

用于限定记录的边界。Infimum 记录是比该页任何主键值都要小的值，Supremum ☞比任何可能大的值。
image.png

2.4.5、User Records 和 FreeSpace

User Records: 实际存储行的内容
FreeSpace：空闲空间，链表结构，当记录被删除后，该空间会被加入空闲链表中

2.4.6、Page Directory （页目录）

2.4.7、File Trailer

三、索引与算法

3.1、算法

3.1.1、二分查找法

3.1.2、平衡二叉树

3.1.3、B+树

3.2、索引

3.2.1、聚集索引

3.2.2、辅助索引(第二索引)