MySQL 索引的数据结构及类型_主键索引的非叶子节点

本文主要总结MySQL InnoDB索引的数据结构及类型，举例说明了B+树能存储的非叶子节点的数量，总结说明索引的类型及优点

B+树

在InnoDB引擎中，索引的底层数据结构是B+树。

• 非叶子节点：存的就是主键索引的指针。
• 叶子节点：叶子节点存储数据。

注意并不是所有的行数据都在叶子节点上，只是父节点中指针指向的那些节点在树上

B+树和B树对比

• B+树是多路搜索树，树的层级更低（检索更快）
• B+树只有叶子节点存储数据，B+树比B树更矮
• B+树叶子节点有双向链表，便于遍历数据

查询表索引的信息

SELECT b.name, a.name, index_id, `type`, a.space, a.PAGE_NO 
FROM information_schema.INNODB_SYS_INDEXES a, information_schema.INNODB_SYS_TABLES b 
WHERE a.table_id = b.table_id AND a.space <> 0
1
2
3

页大小和树高度

InnoDB的数据组织的最小存储单元是页（page），默认情况下，page的大小为16K。

在默认情况下，InnoDB存储引擎页的大小为16KB，即一个区中一共有64个连续的页。自MySQL 5.7后，提供了一个设定page大小的参数innodb_page_size，默认值是16K。

如下就是一个只有2层的B+树示意图：

行数据的组织方式是以页为最小单位，按照链表的方式来组织的。非叶子节点上的指针指向的叶子节点就算是在树上。而对于叶子节点，一个页内是存放了多条行记录的，这多条记录是按照索引从小到大排序的，所以查询的过程首先是根据B+树索引定位到具体的页，然后页内使用二分查找法去找具体的行数据。

InnoDB B+树高度示例

非叶子节点就是一个16K大小的页，所以对于一棵树能存多少数据，主要就看非叶节点能存下多少个[主键ID+指针]。InnoDB中一个指针是6字节长度。

假设一行数据的大小是1K，那么叶子节点的一个页可以存放16行这样的数据。若一行数据大小为16K，则一个页只能存储一行数据。所以合理分配字段的长度会影响页能存储的行数据数，从而可能影响B+树的高度以致于影响查询效率

以主键ID是一个bigint(8字节)来分析B+树存下多少数据，此时[主键ID+指针]总共占14字节

1. 当高度为2时，一个16K大小的根节点可以存下的[主键ID+指针]个数=16K/14=16384/14=1170，也就是说一个高度=2的B+树可以放下1170个叶子节点，即1170个用于存放行数据的页，即可以存放的行数据的大小=1170*16K=18720K=18M，准确的说这是树上的，还有很多不在树上的，所以实际能放下的数据不止18M。

2. 当高度为3时，根节点的16K的页可以存放16K/14=1170个[主键ID+指针]，即第二层就可以有1170个页。所以总共树上可以放的叶子节点的个数=1170*1170=1368900，所以能放下的数据=1368900*16K=21902400K=21G，假设一行的数据大小为1k，能存储的行数为1170*1170*16=21902400。

1. 一个page内还有一些其他的数据，如next指针，LSN等，所以说一个page的16K不完全都拿来存行数据
2. 并不是所有的行数据都在叶子节点上，只是父节点中指针指向的那些节点在树上

索引

数据库中的B+树索引可以分为聚集索引和辅助索引。聚集索引的叶子结点存放的是一整行记录，而辅助索引叶子结点存放的是主键值。

B+树索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2~4层，这也就是说查找某一键值的行记录时最多只需要2到4次IO。

聚集索引

聚集索引(clustered index)就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。

聚集索引的好处：

• 聚集索引的存储并不是物理上连续的，而是逻辑上连续的，维护成本低
• 对于主键的排序查找和范围查找速度非常快，叶子节点就是用户所要查询的数据

一是前页通过双向链表连接，页按照主键的顺序排序；另一点是每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。
InnoDB只聚集在同一个页面中数据，包含相邻键值的页面可能相距甚远。

辅助索引

InnoDB存储引擎的辅助索引的书签就是相应行的聚集索引键。用户查询时，若当前索引无法检索出完整的内容，需要通过主键二次查询，这个过程称为回表

回表：非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表

联合索引

联合索引是指对表上的多个列进行索引。

联合索引的好处：

1. 索引键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据
2. 已经对第二个键值进行了排序处理，可以避免多一次的排序操作

覆盖索引

InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作

索引优化

覆盖索引，最左匹配原则是优化查询的常见思路

非主键自增时需要考虑长度、唯一性以及块移动的问题。插入效率下降，存在移动块的数据问题

---

参考资料：

1. 《MySQL技术内幕 InnoDB存储引擎》
2. 一篇文章讲透MySQL为什么要用B+树实现索引
3. MySQL hash索引及B+Tree索引
4. 如何理解Mysql的索引及他们的原理