各个数据页可以组成一个`双向链表`，而每个数据页中的记录会按照主键值从小到大的顺序组成一个`单向链表`，每个数据页都会为存储在它里边儿的记录生成一个`页目录`，在通过主键查找某条记录的时候可以在`页目录`中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录  `目录项记录`和普通的`用户记录`的不同点： * `目录项记录`的`record_type`值是1，而普通用户记录的`record_type`值是0。 * `目录项记录`只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有`InnoDB`自己添加的隐藏列。 * `min_rec_mask`，只有在存储`目录项记录`的页中的主键值最小的`目录项记录`的`min_rec_mask`值为`1`，其他别的记录的`min_rec_mask`值都是`0`。 #### 聚簇索引 1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义： * 页内的记录是按照主键的大小顺序排成一个单向链表。 * 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。 * 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。 2. `B+`树的叶子节点存储的是完整的用户记录。 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。 我们把具有这两种特性的`B+`树称为`聚簇索引`，所有完整的用户记录都存放在这个`聚簇索引`的叶子节点处。这种`聚簇索引`并不需要我们在`MySQL`语句中显式的使用`INDEX`语句去创建（后边会介绍索引相关的语句），`InnoDB`存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在`InnoDB`存储引擎中，`聚簇索引`就是数据的存储方式（所有的用户记录都存储在了`叶子节点`），也就是所谓的索引即数据，数据即索引。 **将数据和索引放到一起存储**，索引结构的叶子节点保留了数据行。每个表一定会有一个聚集索引，整个表的数据存储以b+树的方式存在文件中，**b+树叶子节点中的key为主键值，data为完整记录的信息；非叶子节点存储主键的值。** #### 二级索引(非聚簇索引) 和聚簇索引区别 * 使用记录`c2`列的大小进行记录和页的排序，这包括三个方面的含义： * 页内的记录是按照`索引`列的大小顺序排成一个单向链表。 * 各个存放用户记录的页也是根据页中记录的`索引`列大小顺序排成一个双向链表。 * 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的`索引`列大小顺序排成一个双向链表。 * `B+`树的叶子节点存储的并不是完整的用户记录，而只是`索引列+主键`这两个列的值。 * 目录项记录中不再是`主键+页号`的搭配，而变成了`索引列+页号`的搭配。 如果返回的列不在非聚簇索引树种, 则还需要根据得到的主键去聚簇索引里查询详细信息, 此过程叫**回表** **覆盖索引**：索引字段覆盖了查询语句涉及的字段，直接通过索引文件就可以返回查询所需的数据，不必通过回表操作。 ## 索引 * 每个索引都对应一棵`B+`树，`B+`树分为好多层，最下边一层是叶子节点，其余的是内节点。所有`用户记录`都存储在`B+`树的叶子节点，所有`目录项记录`都存储在内节点。 * `InnoDB`存储引擎会自动为主键（如果没有它会自动帮我们添加）建立`聚簇索引`，聚簇索引的叶子节点包含完整的用户记录。 * 我们可以为自己感兴趣的列建立`二级索引`，`二级索引`的叶子节点包含的用户记录由`索引列 + 主键`组成，所以如果想通过`二级索引`来查找完整的用户记录的话，需要通过`回表`操作，也就是在通过`二级索引`找到主键值之后再到`聚簇索引`中查找完整的用户记录。 * `B+`树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是`联合索引`的话，则页面和记录先按照`联合索引`前边的列排序，如果该列值相同，再按照`联合索引`后边的列排序。 * 通过索引查找记录是从`B+`树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了`Page Directory`（页目录），所以在这些页面中的查找非常快。 ## 索引的代价 * 空间 每建立一个索引都要为它建立一棵`B+`树，每一棵`B+`树的每一个节点都是一个数据页，一个页默认会占用`16KB`的存储空间，一棵很大的`B+`树由许多数据页组成 * 时间 每次对表中的数据进行增、删、改操作时，都需要去修改各个`B+`树索引。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。 `WHERE`子句中的几个搜索条件的顺序对查询结果没有影响, MySQL的优化器是很智能的. 1. `B+`树索引在空间和时间上都有代价，所以没事儿别瞎建索引。 2. `B+`树索引适用于下边这些情况： * 全值匹配 * 匹配左边的列 * 匹配范围值 * 精确匹配某一列并范围匹配另外一列 * 用于排序 * 用于分组 3. 在使用索引时需要注意下边这些事项： * 只为用于搜索、排序或分组的列创建索引 * 为列的基数大的列创建索引 * 索引列的类型尽量小 * 可以只对字符串值的前缀建立索引 * 只有索引列在比较表达式中单独出现才可以适用索引 * 为了尽可能少的让`聚簇索引`发生页面分裂和记录移位的情况，建议让主键拥有`AUTO_INCREMENT`属性。 * 定位并删除表中的重复和冗余索引 * 尽量使用`覆盖索引`进行查询，避免`回表`带来的性能损耗。