MySQL InnoDB索引那点事儿 _MySQL

总结下之前看到的一些关于MySQL索引原理的内容，好记性不如烂笔头。
1. B+树我们知道InnoDB的索引是以B+树的形式组织的。B+树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。
下面是B+树的示例：

文章插图

B+树把所有的数据都存储在叶子节点中，内部节点只存放关键字和孩子指针，因此最大化了内部节点的分支因子，所以B+树的遍历也更加高效。
B+树通常用于数据库和操作系统的文件系统中，其特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树适合作为数据库的基础结构，完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问（随机访问即给出任意一个地址，要求返回这个地址存储的数据）但是容量较小。而硬盘的随机访问要经过机械动作（1磁头移动、2盘片转动），访问效率比内存低几个数量级，但是硬盘容量较大。典型的数据库容量大大超过可用内存大小，这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。
使用B+树作为索引结构有如下优势：
1.B+树非叶子节点上是不存储数据的，仅存储键值（聚集索引）。
之所以这么做是因为在数据库中页的大小是固定的，InnoDB中页的默认大小是 16KB 。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
另外真实数据库中的B+树应该是非常扁平的，其阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO 。
2.B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。因而B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。
2.InnoDB页存储结构2.1 存储结构存储引擎中所有数据都被存储在表空间中，表又由Segment(段)、Extent(区)、Page(页)组成，如下为MySQL技术内幕中介绍的InnoDB逻辑存储结构：

文章插图

1.表空间：在默认情况下，InnoDB存储引擎有一个共享表空间 ibdata1，所有的数据都放在这个表空间内.如果启用了innodb_file_per_table参数，每张表的表空间只存放数据、索引和插入缓冲bitmap页，其他的数据如undo信息、插入缓冲、double write buffer等还是存放在共享表空间中。
2.段：常见的段有数据段、索引段、回滚段等。数据段是B+树的叶子结点，索引段为B+树的非叶子结点

文章插图

3.区：区由连续页组成，每个区大小固定为1MB，为保证区中page的连续性通常InnoDB会一次从磁盘中申请4-5个区。在默认page的大小为16KB的情况下，一个区则由64个连续的page 。
4.页：页是InnoDB磁盘管理的最小单位也叫做块，默认大小为16kB 。常见的页有数据页、undo页、系统页等。类型为B-tree Node的页存放的即是表中行的实际数据
5.行：InnoDB存储引擎中数据是按行进行存放的，每个页中最多存放7992行记录
2.2 页结构Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最小单位，与数据库相关的所有内容都存储在这种Page结构里。每个Page使用一个32位的int值来唯一标识，这也正好对应InnoDB最大64TB的存储容量（16Kib * 2^32 = 64Tib）。一个Page的结构如下所示：