MySQL-索引概述及结构

概述

        索引是一种有序的数据结构，用来帮助MySQL数据库高效获取数据
        在数据库中，除了基本的数据，其实数据库系统还维护一种满足特定算法查找的数据结构，这种数据结构以某种形式来指向我们在数据库存储的数据，我们可以通过这种数据结构来高效的获取我们想要的数据，而这种结构就是索引

🧐存在的意义

        虽说索引的存在能让我们很高效的获取数据，但这种高效是真的吗？我们现在才有两种方式对于同一张表进行查询，看在时间上会有什么情况。在这张表中，目前只有id为主键属于聚集索引(什么是聚集索引后文会提)，而其他的字段均是普通的字段未进行设置。现在采用age字段，当其两种方式(即设立为索引的age和不是索引的age)进行数据查找第15号胡青的信息，看会有什么样子的时间差异。
现在数据库有如下的数据

未给age创立索引时：执行语句：select * from emp where age=70;

给age创建索引结构：create index idx_emp_age on emp(age);
执行以后，查看该表下的索引结构，会发现有 idx_emp_age这个索引结构

这个时候再执行语句：select * from emp where age=70;

        会发现两者的时间有变化，虽然说没有到达1s的差距，但如果随着我们数据库的数据量增大起来的时候，这个时间的差值我想就是会很不一样了，这也就会造成用户在使用我们的网站等时候，进行数据查询过慢而觉得体验感不佳。所以在数据库中进行索引的设立对于我们开发项目是很有意义的，当然这也并不是说所有的都进行设立为索引就可以了，而是需要进行实际情况的考虑，因为索引建立的越多，会使得我们的数据库系统需要花费额外的精力对其进行维护，这会影响我们对表数据的增删效率，而原本只是为了增加我们查询的效率，结果最后造成了我们增删效率大打折扣，这是得不偿失的

        而这两种不同方式所进行的查询，之所以会有如此大的差别，这是在于为设立索引结构的时候，数据库系统底层对于我们想要查找的数据位置在哪里不清楚，只能从表头一条条进行遍历判断，这会需要花费很大量的时间，而建立了索引结构以后，底层的数据不再是简单的链式存储了，而是采用了二叉树的方式进行设立，每一次进行判断然后二分，这便使得我们的数据在查找的过程中快了许多

🧐索引的特点

        通过上述的简单的一个案例，相信大家对于索引的特点，为什么说其是一种高效的数据查询的数据结构了吧，但这只是其的好处，世上没有什么东西是完美的，所以对于索引其实也有属于他的缺点

优点	缺点
因为底层是二叉树的结构，所以可以使得数据库系统对于数据的检索效率有很大的提升，降低了数据库的IO成本	索引虽然是增加了数据库的查询效率，但是索引列也是需要占用空间的，这会使得原本可能可以存储一万条的数据，之后变得存储不了这么多，用空间换时间
通过索引对数据进行了排序，而不是像原本一样没有顺序，需要进行数据的从头到尾的查询，这降低了数据排序的成本，降低了CPU的消耗	因为底层采用了索引结构，对数据进行了排序，所以就会造成数据插入或者删除的时候，不再像之前那么便利了，降低了对表的更新速度，因为当有数据要增加或者删除的时候，就需要对索引进行一个调整，使得效率降低

🧐索引结构 位置

        MySQL的索引是在存储引擎层实现的，因为在存储引擎层中有不同的存储引擎，所以就会出现不同的存储引擎会有不同的索引结构
👇这是MySQL所支持的所有的索引结构

索引结构	描述
B+Tree索引	这是一种最常见的索引结构，大部分的存储引擎都支持这种索引结构
Hash索引	底层的数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围的查询(即只能进行精确匹配)
R-tree(空间索引)	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型
Full-text(全文索引)	是一种通过建立倒排索引，快速匹配文档的方式，类似于Lucene、Solar、ES

对于不同的存储引擎对于索引结构的支持

索引	InnoDB	MyISAM	Memory
B+tree索引	支持	支持	支持
Hash索引	不支持	不支持	支持
R-tree索引	不支持	支持	不支持
Full-text索引	5.6版本后支持	支持	不支持

而目前我们平常所说的索引，如果没有特别的指定，就是在说的B+树结构组织的索引

🧐索引结构的递变 二叉树

        首先，假如MySQL的底层索引结构采用的是二叉树的数据结构，对于其存储的比较理想的结构是如下图所示：

但这只是理想的情况下，加入存储的时候，是按照主键的顺序进行存储，这个时候就会发现有一个问题，即会形成一个单向链表的形式          所以，如果采用二叉树的方式作为索引结构，会出现：当数据是按照顺序进行存储的时候，会形成一个单链表，最后对于数据的查询底层还是类似于全表查询，并没有什么实质上的改进，而且随着数据的增加，层级会越来越大，这最后会使得检索速度变慢。

                                                                       
                                                                              ⬇改进

         选择采用选择红黑树的方式，因为红黑树是一种平衡二叉树。这样子就可以解决上述的第一个问题，数据按照顺序进行插入的时候，结果形成了一个单链表的形式。

         虽然可以解决这个问题，但是红黑树还是有一样的问题，就是随着数据的增加，层级会较深，最后还是会造成检索速度很慢。而也是因为这种原因，MySQL实质上并没有采用这种方式，而是采用了B+Tree的方式作为索引结构。接下来进行了解这种结构 B-Tree

         B树是一种多叉路衡查找树，相对于二叉树，它可以有多个分值，即多叉。

         ⭐ 树的度数指的是一个节点的子节点个数
         以一个最大度数为5的B树，这个B树的每个节点可以存储4个key，5个指针。这四个key分别对应5个指针。指针个数比key个数多一个，即(n)个key，会有(n+1)个指针，而每个key下面存储放着的就是对应的数据。即：度数为n的B树，其每个节点会有n各指针，n-1个key
        存储的动态形式，当有数据进行存储的时候，但存储的数据的数目没有查过四个的时候，数据会存储在同一行，当第五个数据存入进来以后，会根据已经存储的数据进行排序，然后将这五个数据中的中间位置的数据将其向上抛出，然后除中间数据以外的两边各两个数据，将会变成原本中间节点的子节点

        不管是有多少层，只要大于四就逐级向上送。最后想要往这个树里面存储数据的话，这个数据就是存储在每一个key的下面的。而且需要注意的是，在B树种，非叶子节点和叶子节点都会存放数据，而且只要节点存储的key的数量达到五个的时候，中间元素就向上进行裂变

B+Tree

        而对于B+TRee其底层与B树是一样的，是其一种变形。上文刚刚说B树是不管是否是叶子节点都会进行数据存储，而B+Tree这正好是想反的，其数据只存储在叶子节点上，如下图所示

        绿色框框框起来的部分，是索引部分，在这部分里面不进行数据的存储，进行起到一个索引的作用，用于在检索数据的时候作为一种导航
        红色框框框起来的部分，是进行数据存储的部分，在其叶子节点中进行了具体数据的存储。即所有的数据元素都会出现叶子节点上。而且需要注意的是：在叶子节点中他们会形成一个单向链表的形式，每个节点都会通过一个指针指向下一个节点。
        其动态存储的时候也是跟B树的一样，只是在分裂的时候，原本中间元素不仅会向上分裂，而且从中间元素的左边会有一个指针指向中间元素，形成一个链表，如下图所示

MySQL中的B+Tree

        MySQL中的B+树相对于原本的B+树进行了一个优化改进，在叶子节点的位置处，增加了一个指向相邻节点的链表指针，使得在叶子节点位置里形成了带有顺序指针的B+树，提高了区间访问的性能，利于排序。

        每一个节点都是存储在数据块当中的，也叫页。
这个页：Innodb存储引擎的逻辑存储结构中，一个页的默认存储大小是16KB

Hash结构

        哈希索引就是采用了一定的哈希算法，将键值通过哈希算法换成新的哈希值，然后映射倒对应的位置上，然后存储在哈希表中。

        每一个键值都有对应的一个哈希值，但随着数据的增加，肯定会出现一种情况即哈希值相同，映射到了同一个槽位上，产生了哈希冲突，而这个时候可以采用链表来解决问题，具有相同哈希值的键值关联在一起，形成一个链表

        而对于哈希索引它只能够实现等值的比较，不支持范围的查询。因为在存储的过程中，是通过进行哈希值的计算进行数据的存储，而没有什么顺序的，所以给了特定范围以后，由于数据不是连续按照顺序存储的，所以在查询的过程中不能进行范围的查询。也正因为是无序的，所以就无法利用索引来完成排序的 *** 作，不过这种结果的查询效率很高，只要进行一次检索查看相应的哈希值进行匹配就可以立马查找相应的数据，但这种情况是没有在哈希碰撞的前提下
        对于哈希索引，目前只有Memory存储引擎支持这种索引。而在InnoDB中提供了一种哈希索引的自适应功能，这个功能是指：MySQL会根据我们的查询条件，在指定的条件下会自动的将B+树索引自动的构建成哈希索引，这个过程是自动话的

疑问

为什么InnoDB存储引擎会选择B+树索引结构？
         ①对于二叉树：B+树索引的层级会更少，搜索的效率会更高
         ②而相对于B树，因为B树是不管是叶子节点还是子节点都会进行数据的存储，而B+树只有叶子节点才会进行数据的报错，这样子可以使得数据库存储更加大量的数据。原因：键值存储的位置是存储引擎逻辑结构中的页，一个节点最终是存放在一个磁盘块或者说是一页里面的，一页的存储的数据大小是固定的16KB，如果B树存储的话，不仅仅需要存储索引还有存储数据，那么页里面可以进行存储的键值数目就会减少，而对于B+树来说，因为只有叶子节点进行数据的存储，所以使得可以存储的键值会变多。而这个时候在相同的数据量的情况下，B+树的层级会相对来说更少，而B树面对相同的数据量，只能增加树的高度，导致性能降低。并且在B+树中，采用的是双向链表，这会对于叶子节点中的数据更加的方便进行搜索查找以及排序
         ③对于hash索引，这是因为hash索引只支持等值匹配，不支持范围 *** 作的
         所以最后InnoDB存储引擎中会选择B+树索引结构