文章内容整顿自【博学谷狂野架构师】
索引（index）是帮忙MySQL高效获取数据的数据结构(有序)。在数据之外，数据库系统还保护着满足 特定查找算法的数据结构，这些数据结构以某种形式援用（指向）数据， 这样就能够在这些数据结构 上实现高级查找算法，这种数据结构就是索引。
优缺点：
长处：
- 进步数据检索效率，升高数据库的IO老本
- 通过索引列对数据进行排序，升高数据排序的老本，升高CPU的耗费
毛病：
- 索引列也是要占用空间的
- 索引大大提高了查问效率，但升高了更新的速度，比方 INSERT、UPDATE、DELETE
索引构造
| 索引构造 | 形容 |
|---|---|
| B+Tree | 最常见的索引类型，大部分引擎都反对B+树索引 |
| Hash | 底层数据结构是用哈希表实现，只有准确匹配索引列的查问才无效，不反对范畴查问 |
| R-Tree(空间索引) | 空间索引是 MyISAM 引擎的一个非凡索引类型，次要用于天文空间数据类型，通常应用较少 |
| Full-Text(全文索引) | 是一种通过建设倒排索引，疾速匹配文档的形式，相似于 Lucene, Solr, ES |
- 上述是MySQL中所反对的所有的索引构造，接下来，咱们再来看看不同的存储引擎对于索引构造的反对 状况。
| 索引 | InnoDB | MyISAM | Memory |
|---|---|---|---|
| B+Tree索引 | 反对 | 反对 | 反对 |
| Hash索引 | 不反对 | 不反对 | 反对 |
| R-Tree索引 | 不反对 | 反对 | 不反对 |
| Full-text | 5.6版本之后反对 | 反对 | 不反对 |
留神： 咱们平时所说的索引，如果没有特地指明，都是指B+树结构组织的索引。
二叉树
如果说MySQL的索引构造采纳二叉树的数据结构，比拟现实的构造如下：
如果主键是程序插入的，则会造成一个单向链表，构造如下：
所以，如果抉择二叉树作为索引构造，会存在以下毛病：
- 程序插入时，会造成一个链表，查问性能大大降低。
- 大数据量状况下，层级较深，检索速度慢。
此时大家可能会想到，咱们能够抉择红黑树，红黑树是一颗自均衡二叉树，那这样即便是程序插入数据，最终造成的数据结构也是一颗均衡的二叉树,构造如下:
然而，即使如此，因为红黑树也是一颗二叉树，所以也会存在一个毛病：
- 大数据量状况下，层级较深，检索速度慢。
所以，在MySQL的索引构造中，并没有抉择二叉树或者红黑树，而抉择的是B+Tree，那么什么是B+Tree呢？在详解B+Tree之前，先来介绍一个B-Tree。
B-Tree
B-Tree，B树是一种多路衡查找树，绝对于二叉树，B树每个节点能够有多个分支，即多叉。以一颗最大度数（max-degree）为5(5阶)的b-tree为例，那这个B树每个节点最多存储4个key，5个指针：
树的度数指的是一个节点的子节点个数。
咱们能够通过一个数据结构可视化的网站来简略演示一下。B-Tree Visualization (usfca.edu)(opens new window)
插入一组数据： 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。而后察看一些数据插入过程中，节点的变动状况。
特点：
- 5阶的B树，每一个节点最多存储4个key，对应5个指针。
- 一旦节点存储的key数量达到5，就会裂变，两头元素向上决裂。
- 在B树中，非叶子节点和叶子节点都会存放数据。
B+Tree
B+Tree是B-Tree的变种，咱们以一颗最大度数（max-degree）为4（4阶）的b+tree为例，来看一下其构造示意图：
咱们能够看到，两局部：
- 绿色框框起来的局部，是索引局部，仅仅起到索引数据的作用，不存储数据。
- 红色框框起来的局部，是数据存储局部，在其叶子节点中要存储具体的数据。
咱们能够通过一个数据结构可视化的网站来简略演示一下。B+ Tree Visualization (usfca.edu)(opens new window)
插入一组数据： 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。而后察看一些数据插入过程中，节点的变动状况。
最终咱们看到，B+Tree 与 B-Tree相比，次要有以下三点区别：
- 所有的数据都会呈现在叶子节点。
- 叶子节点造成一个单向链表。
- 非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点寄存的。
上述咱们所看到的构造是规范的B+Tree的数据结构，接下来，咱们再来看看MySQL中优化之后的B+Tree。
MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的根底上，减少一个指向相邻叶子节点的链表指针，就造成了带有程序指针的B+Tree，进步区间拜访的性能，利于排序。
Hash
MySQL中除了反对B+Tree索引，还反对一种索引类型---Hash索引。
- 构造
哈希索引就是采纳肯定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，而后存储在hash表中。
如果两个(或多个)键值，映射到一个雷同的槽位上，他们就产生了hash抵触（也称为hash碰撞），能够通过链表来解决。
- 特点
- Hash索引只能用于对等比拟(=，in)，不反对范畴查问（between，>，< ，...）
- 无奈利用索引实现排序操作
- 查问效率高，通常(不存在hash抵触的状况)只须要一次检索就能够了，效率通常要高于B+tree索引
- 存储引擎反对
在MySQL中，反对hash索引的是Memory存储引擎。 而InnoDB中具备自适应hash性能，hash索引是 InnoDB存储引擎依据B+Tree索引在指定条件下主动构建的。
思考题： 为什么InnoDB存储引擎抉择应用B+tree索引构造?
- 绝对于二叉树，层级更少，搜寻效率高；
- 对于B-tree，无论是叶子节点还是非叶子节点，都会保留数据，这样导致一页中存储的键值缩小，指针跟着缩小，要同样保留大量数据，只能减少树的高度，导致性能升高；
- 绝对Hash索引，B+tree反对范畴匹配及排序操作；
索引的分类
在MySQL数据库，将索引的具体类型次要分为以下几类：主键索引、惟一索引、惯例索引、全文索引。
| 分类 | 含意 | 特点 | 关键字 |
|---|---|---|---|
| 主键索引 | 针对于表中主键创立的索引 | 默认主动创立，只能有一个 | PRIMARY |
| 惟一索引 | 防止同一个表中某数据列中的值反复 | 能够有多个 | UNIQUE |
| 惯例索引 | 疾速定位特定数据 | 能够有多个 | |
| 全文索引 | 全文索引查找的是文本中的关键词，而不是比拟索引中的值 | 能够有多个 | FULLTEXT |
在 InnoDB 存储引擎中，依据索引的存储模式，又能够分为以下两种：
| 分类 | 含意 | 特点 |
|---|---|---|
| 汇集索引(Clustered Index) | 将数据存储与索引放一块，索引构造的叶子节点保留了行数据 | 必须有，而且只有一个 |
| 二级索引(Secondary Index) | 将数据与索引离开存储，索引构造的叶子节点关联的是对应的主键 | 能够存在多个 |
汇集索引选取规定:
- 如果存在主键，主键索引就是汇集索引
- 如果不存在主键，将应用第一个惟一（UNIQUE）索引作为汇集索引。
- 如果表没有主键，或没有适合的惟一索引，则InnoDB会主动生成一个rowid作为暗藏的汇集索 引。
汇集索引和二级索引的具体构造如下：
演示图：
- 汇集索引的叶子节点下挂的是这一行的数据 。
- 二级索引的叶子节点下挂的是该字段值对应的主键值。
接下来，咱们来剖析一下，当咱们执行如下的SQL语句时，具体的查找过程是什么样子的。
具体过程如下:
- 因为是依据name字段进行查问，所以先依据name='Arm'到name字段的二级索引中进行匹配查 找。然而在二级索引中只能查找到 Arm 对应的主键值 10。
- 因为查问返回的数据是*，所以此时，还须要依据主键值10，到汇集索引中查找10对应的记录，最 终找到10对应的行row。
- 最终拿到这一行的数据，间接返回即可。
回表查问： 这种先到二级索引中查找数据，找到主键值，而后再到汇集索引中依据主键值，获取 数据的形式，就称之为回表查问。
思考题：
以下两条SQL语句，那个执行效率高? 为什么?
A. select * from user where id = 10 ;
B. select * from user where name = 'Arm' ;
备注: id为主键，name字段创立的有索引；
解答：
- A 语句的执行性能要高于B 语句。
- 因为A语句间接走汇集索引，间接返回数据。 而B语句须要先查问name字段的二级索引，而后再查问汇集索引，也就是须要进行回表查问。
思考题：
- InnoDB主键索引的B+tree高度为多高呢?
答：假如一行数据大小为1k，一页中能够存储16行这样的数据。InnoDB 的指针占用6个字节的空间，主键假如为bigint，占用字节数为8. 可得公式：
n * 8 + (n + 1) * 6 = 16 * 1024，其中 8 示意 bigint 占用的字节数，n 示意以后节点存储的key的数量，(n + 1) 示意指针数量（比key多一个）。算出n约为1170。如果树的高度为2，那么他能存储的数据量大略为：
1171 * 16 = 18736； 如果树的高度为3，那么他能存储的数据量大略为：1171 * 1171 * 16 = 21939856。另外，如果有成千上万的数据，那么就要思考分表，波及运维篇常识
如果本文对您有帮忙，欢送
关注和点赞`，您的反对是我保持创作的能源。转载请注明出处！