MySQL索引 聚集索引
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(右边)最终找到数据叶，在数据叶中找到数据行。当然，也有可能找不到数据行(数据行根本不存在)。
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一个值。这样的键值会破坏聚集索引带来的性能帮助。
