从InnoDB索引的数据结构，去理解索引

 
该篇我们都是基于 InnoDB 存储引擎的大前提下讨论的，如文中未明确指出存储引擎，一律说的是 InnoDB.

要知道 InnoDB 的索引数据结构主要是 B+Tree. 按照物理实现方式，可以将索引划分为聚簇索引和非聚簇索引（也称为 二级索引、辅助索引）。

 

1、InnoDB 中的 B+Tree

 

1.1、B+Tree 的组成

• ① 根节点：B+Tree的最顶层节点，如果树的高度大于1，则根节点可以有多个子节点。

• ② 内部节点（也称为内节点、非叶子节点）：除根节点和叶子节点之外的节点，每个内部节点包含多个键值对和指向子节点的指针。内部节点用于索引，不存储实际的数据。内节点用于存放目录项。InnoDB 的B+Tree中，内节点中的目录项记录必须保证唯一性，所以对于二级索引而言，二级索引（非聚簇索引）中必须包含主键列。

• ③ 叶子节点：位于B+Tree最底层的节点，存储实际的数据（用户记录）或索引键值。叶子节点之间通过指针相互连接，形成一个链表结构，便于进行范围查询和排序操作。

      不论是存放 用户记录（指这个记录中存储了所有列的值，包括隐藏列）的数据页，还是存放目录项记录的数据页，我们都把它们存放在 B+Tree 这个数据结构中，故我们也称这些数据页为节点。每个节点（包括根节点、内部节点和叶子节点）都包含多个键值对和指向子节点的指针。B+Tree通过这种结构，将数据存储在一个平衡的多路搜索树中，从而提高了查询性能和数据访问的效率。

 

1.2、B+Tree中的数据页

 

• 在B+Tree中，页是数据存储的基本单位，也是磁盘I/O操作的最小单元。每个页通常具有固定的大小，例如InnoDB存储引擎中，页的大小默认为16KB。
• 页中包含了节点的键值对数据和指向子节点的指针等信息。
• 通俗来讲，一个叶子节点中有一页数据，一页数据中包含了多条用户记录、主键等信息。每页包含的数据量，与每条用户记录的大小、索引大小等相关。一个非叶子节点中也有一页数据，其包含主键、二级索引字段、下级页码等数据。
• 在InnoDB的一个数据页中，至少存放两条数据记录。

       对于非叶子节点，每个页存储了多个键值对和指向子节点的指针，用于索引和导航到下一层的页。对于叶子节点，每个页存储了实际的数据或索引键值，以及指向相邻叶子节点的指针，用于范围查询和排序操作。通过页的设计，B+Tree可以高效地利用存储空间，减少磁盘I/O操作次数，提高查询性能和数据访问的效率。

 

2、聚簇索引

 

InnoDB存储引擎的聚簇索引，是一种按照主键顺序存储数据的索引结构（由于是主键顺序存储，故主键尽量用有序的）。聚簇索引的叶子节点就是数据节点，且数据都是按照主键排序存储的。其特点是将索引和数据行，保存在同一个B+Tree中，因此查询通过聚簇索引可以直接获取数据。二级索引（非聚簇索引）中必须包含主键列，所以如果主键列很大的话，其他的索引也会占用很大的空间。

InnoDB 的一个表，要求必须有聚簇索引，且只能有一个聚簇索引。InnoDB如果没有显示指定，MySQL系统会自动选择一个非空且唯一的列作为聚簇索引，如果不存在这样的列，MySQL 会自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。一般主键即为聚簇索引，建议主键自增。

 

2.1、聚簇索引的特点

 

• 使用记录主键值的大小进行记录和页的排序，这包含三方面的含义：

  • 页内的记录是按照主键的大小顺序排成一个 单向链表。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次，在同一层次中的页，也是根据页中目录项记录的主键大小顺序排成一个双向链表。

• B+Tree 的叶子节点存储的是完整的用户记录。所谓用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

 

2.2、聚簇索引的结构示例

 
以下示例使用 tb_table 表为例，tb_table表使用 InnoDB 引擎，其中包含 c1、c2、c3、c4、c5 五个字段，其中 c1 为主键，即聚簇索引。

• 表数据示例：

c1（主键8）	c2	c3	c4	c5
1	4	u	44	u
3	9	d	99	d
4	4	a	44	aa
5	3	y	33	yy
8	7	a	71	aa
10	4	o	44	oe
12	7	d	77	q
20	2	e	12	tt
43	9	x	32	xx
59	5	b	53	u
76	6	i	41	e
87	8	a	88	aa
99	5	m	55	d

• 聚簇索引结构示例：
  

 

2.3、聚簇索引的优缺点

 

优点	缺点
数据访问更快，因为聚簇索引将索引和数据保存在同一个B+Tree中，节省大量的 io 操作。	插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。所以对于 InnoDB 引擎的表，一般建议 自增的ID列作为主键。
聚簇索引对主键的 排序查找 、范围查找 速度非常快。	更新主键的代价很高，更新主键会导致被更新的行移动，页分裂调整。一般建议 主键为不可更新。
_	二级索引访问需要两次索引查找。使用二级索引查找时，第一次找到主键值，第二次根据主键值找到行数据，这个过程也就是回表。

 

3、非聚簇索引

 

InnoDB的非聚簇索引也称为二级索引或辅助索引，它是一种基于聚簇索引创建的索引结构。非聚簇索引的叶子节点并不直接存储实际的数据行，而是存储了创建非聚簇索引的字段和聚簇索引的主键值。InnoDB的非聚簇索引也是按照B+Tree的数据结构来组织的，这样可以保证查询的高效性。
 

3.1、非聚簇索引结构示例

 

• 非聚簇索引结构示例（表结构数据同 聚簇索引上述示例，其中以 c2 字段作为非聚簇索引字段）：
  

 

3.2、关于回表

 
说到非聚簇索引，就不得不说【回表】的概念。

我们根据非聚簇索引（二级索引）列的大小排序的 B+Tree，只能确定我们要查找记录的主键，所以如果我们要根据非聚簇索引去做查询，但查询的字段中，除了该非聚簇索引字段还包括其他字段，那就要根据非聚簇索引先查到相关用户记录的主键，再根据主键去查该用户记录行的完整数据，再筛选出需要查询的字段。

总结一下，通过非聚簇索引查询时，如果查询的字段不仅仅是该非聚簇索引字段时，就需要使用到 2 棵 B+Tree，这个过程就叫回表。

 

3.3、聚簇索引和非聚簇索引的区别与代价

 

聚簇索引和非聚簇索引的区别	索引的代价
① 聚簇索引的叶子节点存储的是数据记录，非聚簇索引的叶子节点存储的是 数据位置。非聚簇索引不会影响数据表的物理存储顺序。	① 空间上的代价：每建立一个索引都要为它建立一棵 B+Tree 树，每棵 B+Tree 树的每个节点都是一个数据页，一个数据页默认会占用 16KB 的存储空间，一棵 B+Tree 由许多数据页组成，那就是一个比较大的存储空间。
② 对于InnoDB存储引擎而言，一个表只能有一个聚簇索引，因为只能有一种排序存储的方式。可以有多个非聚簇索引，也就是多个索引目录提供数据检索。	② 时间上的代价：每次对表中的数据进行 增、删、改 操作时，都会去修改各个 B+Tree 索引。B+Tree 每层节点都是按照索引列的值 从小到大的顺序排序 而组成 双向链表。不论是叶子节点中的记录，还是内节点中的记录，都是按照索引列的值，从小到大的顺序而形成的一个单向链表.增删改操作可能会对节点和记录的排序造成破坏，存储引擎需要额外的时间进行记录移位、页面分裂、页面回收等操作来维护好节点和记录的排序。
③ 使用聚簇索引的时候，数据的 查询效率高，但是如果对数据进行插入、删除、更新等操作，效率会比非聚簇索引低。	③ 一个表上的索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。

 

4、扩展与问答

 

4.1、InnoDB 和 MyISAM 对比

 

• MyISAM 的索引方式都是非聚簇的；InnoDB有一个聚簇索引，可以有多个非聚簇索引。
• 在InnoDB 的数据文件本身就是索引文件；MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
• 在 InnoDB 存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在 MyISAM 中需要进行一次回表操作，意味着 MyISAM 中建立的索引相当于全部都是二级索引。
• InnoDB 的非聚簇索引 data域存储相应记录的主键值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
• MyISAM 的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的。InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然也不慢，但还是比不上直接拿地址去获取。
• InnoDB要求必须有聚簇索引（MyISAM可以没有）。InnoDB如果没有显示指定，MySQL系统会自动选择一个非空且唯一的列作为聚簇索引，如果不存在这样的列，MySQL 会自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
   

4.2、MySQL使用InnoDB存储引擎时，为什么不建议使用过长的字段作为主键 ？

 
答：所有二级索引都引用主键索引（聚簇索引），过长的主键索引会让二级索引变得过大。

 

4.3、MySQL使用InnoDB存储引擎时，为何不建议使用非单调字段（不是按照递增或递减的顺序进行排列的字段）作为主键 ？

 
答：InnoDB的数据文件本身就是一颗B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效。而使用自增字段作为主键则是一个很好的选择。

 

4.4、一般情况下，为何我们用到的B+Tree 都不会超过4层 ？

 
答：可以初步估算一下，单表的数据存储情况。假设所有存放用户记录的叶子节点代表的数据页可以存放 100 条用户记录，所有存放目录项的记录的内节点代表的数据页可以存放1000条目录项记录，那么：

• 如果B+Tree只有 1 层，也就是只有一个用于存放用户记录的节点，最多存放 100条记录。
• 如果B+Tree只有 2 层，最多存放的 1000 * 100 = 100,000 条记录（即十万条）。
• 如果B+Tree只有 3 层，最多存放的 1000 * 1000 * 100 = 100,000,000 条记录（即一亿条）。
• 如果B+Tree只有 4 层，最多存放的 1000 * 1000 * 1000 * 100 = 100,000,000,000 条记录（即一千亿条）。

 
 
 
系列文章：

一： 《搞懂 MySql 的架构和执行流程》

二： 《从InnoDB索引的数据结构，去理解索引》

三： 《从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择》

四： 《MySQL 的索引分类和设计原则》

五： 《MySQL 优化思路篇》
 
 
 
 
 
.