索引实现方式

☞ MyISAM   MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图：

  这里设表一共有三列，假设我们以 Col1 为主键，则上图是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中，主索引和辅助索引(Secondary key)在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：

  同样也是一颗 B+Tree，data 域保存数据记录的地址。因此，MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址，读取相应数据记录。MyISAM 的索引方式也叫做非聚集索引(辅助索引)

☞ InnoDB   虽然 InnoDB 也使用 B+Tree 作为索引结构，但具体实现方式却与 MyISAM 截然不同。第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道，MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在 InnoDB 中，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

  上图是 InnoDB 主索引(同时也是数据文件)的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键(MyISAM可以没有)，如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形。第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。下图以英文字符的 ASCII 码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

  了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了 InnoDB 的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在 InnoDB 中不是个好主意，因为 InnoDB 数据文件本身是一颗 B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

索引的操作

☞ 创建索引

# 第一种方式，unique 可以省略，如果加上了 unique，表示创建唯一索引。
create [unique] index index_name on tb_name(col_name[(length)]);# 第二种方式
alter tb_name add [unique] index index_name on (col_name[(length)]);

☞ 删除索引

# 索引修改是先删除索引，再重建索引。
drop index index_name on tb_name;

☞ 查看索引

show index from tb_name;

数据检索过程

唯一记录检索

如上图，所有的数据都是唯一的，查询 105 的记录，过程如下： ① 将 P1 页加载到内存 ② 在内存中采用二分法查找，可以确定 105 位于[100,150)中间，所以我们需要去加载 100 关联 P4 页 ③ 将 P4 加载到内存中，采用二分法找到 105 的记录后退出

查询某个值的所有记录

如上图，查询 105 的所有记录，过程如下： ① 将 P1 页加载到内存 ② 在内存中采用二分法查找，可以确定 105 位于[100,150)中间，所以我们需要去加载 100 关联 P4 页 ③ 将 P4 加载到内存中，采用二分法找到最有一个小于 105 的记录，即 100，然后通过链表从 100 开始向后访问，找到所有的 105 记录，直到遇到第一个大于 100 的值为止

范围查找

数据如上图，查询[55,150]所有记录，由于页和页之间是双向链表升序结构，页内部的数据是单项升序链表结构，所以只用找到范围的起始值所在的位置，然后通过依靠链表访问两个位置之间所有的数据即可，过程如下： ① 将 P1 页加载到内存 ② 内存中采用二分法找到 55 位于 50 关联的 P3 页中，150 位于 P5 页中 ③ 将 P3 加载到内存中，采用二分法找到第一个 55 的记录，然后通过链表结构继续向后访问 P3 中的 60、67，当 P3 访问完毕之后，通过 P3 的 nextpage 指针访问下一页 P4 中所有记录，继续遍历 P4 中的所有记录，直到访问到 P5 中所有的 150 为止。

模糊匹配

查询以f开头的所有记录，过程如下： ① 将 P1 数据加载到内存中 ② 在 P1 页的记录中采用二分法找到最后一个小于等于 f 的值，这个值是 f，以及第一个大于 f 的，这个值是 z，f 指向叶节点 P3，z 指向叶节点 P6，此时可以断定以f开头的记录可能存在于[P3,P6)这个范围的页内，即 P3、P4、P5 这三个页中 ③ 加载 P3 这个页，在内部以二分法找到第一条 f 开头的记录，然后以链表方式继续向后访问 P4、P5 中的记录，即可以找到所有已 f 开头的数据

查询包含f的记录，包含的查询在 sql 中的写法是 %f%，可以看一下上面的数据，f 在每个页中都存在，我们通过 P1 页中的记录是无法判断包含f的记录在那些页的，只能通过 io 的方式加载所有叶子节点，并且遍历所有记录进行过滤，才可以找到包含 f 的记录。以如果使用了 %值% 这种方式，索引对查询是无效的。

最左匹配原则   当 b+ 树的数据项是复合的数据结构，比如(name，age，sex)的时候，b+ 树是按照从左到右的顺序来建立搜索树的，比如当(张三，20，F)这样的数据来检索的时候，b+ 树会优先比较 name 来确定下一步的所搜方向，如果 name 相同再依次比较 age 和 sex，最后得到检索的数据；但当(20，F)这样的没有 name 的数据来的时候，b+ 树就不知道下一步该查哪个节点，因为建立搜索树的时候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查询。比如当(张三，F)这样的数据来检索时，b+ 树可以用 name 来指定搜索方向，但下一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是 F 的数据了， 这个是非常重要的性质，即索引的最左匹配特性。