MySQL技术内幕 读书笔记（一）：InnoDB逻辑存储结构与索引树的关系
以下内容均面向MySQL InnoDB存储引擎展开。
逻辑存储结构
从InnoDB存储引擎的逻辑存储结构看，所有数据都被逻辑地存放在一个空间中，称之为表空间（tablespace）。表空间又由段（segment）、区（extent）、页（page，在一些文档中有时也被称为块 block ）组成。InnoDB存储引擎的逻辑存储结构大致如下图所示。
- 表空间
表空间可以看做是InnoDB存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。
- 段
表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等。因为InnoDB存储引擎表是索引组织的（index organized），因此数据即索引，索引即数据，那么数据段即为B+树的叶子节点（Leaf node segment），索引段即为B+树的非索引节点（Non-leaf node segment）。
- 区
区是由连续页组成的空间，在任何情况下每个区的大小都为1MB。为了保证区中页的连续性，InnoDB存储引擎一次从磁盘申请4~5个区，默认情况下InnoDB存储引擎页的大小为16KB，即一个区中一共有64个连续的页。可通过参数设置页的大小为其他值，如2K、4K或者8K，相应的一个区中的页的数量也会跟着改变（因为区的大小维持不变）。
这里提一下为什么InnoDB会选择一次性从磁盘申请4~5个区。因为这样一来，当表的数据量很大的时候，在查询记录时，逻辑相邻的页也会是大致物理相邻的，这样从磁盘读取页数据到内存是就会是顺序IO，一定程度上避免了随机IO，进而提升查询的性能。
还有一点值得注意的是，实际在每个段刚开始时，数据的插入会先使用32个页大小的碎片页（fragment page）来存放数据，在这些碎片页耗尽之后才是区的申请创建。
- 页
同大多数数据库一样，InnoDB有页（Page）的概念（也可以称为块），页是InnoDB磁盘管理的最小单位，默认每个页的大小为16KB。
常见的页类型有：数据页（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）。
这里重点提一下数据页的结构，InnoDB数据页由以下7个部分组成，
其中File Header、Page Header、File Trailer的大小是固定的，分别为38、56、8字节，这些空间用来标记改页的一些信息，如Checksum、数据页所在B+树索引的层数等。User Records、Free Space、Page Directory这些部分为实际的行记录存储空间，因此大小是动态的。
- 行
InnoDB是面向列的（row-oriented），也就是说数据是按行进行存放的。每个页存放的行记录也是有硬性定义的，最多允许存放16KB/2-200行的记录，即7992行记录。
B+索引树结构
在讨论索引树之前先明确一个认知：B+树索引本身并不能找到具体的一条记录，能找到的只是该记录所在的页。数据库把页载入到内存，然后通过Page Directory再进行二叉查找。只不过二叉查找的时间复杂度很低，同时在内存中的查找很快，因此通常忽略这部分查找所用的时间。
有关B+树索引的讲解能Google出来一大堆，这里主要指出其在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2~4层，也就是说查找某一键值的行记录时最多只需要2到4次IO。因为当前一般的机械磁盘每秒至少可以做100次IO，2到4次的IO意味着查询时间只需0.02到0.04秒。
上图是一个B+树聚集索引的示例图，有两个显著的特点：
- 只有叶子节点存放行记录
- 叶子节点之间呈一条双向链表
逻辑存储结构与索引树结构的关联
上面已经介绍了InnoDB的逻辑存储结构被大致划分成表空间、段、区、页、行记录等概念，这些概念是怎么在B+树索引中进行体现的呢？请看下图，
实际上，B+树的每一个节点，就是一个页，例如叶子节点你可以理解为是一个数据页。基于这个叶子节点与页的对应关系我们来倒推一下InnoDB的逻辑存储结构的分层关系（实际并不是简单这样子推出来的，但并不妨碍我们基于此进行理解）：
页的数量随着表数据的增多逐渐增大，便有了区的概念，区就是一系列页的集合，有了区的概念之后在为索引分配空间的时候就从原来的按页为单位分配，转变为按区为单位分配，甚至是当表数据量非常大的时候可以一次性连续分配多个的区，这样做的好处上面已经解释过。当区的数量也增多的时候，我们都知道B+树是有区分叶子节点和非叶子节点的，而如果区不对此做区分的话，就会出现有的叶子节点在A区，有的叶子节点在B区，这样当我们需要进行范围查询的时候查询性能可能就会比较差。于是便又有了段的概念，可以把段简单理解为区的集合，我们将段区分叶子节点段和非叶子节点段（实际还有回滚段等），这样区也便被划分成了叶子节点区和非叶子节点区，叶子节点区的数据尽可能物理邻近存放，可以提升查询效率。页、区、段的概念都有了，在它们的最上层再套上一个表空间（对应于一张或多张表）的概念也就并不奇怪了。