InnoDB是MySQL最常用的事务存储引擎，文章主要为个人学习nnoDB结构的简单总结。

逻辑存储结构

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(文件头信息)：如表空间中页的偏移值(FIL_PAGE_OFFSET)、上一页位置指针(FIL_PAGE_PREV )、下一页位置指针(FIL_PAGE_NEXT)、页类型等.

infimum + Supremum Records：首次创建索引时，InnoDB会在根页面中自动设置一个最小记录和一个最高记录，并且永远不会删除它们。infimum表示比可能最小的索引值还要小的值，Supremum表示比可能最大的索引值还要大的值。最初，它们都存在于根页面上，但是随着索引的增长，最低记录将存在于第一或最低叶子页上，最高记录将出现在最后或最大索引值页上。

User Records(用户记录)：用户插入的所有记录，记录中都有一个记录指针指向下一个记录。换句话说，记录是单向链接列表。因此InnoDB搜索时可以按键顺序访问行。

Page Directory(页目录)：存放了可变数量的记录指针，记录指针也被称为“插槽”(slot)。插槽跟踪记录的逻辑(索引)顺序进行排序，所以易于对Page上的记录进行二分查找，但只能给出一个粗略的位置。在一个填满数据的Page中，每个槽有6个记录。

聚集(聚簇)索引：以主键创建的索引，叶子节点存储行数据
非聚集(聚簇)索引：非主键创建的索引，叶子节点存储的是索引列和主键。使用非聚集索引查询数据，会先根据索引列获取主键，再根据主键查到数据(该过程叫回表)。使用复合索引可省去回表查询。

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])的子树
所有叶子结点位于同一层
特性如下：
关键字集合分布在整颗树中
任何一个关键字出现且只出现在一个结点中
搜索有可能在非叶子结点结束
其搜索性能等价于在关键字全集内做一次二分查找
自动层次控制