文章内容整理自【博雪谷狂野架构师】索引（index）是帮助MySQL高效获取数据的数据结构（有序）。除了数据之外，数据库系统还维护着满足特定搜索算法的数据结构。这些数据结构以某种方式引用（指向）数据，因此可以在这些数据结构上实现高级搜索算法。这个数据结构是一个索引。.优缺点：优点：提高数据检索效率，降低数据库IO成本通过索引列对数据进行排序，降低了数据排序的成本，降低了CPU消耗缺点：索引列也是占用空间的索引，大大提高了查询效率，但是减少了更新速度，如INSERT、UPDATE、DELETE索引结构索引结构描述了B+Tree最常见的索引类型，大多数引擎都支持B+Tree索引Hash底层数据结构是用哈希表实现的，只有精确匹配的索引列R-Tree（spatialindex）空间索引是MyISAM引擎的一种特殊索引类型，主要用于地理空间数据类型，通常使用较少。Full-Text（全文索引）是一种索引，通过建立倒排索引的方法快速匹配文档，类似于Lucene、Solr、ES。以上就是MySQL支持的所有索引结构。接下来我们看看不同存储引擎对索引结构的支持情况。索引InnoDBMyISAMMemoryB+Tree索引支持支持Hash索引不支持不支持不支持不支持R-Tree索引不支持不支持不支持全文5.6版本后支持不支持指索引组织B+树结构。二叉树MySQL的索引结构如果采用二叉树的数据结构，那么理想的结构是这样的：如果顺序插入主键，就会形成一个单向链表，结构如下：因此，如果选择二叉树作为索引结构，会有以下缺点：顺序插入时会形成链表，查询性能会大大降低。在数据量大的情况下，层次较深，检索速度较慢。此时，你可能认为我们可以选择红黑树。红黑树是一种自平衡二叉树。即使顺序插入数据，最终的数据结构也是平衡二叉树。结构如下：不过，即使这样，由于红黑树也是二叉树，它也有一个缺点：在数据量大的情况下，层次较深，检索速度快是慢的。所以在MySQL的索引结构中，并没有选择二叉树或者红黑树，而是选择了B+Tree，那么什么是B+Tree呢？在详细讲解B+Tree之前，我们先介绍一个B-Tree。B-TreeB-Tree，B树是一种多路平衡搜索树。与二叉树相比，B树的每个节点都可以有多个分支，即多叉。以一棵最大度数（max-degree）为5（order5）的b树为例，那么这棵b树的每个节点最多可以存储4个key和5个指针：树的度是指子节点的数量。我们可以通过一个可视化数据结构的网站来简单演示一下。B树可视化(usfca.edu)(opensnewwindow)插入一组数据：1006516936890055678035215120023488815890100088120268250。然后观察一些数据插入过程中节点的变化。特点：5阶B树，每个节点最多存储4个key，对应5个指针。一旦一个节点存储的key数量达到5个，它就会被裂变，中间的元素会向上分裂。在B树中，非叶节点和叶节点都存储数据。B+TreeB+Tree是B-Tree的变种。我们以一个最大度数（max-degree）为4（4thorder）的b+tree为例来看它的结构图：可以看到有两部分：绿色框框住的部分是索引部分，只起到索引数据的作用，不存储数据。红框框出的部分是数据存储部分，具体的数据要存储在它的叶子节点中。我们可以通过一个可视化数据结构的网站来简单演示一下。B+TreeVisualization(usfca.edu)(opensnewwindow)插入一组数据：1006516936890055678035215120023488815890100088120268250。然后观察一些数据插入过程中节点的变化。最后我们可以看到，B+Tree与B-Tree相比，主要有以下三个不同点：所有的数据都会出现在叶子节点中。叶节点形成一个单向链表。非叶子节点只作为索引数据，具体的数据存放在叶子节点中。上面我们看到的结构就是标准的B+Tree数据结构。接下来我们看一下MySQL中优化后的B+Tree。MySQL索引数据结构优化了经典的B+Tree。在原有B+Tree的基础上，增加了一个指向相邻叶子节点的链表指针，形成了一个顺序指针的B+Tree，提高了区间访问的性能，方便了排序。HashMySQL除了支持B+Tree索引外，还支持一种索引类型——Hash索引。结构哈希索引是通过一定的哈希算法将键值转换成新的哈希值，映射到对应的槽位，然后存储到哈希表中。如果两个（或多个）key值映射到同一个slot，就会产生hashconflict（也称为hashcollision），可以通过链表来解决。特点Hash索引只能用于点对点比较（=,in），不支持范围查询（between,>,<,...）不能使用索引完成排序操作查询效率高，通常（没有hash冲突）只需要一次查找，效率通常比B+树索引存储引擎要高。在MySQL中，内存存储引擎支持哈希索引。InnoDB具有自适应哈希函数，哈希索引由InnoDB存储引擎在指定条件下基于B+Tree索引自动构建。思考题：为什么InnoDB存储引擎选择使用B+tree索引结构？与二叉树相比，层次更少，搜索效率更高；对于B-tree来说，无论是叶子节点还是非叶子节点，都会保存数据，这就导致一页中保存的key值的个数减少，指针的个数也减少。要保存大量数据，只能增加树的高度，导致性能下降；相对于Hash索引，B+tree支持范围匹配和排序操作；索引的分类在MySQL数据库中，索引的具体类型主要分为以下几类：主键索引、唯一索引、常规索引、全文索引。分类含义特征关键字主键索引是默认为表中的主键自动创建的。PRIMARY唯一索引只能有一个，避免同一张表中一个数据列的值重复。可以使用多个UNIQUE通用索引来快速定位特定数据。有多个全文索引。全文索引在文中寻找关键词，而不是比较索引中的值。可以有多个FULLTEXT。在InnoDB存储引擎中，根据索引的存储形式，可以分为以下两种：分类含义特点聚簇索引将数据存储和索引放在一起。索引结构的叶子节点必须有行数据，只有一个二级索引（SecondaryIndex），分别存储数据和索引。索引结构的叶子节点是关联的，对应的主键可以有多个聚簇索引选择规则：如果有主键，则主键索引为聚簇索引；如果没有主键，第一个唯一（UNIQUE）索引将被用作聚簇索引。如果表没有主键，或者没有合适的唯一索引，InnoDB会自动生成一个rowid作为隐藏聚集索引。聚簇索引和二级索引的具体结构如下：演示图：该行的数据挂在聚簇索引的叶子节点下。二级索引的叶子节点挂着字段值对应的主键值。下面我们来分析一下当我们执行下面的SQL语句时，具体的查找过程是怎样的。具体过程如下：由于查询是基于name字段的，所以先根据name='arm'在name字段的二级索引中进行匹配查找。但是在二级索引中只能查到Arm对应的主键值10。由于查询返回的数据是*，此时还需要根据主键值10在聚簇索引中查找10对应的记录，最终找到10对应的行。最后得到这一行的数据，直接返回。回表查询：这种先在二级索引中查找数据，找到主键值，然后根据主键值在聚簇索引中获取数据的方法称为回表查询。思考题：下面两条SQL语句，哪个效率更高？为什么？A.select*fromuserwhereid=10;B.select*fromuserwherename='Arm';备注：id是主键，由name字段创建有索引；答：A语句的执行性能高于B语句。因为A语句直接遍历聚簇索引，直接返回数据。B语句需要先查询name字段的二级索引，再查询聚簇索引，即需要回表查询。思考题：InnoDB主键索引的B+树高度是多少？答：假设一行数据的大小为1k，那么一个page可以存储16行这样的数据。InnoDB的指针占用6个字节空间，假设主键为bigint，占用字节数为8。可用公式：n*8+(n+1)*6=16*1024，其中8表示bigint占用的word节点个数，n表示当前节点存储的key个数，(n+1)表示指针个数（比key多一个）。计算n大约为1170。如果树的高度为2，那么它可以存储的数据量大约为：1171*16=18736；如果树的高度为3，那么它能存储的数据量大约是：1171*1171*16=21939856。另外，如果有几万条数据，那么还要考虑分表，涉及到操作和维护知识。如果本文对您有帮助，请关注点赞`，您的支持是我坚持创作的动力。转载请注明出处！
