索引的数据结构（2）
常见索引概念
索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集 索引称为二级索引或者辅助索引。
1. 聚簇索引
特点：
1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内 的记录是按照主键的大小顺序排成一个 单向链表 。 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键 大小顺序排成一个 双向链表 。
2. B+树的 叶子节点 存储的是完整的用户记录。 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
优点：
数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非 聚簇索引更快 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多 个数据块中提取数据，所以 节省了大量的io操作 。
缺点：
插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影 响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为 不可更新
二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据
2. 二级索引（辅助索引、非聚簇索引）
概念：回表 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根 据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就 是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！
问题：为什么我们还需要一次 回表 操作呢？直接把完整的用户记录放到叶子节点不OK吗？
3. 联合索引
我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按 照 c2和c3列 的大小进行排序，
这个包含两层含义：
先把各个记录和页按照c2列进行排序。
在记录的c2列相同的情况下，采用c3列进行排序
注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。它的意 思与分别为c2和c3列分别建立索引的表述是不同的，
不同点如下：
建立 联合索引 只会建立如上图一样的1棵B+树。
为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。
3.4 InnoDB的B+树索引的注意事项
1. 根页面位置万年不动
2. 内节点中目录项记录的唯一性
3. 一个页面最少存储2条记录MyISAM中的索引方案
B树索引适用存储引擎如表所示：
即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MyISAM默认的索 引是Btree索引；而Memory默认的索引是Hash索引。
MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是 数据记录的地址 。
MyISAM索引的原理
下图是MyISAM索引的原理图。如果我们在Col2上建立一个二级索引，则此
如果我们在Col2上建立一个二级索引，则此索引的结构如下图所示：
MyISAM 与 InnoDB对比
MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区 别：
① 在InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次 回表 操作，意味着MyISAM中建立的索引相当于全部都是 二级索引 。
② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，索引文件仅保存数 据记录的地址。
③ InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通 过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个 可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐 含字段作为主键，这个字段长度为6个字节，类型为长整型。