MySQL InnoDB结构
逻辑存储结构
-
Tablespace(表空间)
InnoDB把数据保存在表空间内，表空间可以看作是InnoDB存储引擎逻辑结构的最高层。本质上是一个由一个或多个磁盘文件组成的虚拟文件系统，存储表和索引，还保存了回滚段、双写缓冲区等 -
Segment(段)
表空间的主要组织单位，常见的段有数据段、索引段、回滚段等，是构成索引、表、回滚段的基本元素。 创建一个索引（B+树）时会同时创建两个段，分别是内节点段和叶子段，内节点段用来管理（存储）B+树非叶子（页面）的数据，叶子段用来管理（存储）B+树叶子节点的数据。 -
extent(区/簇)
簇是构成段的基本元素，一个段由若干个簇构成。 簇是由64个连续的页组成的，每个页大小为16KB，即每个簇的大小为1MB。 -
Page(页)
页是InnoDB存储引擎磁盘管理的最小单位，每个页默认16KB。常见的页类型有数据页（B-tree Node）、Undo页（Undo Log Page）、系统页（System Page）、事务数据页（Transaction system Page）等。 -
Row(行)
数据的存放形式，最多允许存放16KB/2-200，即7992行记录。
页结构
| 名称 | 描述 |
|---|---|
| File Header(文件头信息) | 如表空间中页的偏移值、上/下一页位置指针、页类型等 |
| Page Header(页头信息) | 如当前页记录的数量、页中空闲空间的起始地址、索引ID(当前页属于哪个索引)等。 |
| Infimun + Supremum Records | 虚拟的行记录，限定记录的边界。 |
| User Records(用户记录) | 用户插入的数据行记录，B+树索引组织。 |
| Free Space(空闲空间) | 一个链表结构。在一条记录被删除后，该空间会被加入到空闲链表中用于插入时分配 |
| Page Directory(页目录) | 存放了记录(页)的相对位置，基础单位是槽(slot)，一个槽中可能包含多个记录，用于跟踪记录的逻辑顺序(按键排序)，所以很容易对页面上的记录进行二分查找。即B+树索引本身并不能找到具体的一条记录，只能找到该记录所在的页。数据库把页载入到内存中，通过page directory再进行二叉查找。 |
| File Trailer | 检测页的完整性（是否完整地写入了磁盘） |
索引结构类型
-
聚集(聚簇)索引：以主键创建的索引，叶子节点存储行数据
-
非聚集(聚簇)索引：非主键创建的索引，叶子节点存储的是索引列和主键。使用非聚集索引查询数据，会先根据索引列获取主键，再根据主键查到数据(该过程叫回表)。使用复合索引可省去回表查询。
B树(B-树)、B+树
B-tree树即B树，B即Balanced，故B树的原英文B-tree其实就是B树，由于B+、B-的命名常让人误认为B-tree是另一种树。
-
B-树
B-树是一种多路搜索树，其定义如下：- 定义任意非叶子结点最多只有M个儿子；且M>2
- 根结点的儿子数为[2, M]
- 除根结点以外的非叶子结点的儿子数为[M/2, M]
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
- 非叶子结点的关键字个数=指向儿子的指针个数-1
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
- 所有叶子结点位于同一层
特性如下： - 关键字集合分布在整颗树中
- 任何一个关键字出现且只出现在一个结点中
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
- 自动层次控制