MySQL索引 聚集索引

如果你想了解MySQL索引查询优化，你首先应该对MySQL数据组织结构、B-Tree索引、聚集索引，次要索引有一定的了解，才能够更好地理解MySQL查询优化行为。这里主要探讨MySQL InnoDB的聚集索引。

InnoDB数据存储结构

1.MySQL将所有数据都逻辑地存放在ib_data1文件中，我们称之为表空间。当然，你也可以一个表对应一个物理文件,将innodb_file_per_table设置成ON即可。
2.表空间又划为成段，有数据段(leaf node segment)，索引段(none-leaf node segment)，回滚段(rollback segment)。表空间由这些段和页组成，比如32页碎片页。
3.每段又划为成区，InnoDB每次最多可以申请4个区，即4M的存储空间。
4.每个区又划为成页，一个区划分成64页，每个页的大小是16KB，大小不能够改，这也固定了一个区的大小为4M。页是MySQL操作的最小逻辑单位。
5.InnoDB是面向行的，这就意味着数据行存放在页中，每页最多能记录7992行数据。
6.MySQL定义了不同作用的页类型，比如B-Tree Page, Undo Log Page等，我们最关心的是B-Tree Page(数据页)。实际数据就以这样的页逻辑实体存在于表空间,总是以B+树结构索引组织的。
7.换句话就说，实际数据一行一行地存放在B-Tree页中，这些页都放在数据段leaf node segment中。B-Tree Page是B+树的叶子节点。
8.一个B-Tree树，由7部分构成

• 8-1.File Header，这里记录了页在表空间的一些信息，比如上一页，下一页，属于哪个表空间等等
• 8-2.Page Header, 这里记录了页本身的一些存储信息。比如第一个记录的位置，记录数，最后插入记录行的位置，该页的索引ID等等
• 8-3.Infimum & Supermum Records, MySQL虚拟的二个行记录，用来界定记录的边界。分别代表此页中任何pk值还小的值和任何pk值还大的值。
• 8-4.user records, 实际存储的行记录。
• 8-5.free space,空闲空间，同样是链表结构。当一个数据记录删除后，就会加入到空闲链表中
• 8-6.page directory, 存放了记录的相对位置。注:聚集索引本身找不到具体的一条记录。而是通过 聚集索引找到该记录所在的页，然后再通过Page Directory进行二分查找找到具体数据。
• 8-7.File Trailer, MySQL InnoDB利用它来保证页完整地写入磁盘。

B-Tree索引查找数据

B+树，由B树和索引顺序访问方法演化面来的一种数据结构，较为复杂，常用于磁盘等存储设备的一种平衡查找树(所谓平衡，请查阅二叉树和平衡二叉树)。在B+树中,所有记录节点都按键值的大小顺序存放在同一层叶子节点中，各叶节子节点指针进行链接，每个叶子节点到达根节点的距离都是一样的。下图分别演示了G和H记录查询过程。

MySQL InnoDB一般按照每张表的主键构造一颗B+树，存放在表空间，其中整张表的行记录就是这颗B+树的叶子节点，存放在表空间的数据段(leaf node segment)。这就意味着数据行在表空间存储是有序的。MySQL通过B+树查找算法能够加速数据的访问，避免扫描整个表，大大减少了I/O逻辑操作。MySQL InnoDB查找某行数据的时候，通常先从root节点，找到子节点，直到找到叶子节点。叶子节点就是数据页，即(B-Tree类型页)，然后通过该页的Page Directory进行二分查找，找到数据行(上文有提到过，MySQL是不能通过B-Tree索引找到用户数据行)。

执行select * from user where uid = 92这样的一句查询。MySQL依照主键uid建立的B+树索引，MySQL从这颗B+树的根节点查找，一直找到叶子页的上一层节点，比较键值92>91(右边)最终找到数据叶，在数据叶中找到数据行。当然，也有可能找不到数据行(数据行根本不存在)。

InnoDB聚集索引

MySQL有没有支持聚集索引，取决于采用哪种存储引擎。MySQL InnoDB一定会建立聚集索引，所谓聚集，指实际数据行和相关的键值保存在一块(如上图)，这也决定了一个表只能有一个聚集索引，即MySQL不会一次把数据行保存在二个地方。InnoDB通常根据主键值(primary key)进行聚集，但是当一个表没有PK怎么办?InnoDB选取聚集索引参照列的顺序是
1.如果声声明了主键(primary key)，则这个列会被做为聚集索引
2.如果没有声明主键，则会用一个唯一且不为空的索引列做为主键，成为此表的聚集索引
3.上面二个条件都不满足，InnoDB会自己产生一个虚拟的聚集索引。
优点与缺点
聚集索引的优点,就是提高数据访问性能。聚集索引把索引和数据都保存到同一棵B+树数据结构中，并且同时将索引列与相关数据行保存在一起。这意味着，当你访问同一数据页不同行记录时，已经把页加载到了Buffer中，再次访问的时候，会在内存中完成访问，不必访问磁盘。不同于MyISAM引擎，它将索引和数据没有放在一块，放在不同的物理文件中，这样索引对应的是磁盘位置，不得不通过磁盘位置访问磁盘数据。

聚集索引的缺点同他的优点一样明显:
1.建立索引比较昂贵，尤其是插入新行或者主键被更新导至要分页(page split)的时候。建议在插入新行后，负载较低的夜间，通过OPTIMIZE TABLE优化表，因为必须被移动的行数据可能造成碎片。
2.聚集索引有可能比全表扫描还慢，尤其是存储得比较稀疏的时候。这要求设计的时候，尽量避免将UUID做为主键，推荐使用INT AUTO_INCREMENT列做为代理键。
3.次要索引(second index)可能会比预想的大，因为它们的叶子节点包含了被索引的主键列值。所以，不推荐使用64位的UUID，或者过长的pk值，会导致none-leaf segment占用更多的物理空间。
4.次要索引访问数据始终需要二次查找，而不是一次。次要索引叶子节点存储的不再是行的物理位置，而是主键值。通过次要索引首先找到的是pk值，再通过pk值找到数行据的数据叶，再通过数据叶中的Page Directory找到数据行。
设计Tips
根据上文描述，当你在做InnoDB表设计的时候，如果不需要任何特定列的聚集，就可以定义一个代理键(Surrogate Key)作为聚集索引的键值，该值与应用程序无关，推荐使用AUTO_INCREMENT列。这样会保证行是顺序插入并且能提高使用主键联接的性能。尽可能地避免随机(乱序)聚集键，像UUID，或者MD5一个值。这样的键值会破坏聚集索引带来的性能帮助。