MySQL索引 - 聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。当表有聚簇索引的时候，它的数据行实际存放在索引的叶子页（leaf page）中。术语“聚簇”表示数据行和相邻的健值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
聚簇索引的存放如下图：
由上图注意到，叶子页包含了行的全部数据，但是节点页只包含了索引列。在这张图中，索引列包含的是整数值。
聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。InnoDB 只聚集在同一个页面中的记录。包含相邻健值的页面可能相距甚远。
聚簇索引优点：
- 可以把相关数据保存在一起。例如实现电子邮箱时，可以根据用户 ID 来聚集数据，这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引，则每封邮件都可能导致一次磁盘 I/O。
- 数据访问更快。聚簇索引将索引和数据保存在同一个 B-Tree 中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
- 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
聚簇索引缺点：
- 聚簇数据最大限度地提高了 I/O 密集型应用的性能，但如果数据全部都放在内存中，则访问的顺序就没那么重要了。聚簇索引也就没扫描优势了。
- 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到 InnoDB 表中速度最快的方式。但如果不是按照主键顺序加载数据，那么加载完成后最好使用 OPTIMIZE TABLE 命令重新组织一下表。
- 更新聚簇索引列的代价很高，因为会强制 InnoDB 将每个被更新的行移动到新的位置。
- 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂（page split）”的问题。当行的主键值要求必须将这一行插入到某个已满的页时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂的操作。页分裂会导致表占用更多的磁盘空间。
- 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。
- 二级索引（非聚簇索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。
- 二级索引访问需要两次索引查找，而不是一次。
为什么二级索引需要两次索引查找？因为二级索引的叶子节点保存的不是指向行的物理位置的指针，而是行的主键值。这就意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后根据这个值去聚簇索引中查找到对应的行。这里做了重复的操作：两次 B-Tree 查找而不是一次。
InnoDB 和 MyISAM 的数据分布对比
聚簇索引和非聚簇索引的数据分布有区别，以及对应的主键索引和二级索引的数据分布也有区别。使用以下的表来做测试：
1 CREATE TABLE layout_test( 2 col1 int NOT NULL, 3 col2 int NOT NULL, 4 PRIMARY KEY(col1), 5 KEY(col2) 6 );
假设该表的主键取值为1 ~ 10 000，按照随机顺序插入并使用 OPTIMIZE TABLE 命令做了优化。换句话说，数据在磁盘上的存储方式已经是最优，但行的顺序是随机的。列 col2 的值是从 1 ~ 100 之间随机赋值，所以有很多重复值。
MyISAM 的数据分布。MyISAM 的数据分布非常简单，它按照数据插入的顺序存储在磁盘上，如图所示：
由上图 5-4 可以看出，行的旁边显示了行号，从 0 开始递增。因为行是定长的，所以 MyISAM 可以从表的开头跳过所需的字节找到需要的行（MyISAM 并不总是使用图 5-4 中的“行号”，而是根据定长还是变长的行使用不同策略）。
这种分布方式很容易创建索引。下面显示的一系列图，隐藏了页的物理细节，只显示索引中的“节点”，索引中的每个叶子节点包含“行号”。图 5-5 显示了表的主键。
col2 的索引如下图所示：
如上图 5-6 可以看出 col2 列的索引和其它索引没有什么区别。事实上，MyISAM 中主键索引和其他索引在结构上没有什么不同。主键索引就是一个名为 PRIMARY 的唯一非空索引。
InnoDB 的数据分布。因为 InnoDB 支持聚簇索引，所以使用非常不同的方式存储同样的数据。InnoDB 以如图 5-7 所示的方式存储数据。
由上图可以看出，InnoDB 的聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和 MVCC 的回滚指针以及所有的剩余列（在这个例子中是 col2）。如果主键是一个列前缀索引，InnoDB 也会包含完整的主键列和剩下的其他列。
还有一点和 MyISAM 的不同是，InnoDB 的二级索引和聚簇索引很不相同。InnoDB 二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。
这样的策略减少了当出现行移动或者数据页分裂时二级索引的维护工作。使用主键值当作指针会让二级索引占用更多的空间，换来的好处是，InnoDB 在移动行时无须更新二级索引中的这个“指针”。
图 5-8 可以看出表的 col2 索引，每一个叶子节点都包含了索引列（这里是 col2），紧接着是主键值（col1）。
图 5-9 是描述 InnoDB 和 MyISAM 如何存放表的抽象图，可以很容易的看出 InnoDB 和 MyISAM 保存数据和索引的区别。
在 InnoDB 表中按主键顺序插入行
最好避免使用随机的（不连续且值的分布范围非常大）的列做聚簇索引（可以使用 int 型的自增 ID），特别是 I/O 密集型的应用。例如：使用 UUID 来作为聚簇索引则会很糟糕：它使得聚簇索引的插入变得完全随机，这是最坏的情况，使得数据没有任何聚集特性。
下面我们用两张表来做基准测试。第一个表使用整数 ID 插入 userinfo 表：
1 CREATE TABLE `userinfo`( 2 `id` int unsigend NOT NULL AUTO_INCREMENT, 3 `name` varchar(64) NOT NULL DEFAULT '', 4 `email` varchar(64) NOT NULL DEFAULT '', 5 `password` varchar(64) NOT NULL DEFAULT '', 6 `dob` date DEFAULT NULL, 7 `address` varchar(255) NOT NULL DEFAULT '', 8 `city` varchar(64) NOT NULL DEFAULT '', 9 `state_id` tinyint unsigend NOT NULL DEFAULT '0', 10 `country_id` smallint unsigend NOT NULL DEFAULT '0', 11 PRIMARY KEY (id), 12 UNIQUE KEY email (email), 13 KEY country_id (country_id), 14 KEY state_id (state_id), 15 KEY state_id_2 (state_id,city,address) 16 ) ENGINE = InnoDB
第二个例子是 userinfo_uuid 表，除了主键改为 UUID，其余和前面的 userinfo 表完全相同。
1 CREATE TABLE `userinfo`( 2 `uuid` varchar(36) NOT NULL, 3 ... 4 );
现在已经创建好了两个测试表了，接下来我们依次插入100万条记录。然后继续依次插入300万条记录，使索引的大小超过服务器的内存容量。结果如下图：
注意到向 UUID 插入行不仅花费的时间更长，而且索引占用的空间也更大。这一方面是由于主键字段更长；另一方面是由于页分裂和碎片导致的。
图 5-10 是往第一个表插入数据时，索引发生的变化。
如图 5-10 可以看出，因为主键的值是顺序的，所以 InnoDB 把每一条记录都存储在上一条记录的后面。当达到页的最大填充因子时（InnoDB 默认的最大填充因子是页大小的 15/16，留出部分空间用于以后修改），下一条记录就会写入新的页中。一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满（二级索引页可能是不一样的）。
图 5-11 是往 UUID 表插入数据时，索引发生的变化。
由图 5-11 可知，因为新行的主键值不一定比之前插入的大，所以 InnoDB 无法简单地总是把新行插入到索引的最后，而是需要给新行寻找合适的位置 —— 通常是已有数据的中间位置 —— 并且分配空间。这会增加很多的额外工作，并导致数据分布不够优化。下面是总结的一些缺点：
- 写入的目标页可能已经刷到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB 在插入之前不得不先找到并从磁盘读取目标页到内存中。这将导致大量的随机 I/O。
- 因为写入是乱序的，InnoDB不得不频繁的做页分裂操作，以便为新的行分配空间。页分裂会导致移动大量数据，一次插入最少需要修改三个页而不是一个页。
- 由于频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。
把这些随机值载入到聚簇索引之后，也许需要做一次 OPTIMIZE TABLE 来重建表并优化页的填充。
从这个案例可以看出，使用 InnoDB 时应该尽可能地按主键顺序插入数据，并且尽可能地使用单调增加的聚簇健的值来插入新行。
参考资料：
高性能MySQL（第3版）