InnoDB引擎的底层实现

InnoDB引擎的底层实现

InnoDB的存储文件有两个，后缀名分别是 .frm和 .idb；其中 .frm是表的定义文件， .idb是表的数据文件。

1、InnoDB引擎采用B+Tree结构来作为索引结构

B-Tree（平衡多路查找树）：为磁盘等外存储设备设计的一种平衡查找树

系统从磁盘读取数据到内存时是以磁盘块位基本单位的，位于同一磁盘块中的数据会被一次性读取出来，而不是按需读取。

InnoDB存储引擎使用页作为数据读取单位，页是其磁盘管理的最小单位，默认page大小是16k.

系统的一个磁盘块的存储空间往往没有那么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。

InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时，如果一个页中的每条数据都能助于定位数据记录的位置，这将会减少磁盘I/O的次数，提高查询效率。

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，例：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。

以根节点为例，关键字为17和35，P1指针指向的子树的数据范围小于17，P2指针指向的子树的数据范围为17----35，P3指针指向的子树的数据范围大于35；

模拟查找关键字29的过程：

a.根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第一次】

b.比较关键字29在区间（17,35），找到磁盘块1的指针P2;

c.根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第二次】

d.比较关键字29在区间（26,30），找到磁盘块3的指针P2；

e.根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第三次】

f.在磁盘块8中的关键字列表中找到关键字29.

MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，因此力求达到树的深度不超过3，也就是I/O不需要超过三次；

分析上面的结果，发现需要三次磁盘I/O操作，和三次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率；而三次磁盘I/O操作时影响整个B-Tree查找效率的决定因素。

B+Tree

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，B-Tree中每个节点中有key，也有data，而每一页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

在B+Tree中所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度；

B+Tree在B-Tree的基础上有两点变化：（1）数据是存在叶子节点中的

                                                         （2）数据节点之间是有指针指向的

由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。

因此可以对B+Tree进行两种查找运算，一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

InnoDB中的B+Tree

InnoDB是以ID为索引的数据存储

采用InnoDB引擎的数据存储文件有两个，一个定义文件，一个是数据文件。

InnoDB通过B+Tree结构对ID建索引，然后在叶子节点中存储记录

若建立索引的字段不是主键ID，则对该字段建索引，然后在叶子节点中存储的是该记录的主键，然后通过主键索引找到对应记录