索引概述
介绍：
索引（index）是帮助MySQL高效获取数据的数据结构（有序）。在数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。
执行一条sql语句：select * from user where age = 45
无索引的情况：
会从第一条记录开始匹配，判断age是否为45；直到匹配成功之后，因为不确定后面会不会还有age = 45的情况，所以仍然会继续匹配，直到把整张表都遍历一遍。这种情况称为全表扫描，性能极低。
有索引的情况：
以二叉树为例（并不是真实的索引结构，只是以二叉树为例），如果要对age建立索引，当要往表中插入一条数据时，就要维护二叉树的节点，而这个节点要指向这行数据的地址。
当要45和36匹配时，45比36大，所以往右边走，跟48匹配；
比48小，所以往左边走，就找到了45。
找到45之后，就能通过这个节点的指向找到这一行数据。有索引的情况下只需匹配3次就能找到对应的数据。这个搜索效率是非常高效的。
索引的优缺点：
优势：
- 提高数据检索的效率，降低数据库的IO成本
- 通过索引列对数据进行排序，降低数据排序的成本，降低CPI的消耗
劣势：
- 索引列也是要占用空间的
- 索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行INSERT、UPDATE、DELETE时，效率降低
索引结构
在MySQL体系结构中，索引是在第三层，存储引擎层实现的。这也意味着，根据存储引擎的不同，索引的结构也会不同。主要包含以下几种：
- B+Tree索引：最常见的索引类型，大部分引擎都支持B+树索引。
- Hash索引：底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询。
- R-tree（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少。
- Full-text（全文索引）：是一种通过简历倒排索引，快速匹配文档的方式。类似于Lucene，Solr，ES。
二叉树
从二叉树的根节点开始，比根节点大的走右边，比根节点小的走左边。这样往往会有两个缺点：
- 顺序插入时，会形成一个链表，查询性能大大降低。
- 大数据量情况下，层级较深，检索速度慢。
为了解决第一个问题，可以利用红黑树：
红黑树虽然解决了第一个问题，但是依然会存在第二个问题，大数据量情况下，层级较深，检索速度慢。
B-Tree（多路平衡查找树）
以一棵最大度数（max-degree）为5（5阶）的b-tree为例（每个节点最多存储4个key，5个指针）：
比20小的数在第一个子节点，20到30之间的数在第二个子节点，以此类推。
简单介绍一下B-Tree的裂变方式：
通过数据结构可视化网站来演示
- 一个节点中有4个元素
-
当我再往里面插入元素的时候，中间的元素会往上裂变，把两边的元素分成两个子节点
-
以此类推，当某子节点中的元素达到了裂变条件，也会像步骤2一样裂变
比如在下面元素中再插入元素8
当插入元素8之后，元素6就会往上裂变，而裂变的元素会跟元素3处于同一个节点中，直至根节点再次发生裂变
-
当子节点需要往父节点发生裂变后，父节点也需要裂变时，就会往上裂变一层，如下图
当插入元素17时，子节点就会发生裂变，而元素15裂变到根节点后，根节点也需要发生裂变了
B+Tree
B+Tree实际上是B-Tree的变种，以一棵最大读书（max-degree）为4（4阶）的B+Tree为例：
在B+Tree中，叶子节点形成一个单向链表。所有的元素都会出现在叶子节点，叶子节点用来存放数据，而黄色部分的非叶子节点只起到索引的作用。
裂变过程跟B-Tree一样，但是裂变到上层节点的元素在子节点也会存在，并不会消失。如：
再插入一个元素12，该B+Tree就达到了裂变的条件
虽然11裂变到了上一层节点，但是在叶子节点中，11元素依然会保留。
与B-Tree的区别：
- 所有的数据都会出现在叶子节点
- 叶子节点形成一个单项列表
MySQL中B+Tree的索引结构
MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。
Hash索引
哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。
如果两个（或多个）键值，映射到同一个槽位上，他们就产生了hash冲突（也成为hash碰撞），可以通过链表来解决。
如下表，要为name字段创建一个hash索引，
需要先算出这个表中每一行数据的hash值，再拿到name字段是所有值，针对name字段的所有值，通过内部的哈希函数算法去计算每一个name值应该落在哪个hash表的对应槽位上。
如金庸，算出来槽位值为005，那么在005槽位中就会存储金庸(key)和58dda（值），58dda代表的是金庸这个key，对应的这一行所代表的hash值。
出现hash冲突时，就会在对应的槽位里形成一个链表，如下图杨逍计算出来的槽位值也是005。
Hash索引特点：
- Hash索引只能用于对等比较（=，in），不支持范围查询（between，>，<，…）。
- 无法利用索引完成排序操作。
- 查询效率高，通常只需一次检索就可以了，效率通常要高于B+Tree索引。
存储引擎支持：
在MySQL中，支持hash索引的是Memory引擎，而InnoDB中具有自适应hash功能（在指定的条件下会自动的将B+Tree索引构建为Hash索引）。
为什么InnoDB存储引擎选择使用B+Tree索引结构
- 相对于二叉树，层级更少，搜索效率高。
- 对于B-Tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低。
- 相对Hash索引，B+Tree支持范围匹配以及排序操作。
第2点说明：如下图所示。在InnoDB中，页是磁盘操作的最小单元，一个页的大小是固定的16k。如果在非叶子节点中也存储数据，就占用了页的一部分空间，导致一页中存储的键值减少。从而导致存储相同的数据，用的页就会多，也就是增加了树的高度。
索引分类
索引主要分为4类：
- 主键索引
- 唯一索引
- 常规索引
- 全文索引
主键索引只能有一个，其他索引可以有多个。
聚集索引和二级索引
在InnoDB存储引擎中，根据索引的存在形式，又可以分为：聚集索引、二级索引。
在很多地方会把二级索引称为辅助索引或非聚集索引
聚集索引选取规则：
- 如果存在主键，主键索引就是聚集索引。
- 如果不存在主键，将使用第一个唯一索引作为聚集索引。
- 如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引。
聚集索引结构图：
上图中，第一个叶子节点5中的row，值的就是id为5的这一行对应的数据。
二级索引结构图：
根据name字段再建立一个索引，是一个二级索引。二级索引的叶子节点下面挂着的是叶子节点的name值对应的这一行元素的id。
回表查询
当执行select * from user where name = 'Arm'的时候，会走下面的索引，找到Arm之后，就拿到了ID。然后根据ID再走一次聚集索引。这个过程称为回表查询。
回表查询指先走二级索引找到对应的主键值，再根据主键值到聚集索引中拿到这一行的行数据。
总结：
聚集索引B+Tree的叶子节点下面挂着的是这一行的数据。
二级索引B+Tree的叶子节点下面挂着的是对应的id。
执行效率判断
问题一：以下SQL语句那个执行效率高？为什么？
1. select * from user where id = 10;
2. select * from user where name = 'Arm'
备注：id为主键，name字段创建的有索引
SQL1的执行效率高。因为只用经过一次聚集索引就可以查出来。
SQL2需要进行回表查询，先经过二级索引查出id，再通过聚集索引查出行数据。
问题二：InnoDB主键索引的B+Tree高度有多高呢？
假设：一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键即使为bigint，占用字节数为8。
高度为2：n * 8 + (n+1) * 6 = 16*1024，算出n约为1170，1171 * 16 = 18736。
