基于8.0版本
索引数据结构
数据结构演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- 二叉树
演示：https://www.cs.usfca.edu/~galles/visualization/BST.html
缺点：对于自增序列将蜕变成链表
- 红黑树
演示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
缺点：树高度不可控，大数据量查找效率不高
- Hash表
缺点：不支持范围查找
- B-Tree
节点中的数据索引从左到右递增
演示：https://www.cs.usfca.edu/~galles/visualization/BTree.html
- B+Tree
非叶子结点只存储索引，叶子节点包含所有索引字段
相比B-Tree增加叶子结点间的指针连接，提高区间访问速度（可用于范围查找）
叶子、非叶子结点有序，非叶子结点索引页常驻内存（高版本）减少磁盘I/O
演示：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
MyISAM与InnoDB数据存储差异：
MyISAM通过MYI查找索引获得数据所在磁盘文件地址，根据地址从MYD获取对应数据（非聚集索引）
InnoDB主键索引数据与索引存放在同一文件（聚集索引），非主键索引：叶子结点存放的数据为主键
Buffer Pool
InnoDB数据缓存区，用于缓存数据提高访问性能，启动默认申请128M内存
页
默认16KB，数据存取的基本单位，数据、索引均以页的形式体现
三种链表
链表通用结构
基节点，记录链表头尾节点指针、统计信息
控制块，记录页信息，用于快速增加、删除制定类型页信息
- Free链表（空闲链表，记录Buffer Pool空闲页块）
每次数据读取如果Buffer Pool中没有所需数据则从磁盘读取数据所在页数据存入Buffer Pool，可存入的空闲页块从空闲链表中获取，如果空闲链表为空则通过LRU链表释放
- Flush链表（刷写链表，记录Buffer Pool中哪些页块是脏页）
每次数据修改仅修改Buffer Pool中的数据，由定时任务从刷写链表中将脏页数据持久化到磁盘中（1s或10s）
- LRU链表（最近最少使用链表，记录Buffer Pool最近最少使用页块）
链表分为两个区域：热数据区域（5/8）、冷数据区域（3/8）
每次查找数据后将数据块插入头节点（如果期间再次使用则需再次将数据块转移动至头节点），Buffer Pool满后释放尾节点对应页数据
冷数据区域控制块同一页数据两次访问时间大于1秒时将控制块转移到热数据区域（解决全表扫描等短时间连续访问相同页数据导致热数据频繁淘汰问题）
Log Buffer
Redo Log（InnoDB）
- innodb_flush_log_at_trx_commit（控制redo log持久化逻辑）
0 表示事务提交时，不立即对redo log进行持久化，由后台线程处理写盘操作
1 表示事务提交时，立即对redo log进行持久化（默认）
2 表示事务提交时，立即将redo log写入操作系统缓冲区，由操作系统处理写盘操作
- update操作（默认）流程
- 更新Buffer Pool页数据
- 生成redo log对象
- commit后持久化redo log（顺序I/O，MySQL安装后默认创建2个48M log文件，减少磁盘寻址消耗）
- 如果redo log文件均已写满则触发check point，将flush链表所标记页数据写入磁盘
- 记录Change Buffer
Bin Log（MySQL）
主从同步时使用
Undo Log
事务回滚时使用，用于记录修改前数据
Change Buffer
用于解偶更新操作对索引更新的影响，临时记录更新操作用于后续索引更新
- update操作流程
- 更新操作涉及索引更新时，如果非主键索引页不在Buffer Pool中则先将本次修改记录在Change Buffer中
- 在下一次数据查询用到索引页时，先检查Change Buffer中是否有对应索引页的修改，如有则进行修改后放入Buffer Pool中用于后续使用
Double Write Buffer
用于解决部分磁盘页数据部分写入失败问题，操作系统每页4KB，InnoDB每页16KB（操作系统需分4次才能完成磁盘写入操作）
- 写入操作
- 写入双写缓冲区（写入成功后删除Redo Log）
- 写入表空间