索引的定义
索引是存储引擎用于快速查找数据纪录的一种数据结构
- 典型的例子就是查字典，通过查找目录快速定位到要查找的字。
- 数据是存储在磁盘上的，查询数据时，如果没有索引，会加载所有的数据到内存，依次进行检索，读取磁盘次数较多
索引的分类
索引按照索引列是否是主键，分为主键索引和辅助索引（除主键列索引外，其他列的索引都是辅助索引）
辅助索引又可分为唯一索引，普通索引，全文索引
- 主键索引：即主索引，根据主键建立索引，不允许重复，不允许空值；
- 唯一索引：用来建立索引的列的值必须是唯一的，允许空值；
- 普通索引：用表中的普通列构建的索引，没有任何限制；
- 全文索引：用大文本对象的列构建的索引，在MySQL5.6以下，只有MyISAM表支持全文检索。在MySQL5.6以上Innodb引擎表也提供支持全文检索；
ALTER TABLE 可以用来创建索引，包括普通索引、UNIQUE索引或PRIMARY KEY索引：
ALTER TABLE table_name ADD INDEX index_name (column_list)
ALTER TABLE table_name ADD UNIQUE (column_list)
ALTER TABLE table_name ADD PRIMARY KEY (column_list)
数据结构主要有BTree索引 和 哈希索引 。对于哈希索引来说，底层的数据结构就是哈希表，因此在绝大多数需求为单条记录查询的时候，可以选择哈希索引，查询性能最快；其余大部分场景，建议选择BTree索引。
正向索引和反向索引（倒排索引）
正向索引
正向索引：正排表是以文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。
“文档1”的ID > 单词1：出现次数，出现位置列表；单词2：出现次数，出现位置列表；…………。
“文档2”的ID > 此文档出现的关键词列表。
正排表结构如上图所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的。
- 添加文档时，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。
- 删除文档时，则直接找到该文档号文档对应的索引信息，将其直接删除。
- 查询文档时，对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。
正排表的工作原理简单，但是检索的效率太低
反向索引（倒排索引）
反向索引：倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。
倒排索引的结构如下：
“关键词1”：“文档1”的ID，“文档2”的ID，…………。
“关键词2”：带有此关键词的文档ID列表。
倒排索引的简单实例
假设文档集合包含五个文档，每个文档内容下图所示，在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。
中文和英文等语言不同，单词之间没有明确分隔符号，所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流，为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在如此处理结束后，我们可以得到最简单的倒排索引
“单词ID”一栏记录了每个单词的单词编号，第二栏是对应的单词，第三栏即每个单词对应的倒排列表。比如单词“谷歌”，其单词编号为1，倒排列表为{1,2,3,4,5}，说明文档集合中每个文档都包含了这个单词。
这是一个相对复杂些的倒排索引，与上图的基本索引系统相比，在单词对应的倒排列表中不仅记录了文档编号，还记载了单词频率信息（TF），即这个单词在某个文档中的出现次数，之所以要记录这个信息，是因为词频信息在搜索结果排序时，计算查询和文档相似度是很重要的一个计算因子，所以将其记录在倒排列表中，以方便后续排序时进行分值计算。
在图中的例子里，单词“创始人”的单词编号为7，对应的倒排列表内容为：（3:1），其中的3代表文档编号为3的文档包含这个单词，数字1代表词频信息，即这个单词在3号文档中只出现过1次，其它单词对应的倒排列表所代表含义与此相同。
上图所示索引系统除了记录文档编号和单词频率信息外，额外记载了两类信息，即每个单词对应的“文档频率信息”（对应图中的第三栏）以及在倒排列表中记录单词在某个文档出现的位置信息。
文档频率信息：代表了在文档集合中有多少个文档包含某个单词，之所以要记录这个信息，其原因与单词频率信息一样，这个信息在搜索结果排序计算中是非常重要的一个因子。
单词的位置信息并非索引系统中一定要记录的，位置信息只有在短语查询的时候才能派上用场。
以单词“拉斯”为例，其单词编号为8，文档频率为2，代表整个文档集合中有两个文档包含这个单词，对应的倒排列表为：{(3;1;<4>)，(5;1;<4>)},其含义为在文档3和文档5出现过这个单词，单词频率都为1，单词“拉斯”在两个文档中的出现位置都是4，即文档中第四个单词是“拉斯”。
使用倒排索引进行检索的大致流程
比如用户输入查询词“Facebook”，搜索系统查找倒排索引，从中可以读出包含这个单词的文档，这些文档就是提供给用户的搜索结果，而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序，计算文档和查询的相似性，按照相似性得分由高到低排序输出
索引结构
MySQL的BTree索引使用的是B树中的B+Tree，但对于主要的两种存储引擎的实现方式是不同的。
MyISAM的索引结构
MyISAM: B+Tree 叶节点的data域存放的是数据记录的地址。在索引检索的时候，首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”。
主键索引
叶节点的 data 域存放的是数据记录的地址
这里设表一共有三列,假设我们以 Col1 为主键,图中是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。
辅助索引
在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引,则此索引的结构如下图所示
同样也是一颗 B+Tree,data 域保存数据记录的地址。因此,MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其data 域的值,然后以 data 域的值为地址,读取相应数据记录。
InnoDB的索引结构
InnoDB: 其数据文件本身就是索引文件。相比MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按B+Tree组织的一个索引结构，树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。这被称“聚簇索引（或聚集索引）”。而其余的索引都作为辅助索引，辅助索引的data域存储相应记录主键的值而不是地址，这也是和MyISAM不同的地方。
主键索引
InnoDB存储引擎中表数据文件本身就是按 B+Tree 组织的一个索引结构。这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的 主键
上图是 InnoDB 主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集。
注意：
在 InnoDB 上采用自增字段做表的主键。因为 InnoDB数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:
这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。
辅助索引
与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说,InnoDB 的所有辅助索引都引用主键作为 data 域
例如,下图为定义在 Col3 上的一个辅助索引:
如果使用辅助索引作为搜索条件那么需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
回表
即： 找到对应的叶子节点，获取主键值，然后再通过聚簇索引中的B+树检索到对应的叶子节点，然后获取整行数据。这个过程叫做回表。回表就是先通过辅助索引扫描出数据所在的行，再通过行主键id取出索引中未提供的数据，即基于非主键索引的查询需要多扫描一棵索引树。
InnoDB 要求表必须有主键(MyISAM 可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL 自动为 InnoDB表生成一个隐含字段作为主键,类型为长整形。
聚簇索引和非聚簇索引
InnoDB 使用的是聚簇索引, 将主键组织到一棵 B+树中, 而行数据就储存在叶子节点上,
- 若使用"where id = 14"这样的条件查找主键, 则按照 B+树的检索算法即可查找到对应的叶节点, 之后获得行数据。
- 若对 Name 列进行条件搜索, 则需要两个步骤:
- 第一步在辅助索引 B+树中检索 Name, 到达其叶子节点获取对应的主键。
- 第二步使用主键在主索引 B+树种再执行一次 B+树检索操作, 最终到达叶子节点即可获取整行数据。
MyISM 使用的是非聚簇索引, 非聚簇索引的两棵 B+树看上去没什么不同, 节点
的结构完全一致只是存储的内容不同而已, 主键索引 B+树的节点存储了主键, 辅助键索引B+树存储了辅助键。 表数据存储在独立的地方, 这两颗 B+树的叶子节点都使用一个地址指向真正的表数据, 对于表数据来说, 这两个键没有任何差别。 由于索引树是独立的, 通过辅助键检索无需访问主键的索引树。
为了更形象说明这两种索引的区别, 我们假想一个表如下图存储了 4 行数据。 其中Id 作为主索引, Name 作为辅助索引。 图示清晰的显示了聚簇索引和非聚簇索引的差异
联合索引和最左前缀原则
在平时开发中，我们最常见的是单列索引（比如主键primary key），但在我们需要多条件查询的时候，也会建立联合索引。单列索引可以看成是特殊的联合索引。比如我们在user表上面，给name和phone建立了一个联合索引。
下面的演示都是基于user_innodb表：
DROP TABLE IF EXISTS `user_innodb`;
CREATE TABLE `user_innodb` (
`id` bigint(64) NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`gender` tinyint(1) NOT NULL,
`phone` varchar(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
ALTER TABLE user_innodb add INDEX comidx_name_phone(name,phone); -- 创建联合索引
单值索引的索引结构
所有非叶子结点的构成都是由两部分组成，索引值+指针，而单值索引说的就是在索引值这里就只有一个值（比如id），而联合索引在索引值可能会有多个值（比如name和phone）
联合索引的索引结构
由于 B+树本身是有序的，所以联合索引是从左到右的顺序来建立搜索树的（name在左边，phone在右边）。从上图可以看出来，name是有序的，phone是无序的。当name相等的时候，phone才是有序的。
联合索引查找数据的流程
比如，我们使用 where name=‘Bob’ and phone = ‘132xx’ 去查询数据的时候
- B+Tree 会优先比较 name 来确定下一步应该搜索的方向，往左还是往右
- 如果 name相同的时候再比较 phone
但是如果查询条件没有name，就不知道第一步应该查哪个节点，因为建立搜索树的时候name是第一个比较因子，所以用不到索引。
最左前缀原则
一个有趣的总结：
最左前缀原则：带头大哥不能死，中间兄弟不能断。
我们在建立联合索引的时候，一定要把最常用的列放在最左边。比如下面的三条语句，能用到联合索引吗？
1.使用两个字段，可以用到联合索引（注：两个字段的顺序颠倒并不影响，因为全值匹配时mysql会优化字段顺序）
EXPLAIN SELECT * FROM user_innodb WHERE name= '张三' AND phone='12345678910'
2. 使用左边的name字段，可以用到联合索引：
EXPLAIN SELECT * FROM user_innodb WHERE name= '张三'
3.使用右边的phone字段，无法使用索引，全表扫描：
EXPLAIN SELECT * FROM user_innodb WHERE phone= '12345678910'
