高性能索引优化策略（四）：聚集索引和非聚集索引数据结构及优劣对比
聚集索引并不是一个单独的索引类型，实际上是一种数据存储的方式。聚集索引的实现细节各有不同，在InnoDB引擎中，聚集索引实际上是将索引和数据行使用同样的结构存储在一个二叉树中。
如果数据表中有聚集索引，则数据行实际上是存在所以的叶子节点。“聚集”的形式实际是指相邻键值的数据行是邻近存储的。因为一行数据不能存储在两个叶子节点上，因此在数据表中只能有一个聚集索引。由于是存储引擎负责索引的实现，因此并不是全部的存储引擎都支持聚集索引。在这里我们只讨论InnoDB，但支持聚集索引的存储引擎实现聚集索引的原理都大同小异。
下图展示了数据记录在聚集索引的存储布局。注意，叶子节点包含了完整的数据行，而其他节点仅仅只有索引。在这个图中，索引列使用的是整数。
聚集索引数据存储
有些数据库服务器允许我们选择对哪个索引进行聚集，但MySQL的任意内置的存储引擎都不支持这么做。InnoDB使用主键对数据进行聚集，这意味着上图的索引列实际上是主键列。
如果数据表没有定义主键，InnoDB会选择使用唯一的非空列（Not Null）索引替代。如果没有这样的索引，InnoDB会定义一个隐藏的主键去完成数据聚集（因此，数据表最好自己定义主键）。InnoDB的只能在一个数据页中进行数据聚集，因此即便是临近的索引值的数据存储页也可能间隔很远。
一个聚集主键能够提高性能，但同样也可能导致严重的性能问题。因此，你应当谨慎考虑聚集的使用，尤其是当你将一个数据表的存储引擎从InnoDB改为其他引擎时。
聚集索引具有如下的优势：
- 可以将相关联的数据行保持邻近存储。例如，邮箱应用中，你可以使用user_id进行聚集。这种情况下，你可以从磁盘的很少的分页中获取用户的全部消息。而如果不使用聚集索引，每条消息都可能需要单独占用磁盘I/O。
- 数据访问很快：聚集索引将索引和数据同时存储在二叉树中，因此从聚集索引中获取数据行比起非聚集索引的查询来说快很多。
- 使用了覆盖索引的查询可以利用主键中包含在叶子节点的数据值。
如果你在设计数据表和查询时充分利用这些好处，将能显著提升性能。然而，聚集索引也有缺点：
- 聚集能对受限于I/O负载的情况很大改善，但如果数据是在内存而与磁盘无关，那聚集实际上帮不上什么忙。
- 插入速度严重依赖插入次序。按照主键顺序插入数据是InnoDB表中最快的方式，如果加载数据不是按照主键次序，那在完成大量数据的加载后，最好是使用优化表（OPTIMIZE TABLE）功能重新组织一下数据表。
- 更新聚集索引列的代价很高，因为这会强制InnoDB去移动更新的数据行到一个新的位置。
- 当新的数据行插入时或行的主键更新引起数据行移动，数据表已经构建的聚集索引会分页（page split）。分页情况发生在新的数据行需要移入一个放满数据的存储页时。存储引擎必须将存储页分成两部分去存储新的行，这会导致数据表占用更多的磁盘空间。
- 聚集表在全表扫描时可能会更慢，尤其是数据行密集度不高或者是因为分页导致存储不连续。
- 非聚集索引（Secondary Index）会比你预期的存储要大，这是因为叶子节点包含了主键列引用的数据行。
- 非聚集索引访问时需要两次索引查找而不是一次。这个可能感觉有点费解，其原因在于非聚集索引存储的是数据行指针。记住，叶子节点并并不是存储引用行的实际物理位置，而是该行的主键值。这意味着，使用非聚集索引查询数据行时，存储引擎首先通过非聚集索引找到其叶子节点，然后通过叶子节点的主键再找到数据行的值。这相当于进行了两次二叉树的查找，在InnoDB中，自适应的哈希索引可以减少这种概率。
InnoDB和MyISAM数据布局比较
聚集和非聚集数据布局，以及主键和非聚集索引的差别可能让人困惑和奇怪。我们可以比较一下InnoDB和MyISAM对下面数据表的存储布局来深入了解一下。
CREATE TABLE layout_test (
col1 int NOT NULL,
col2 int NOT NULL,
PRIMARY KEY(col1),
KEY(col2)
);
假设这个表产生了主键1到10000的数据，采用的是随机顺序插入的，然后在通过OPTIMIZE TABLE进行了优化。换言之，数据在磁盘上是有序排列的，但行可能是随机顺序的。数据列col2使用1-100的随机值填充，因此存在很多的重复值。
MyISAM的数据布局更简单些，MyISAM按照插入的顺序在磁盘存储数据，如下图所示。我们以0开始展示了数据行编号，由于每一行的大小是固定的，MyISAM可以从表最开始的地方根据所需要的字节数来找到任意行（MyISAM内部并不总是使用行号，而是根据行是否固定大小或可变大小使用不同的策略）。
数据次序
这种结构使其很容易构建索引，下图绘制了一个数据系列，这个图中，物理的细节（例如存储页）被抽象隐藏，在索引中只有节点。每个索引的叶子节点可以简单地包含对应的行号，在下图是其主键。在这里隐藏了一些细节，例如在前一个节点后有少个内部的二叉树节点，但这对于理解非聚集存储引擎基础的数据布局来说并不重要。
MyISAM聚集索引结构
那对于col2列的索引怎么样。实际上，它和其他索引一样。
MyISAM非聚集索引结构
事实上，在MyISAM中，主键和其他索引并没有结构上的区别。主键只是一个简单的唯一、不为空的索引，仅仅是名字命名为主键而已。
InnoDB由于聚集索引的组织方式，存储同样数据的结构十分不同，如下图所示。
InnDB聚集索引结构
初看这张图，感觉似乎和MyISAM的并无太大不同，但是仔细再看一遍，实际上这个图展示了整张数据表，而不只是索引。由于聚集索引在InnoDB中已经是整张表了，因此这里没有像在MyISAM中的独立的行存储。
InnoDB的聚集索引每个叶子节点都包含主键值、事务ID、回滚指针以便进行事务和MVCC（Multi Version Cocurrent Control, 并发多版本控制），以及剩下的其他列（示例数据表就是col2）。如果主键作用在一个列的前缀上，InnoDB会在其他列中包含主键列的完整值。
同样，与MyISAM相比，非聚集索引和聚集索引有很大不同。相比于存储行指针，InnoDB非聚集索引的叶子节点存储的是主键值，由主键再指向数据。这个策略在行移动或数据分页需要维护非聚集索引时，减少了很多工作。使用行主键值作为指针意味着索引更大，但也意味着InnoDB可以移动行而不需要去更新非聚集索引的指针。下图展示了非聚集索引的数据布局，可以看到非聚集索引实际上存储了主键的值。
InnoDB非聚集索引结构
这些图展示了二叉树的叶子节点，但是我们隐藏了非叶子节点的细节。InnoDB中非叶子节点的二叉树的每一个节点都包含索引列，并另外附加了下一个层级的节点的指针（有可能是非叶子节点也可能是叶子节点）。这个对聚集索引和非聚集索引都一样。下图展示了InnoDB和MyISAM的索引的抽象结构对比，从中可以看出二者的不同之处。
InnoDB和MyISAM存储结构对比
