索引的含义和特点
索引是创建在表上的，是对数据库表中一列或多列的值进行排序的一种数据结构，可以提高查询速度。索引类似于书籍目录，通过翻找目录，提取标题，可以快速定位到对应的章节
如上图，假如要执行 select * from book where title = '第一章'，只要在索引页找到对应标题即可找到对应章节，否则就只能把整本书翻一遍来寻找
索引有其明显的优势，也有不可避免的缺点：
索引的分类和操作
MysqL 的索引按照实现方式有如下类型：
- B-Tree 索引：指所有被索引的列都是排过序的，每个叶节点到根节点的距离都相等。因此，B-Tree 适用于查找某一范围内的数据，而且直接支持数据排序
- Hash 索引：基于哈希表实现，只支持精确查找，不支持范围查找和排序
- R-Tree 索引：空间索引，只有 MyISAM 引擎支持，主要用于 GIS 数据
- Full-text 索引：主要用于查找文本中的关键字，而不是直接与索引中的值相比较，用于解决
WHERE name LIKE "%word%"这类针对文本的模糊查询效率较低的问题
MysqL的索引按照使用逻辑有如下类型：
1. 普通索引
所谓普通索引，就是在创建索引时，不附加任何限制条件（唯一、非空等限制），可以创建在任何数据类型的字段上
创建表时直接创建索引
CREATE TABLE tablename(
propname1 type1 [CONSTRAINT1],propname2 type2 [CONSTRAINT2],......
INDEX|KEY [indexName] (propname1 [(length) [ASC|DESC]])
);
在已存在的表上通过 CREATE 语句创建索引
CREATE INDEX indexName ON tablename (propname [(length) [ASC|DESC]])
通过 ALTER TABLE 语句创建
ALTER table tablename ADD INDEX|KEY indexName(propname [(length) [ASC|DESC]])
2. 唯一索引
所谓唯一索引，就是在创建索引时，限制索引的值必须唯一，主键就是一种特殊的唯一索引
创建表时直接创建索引
CREATE TABLE tablename(
propname1 type1 [CONSTRAINT1],......
UNIQUE INDEX|KEY [indexName] (propname1 [(length) [ASC|DESC]])
);
在已存在的表上通过 CREATE 语句创建索引
CREATE UNIQUE INDEX indexName ON tablename (propname [(length) [ASC|DESC]])
通过 ALTER TABLE 语句创建
ALTER table tablename ADD UNIQUE INDEX|KEY indexName(propname [(length) [ASC|DESC]])
3. 全文索引
全文索引主要关联在 CHAR、VARCHAR 和 TEXT 字段上，以便能更加快速地查询数据量较大的字符串类型字段
创建表时直接创建索引
CREATE TABLE tablename(
propname1 type1 [CONSTRAINT1],......
FULLTEXT INDEX|KEY [indexName] (propname1 [(length) [ASC|DESC]])
);
在已存在的表上通过 CREATE 语句创建索引
CREATE FULLTEXT INDEX indexName ON tablename (propname [(length) [ASC|DESC]])
通过 ALTER TABLE 语句创建
ALTER table tablename ADD FULLTEXT INDEX|KEY indexName(propname [(length) [ASC|DESC]])
4. 多列索引
所谓多列索引（联合索引），是指在创建索引时关联多个字段。虽然可以通过所关联的字段进行查询，但是只有查询条件中使用了所关联字段中的第一个字段，多列索引才会被使用
创建表时直接创建索引
CREATE TABLE tablename(
propname1 type1 [CONSTRAINT1],......
INDEX|KEY [indexName] (propname1 [(length) [ASC|DESC]],propname2 [(length) [ASC|DESC]],......);
);
在已存在的表上通过 CREATE 语句创建索引
CREATE INDEX indexName ON tablename (propname1 [(length) [ASC|DESC]],......);
通过 ALTER TABLE 语句创建
ALTER table tablename ADD INDEX|KEY indexName(propname1 [(length) [ASC|DESC]],......);
5. 删除索引
DROP INDEX indexName ON tablename;
索引的数据结构
MysqL 索引相关的数据结构有两种，一种是 B+Tree，一种是 Hash，大多数情况下都使用 B+Tree 索引，有关 B+Tree 可参考：https://www.cnblogs.com/Yee-Q/p/13833316.html
之前我们说过，索引类似书籍目录，那么我们翻找目录也是一个查询行为，因为要选用合适的数据结构存储索引，提高查询效率
最直观的就是使用 Hash，使用方法就和书籍目录一样，对索引的 key 进行一次 Hash 计算就可以定位出数据存储的位置，但仅支持= 和 IN，不支持范围查询，因为无序所以不支持范围查询，同时数据库大数据存储时容易产生 Hash 冲突
说到提高查找效率，自然会想到平衡二叉树，可参考：https://www.cnblogs.com/Yee-Q/p/13750152.html
平衡二叉树的查询速度的确很快，但维护一棵平衡二叉树的代价是非常大的，通常来说，插入、更新和删除操作后，需要一次或多次左旋和右旋来维持树的平衡性
同时随着数据增多，平衡二叉树的高度会越来越高，大概 1000 条数据就有 9-10 层，那也就是说可能找一个数据需要 9-10 次 IO
为了解决平衡二叉树高度过高导致的 IO 问题，提出了 BTree 和 B+Tree 数据结构，两者都能降低树的高度，但同样的高度下，B+Tree 可以存储更多的索引，并且叶子结点间双向循环链表提高区间访问的性能，方便范围查找数据
使用 B+Tree 作为索引的结构如下：
我们发现，非叶子结点只存储冗余索引，用于检索数据，数据都存放在叶子节点，并且所有叶子节点都有指针相连，指向下一个叶子结点，假如要执行 select * from test_db where id = 29，只需要 3 次 IO 即可，并且根据 id 的每一次查询所需 IO 次数都是一样的，因为子树高度都一样
正因为 B+Tree 的结构特性，所以一般推荐使用整型的自增主键。如果使用非整形主键，如 UUID，索引建立时比较大小需要逐个字符转换为 ASCII 码进行比较，同时非整形主键占用空间更大，也就意味着一个索引页能够存放的索引数量不如整形主键。而且非整形主键下，每次插入主键的值近似于随机，因此新纪录都会插到现有索引页的中间某个位置，MysqL 就不得不为了将新记录插到合适位置而移动数据，增加磁盘开销。而使用整形自增主键，只需要往叶子结点后面放即可，大大减少索引页的分裂和移动数据产生的磁盘开销
上面的图是以主键索引构建 B+Tree，像这种叶子节点包含索引和数据的称为聚簇索引。每个表只能有一个聚簇索引，因为一个表中的记录只能以一种物理顺序存放，一般默认是主键索引
而对于普通索引，叶子结点仅存放索引和对应数据主键，也就是非聚簇索引。根据索引找到主键以后，再去主键索引构建的 B+Tree 查询数据，也就是回表。使用非聚簇索引虽然会导致回表，但能大大减少索引的占用空间，当数据发生修改时，也能降低索引的管理成本
再来看联合索引，，假设有：ALTER TABLE test_innodb ADD INDEX idex_name_age(name,age) USING BTREE，结构如图所示：
联合索引建立 B+tree 会以建立索引的顺序来排列数据，首先以 name 字段排序，再以 age 字段来排序。name 如果相同就以 age 来排列顺序，以此类推，最终查到对应数据的主键 ID 之后再回表，这也是联合索引最左匹配原则的原因，只有第一个字段 name 生效了，第二个字段 age 才能生效