InnoDB存储引擎表的数据结构

B+树是由B树演化而来，不同于B树适合在内存中遍历访问，B+树十分适合于在磁盘中存储与读取。从严格意义上讲，B+树已不满足“树”的定义。B+树的定义这里不再详细介绍，这里只介绍B+树的几个重要特点。如下图所示，即是一棵B+树。

• 每个结点可以存储多个关键字，且每个结点可以有多于两个的孩子数；

• 所有叶子结点都位于同一层次；

• 有分支结点中的关键字会在叶子结点中再次列出，也就是说叶子结点中包含全部关键字的信息；

• 叶子结点之间通过双向链表链接，即每个叶子结点都有指向上一个和下一个叶子结点的指针；

• 叶子结点之间依关键字的大小自小而大链接。

2. B+树为何适合于在磁盘中存储与读取

B+树更适合于在磁盘中存储与读取，主要体现在其具有高扇出性和范围查询的高效率上。

• 高扇出性：

（扇出，是指上级模块直接调用的下级模块的数量）

对于一棵3层的1000阶B+树（结点最大的孩子数目称为B+树的阶），可以存储1000的3次方个值，也就是10亿个值，这已经可以满足生产环境中大多数InnoDB表的存储需求。

高扇出性带来的好处就是查询效率的提升，比如3层的B+树，查询某个关键字只需要3次IO，再考虑到一般情况下，根结点总会缓存在内存中，所以只需要2次IO即可。当前一般的机械硬盘每秒可以做100次IO，所以本次查询花费的时间仅有0.02秒。

• 范围查询：

传统的二叉树需要通过前序遍历或其他遍历方法来查询所有结点中的关键字，而不同于二叉树，B+树所有的关键字都按照大小顺序保存在叶子结点中，且通过双向链表链接。因此针对范围查询，只需要从第一个匹配的关键字，通过链表继续向下匹配即可。

1. 聚集索引

如下图所示，即是聚集索引对应的B+树。其中数字代表每行数据的主键值，而叶子结点中的“ROW8”等代表具体的行数据。

如图中所示，非叶子结点中存放的只有主键值以及指向叶子结点的指针，而叶子结点中存放的是主键值、行数据（包含所有字段的值，此处不考虑行溢出数据）和指向上一个叶子结点与下一个叶子结点的指针。

叶子结点对应着数据库概念中的数据页，在InnoDB存储引擎中，每个数据页大小默认为16KB（innodb_page_size）。如图中所示，每个数据页中包含多行数据，且按照主键的大小顺序排列，也就是说，InnoDB表是天然排过序的。

2. 二级索引

如下图所示，即是某个二级索引（辅助索引）对应的B+树。其中字母代表每行数据中的辅助索引值（非主键值），其中数字代表每行数据中的主键值。

如图中所示，二级索引的非叶子结点中仅包含二级索引所在字段的值和指向叶子结点的指针，而叶子结点中包含二级索引值、主键值以及指向上一个叶子结点与下一个叶子结点的指针。正因为叶子结点中不包含整行数据，当需要通过二级索引查询整行数据时，需要通过在二级索引中查询到的主键值，回到聚集索引中再查询一次，这个过程就被称为“回表”。

1. 为什么必须设置主键？

InnoDB表是索引组织表，是通过聚集索引组织数据的，如果建表时定义了主键，InnoDB引擎就会选择主键作为聚集索引，如果没有定义主键，InnoDB引擎就会选择第一个非空（不包含NULL）唯一索引作为聚集索引。如果以上条件都不满足，InnoDB引擎会选择内置6字节的ROWID作为隐含的聚集索引。

另外可以发现，当主键值的长度越小，辅助索引占用的空间也会越小，这是因为辅助索引中并不存储整行的数据，而是只存储该行数据的主键值。所以一般情况下都会使用自增主键。

2. 为什么创建索引耗时久？

因为创建辅助索引时就是凭空生成一棵B+树，还要根据索引值重新组织数据的排列顺序；当创建主键索引时，则相当于重新构建聚集索引所在的B+树。也因为创建索引的成本很高，所以最好在建表的时候就规划好索引。

3. 当表中索引特别多时，为什么Insert语句会执行比较慢？

因为数据不仅会插入聚集索引所在的B+树，还会在该表其余所有索引所在B+树上插入数据（B+树为了保持平衡，插入操作可能涉及到叶子结点的旋转、拆分等操作）。在生产环境中，DBA一般都会制定开发规范，例如单张表上创建的索引数不得超过5个。

4. 为什么覆盖索引效率会比较高？

前文中介绍了“回表”的概念，而“覆盖索引”效率高就体现在其避免了“回表”的操作。“覆盖索引”指从辅助索引中即可查到指定的字段，也可简单理解为某个辅助索引中包含了所有待查询的字段。辅助索引至少包含了两个字段的值，辅助索引值以及其所在行的主键值，而联合索引中包含的字段值会更多。

另外由于辅助索引中并不包含整行的数据，所以其大小也要远小于聚集索引，因此可以减少大量的IO操作。在查询时巧用覆盖索引，可以让查询更加高效。

END

更多精彩干货分享

点击下方名片关注

IT那活儿