索引概述
介绍：
索引（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。
