一 什么是索引？

        实际上在上一篇介绍MYSQL的体系结构当中我们稍微提及了一点，在引擎层，我们提到不同的引擎对应的索引的实现方式，选择是不一样的。

        简单理解，索引（index）其实就是一种帮助MYSQL高效的获取数据的数据结构（有序排列），说到数据结构就会想到B树，红黑树，hash表等......那么作为一种数据结构，就需要进行维护，保存。例如对u有MyISAM引擎来说，其索引相关的信息都会保存在 xxx.MYI当中进行保存与维护。而在InnoDB存储引擎当中，对应的表结构，数据以及索引都存储在了xxx.ibd当中

二 索引的优缺点

        优点：

                1. 索引的添加可以让我们通过这种数据结构快速的定位对应添加所以的数据，加快查询效率，并且降低数据库的IO次数。

                2. 通过索引将表当中的数据先进行排序，那么就会加快之后数据排序的效率，降低排序成本，降低CPU资源的消耗

        缺点：

                1. 前面我们提到，索引实际上是一种数据结构，那么索引列也是需要占用磁盘的一些空间的。消耗了额外空间（但实际上磁盘比较便宜，其所占用的空间也比较少，可以忽略不计）

                2. 索引提高了数据查询的效率，但是反过来，降低了对应数据的更新以及新增的效率。

这是因为索引也是一种数据结构，我们在修改对应数据的同时，对应的索引的数据也需要进行修改，由此造成的数据的新增和插入速度的降低（对于一些业务来说，实际上增删改占用的比例远远少于查询）

三 索引结构

        MYSQL的索引是在对应的存储引擎层实现的，不同的存储引擎对应的有不同的索引结构，索引结构主要包含以下几种：

        B+Tree索引：最常见的索引类型，大部分的索引引擎都支持

        Hash索引：底层通过HASH表实现，因此决定了其只能够进行精确匹配，无法进行范围查询

        R-tree（空间索引）: 空间索引为MyISAM所特有的一种特殊的索引类型，主要用于地理空间数据类型

        Full-text（全文索引）:是一种通过建立倒排索引，快速匹配文档的方式，类似于Lucene,ES等

   

倒排索引拓展：

                倒排索引实际上也是一种数据结构，广泛用于信息检索系统，例如搜索引擎。其基本思想是将文档中的   单词  与   包含这些单词的文档列表  进行映射，从而快速查找包含特定单词的文档。

                倒排索引组成部分：

                        词项（Term）：文档中出现的唯一单词。

                        文档列表（Document List）：包含该词项的所有文档的标识符。

                工作原理：                 

                        索引构建：

                                在文档集合中提取所有的词项。

                                为每个词项创建一个列表，记录哪些文档包含该词项。

                        查询处理：

                                当用户搜索某个词时，系统可以快速查找该词项对应的文档列表，而不需要逐个扫描所有文档。

四：B+Tree  索引结构

        首先让我们从简单的二叉树开始进行分析，通过其优缺点，观察，总结为什么大部分的存储引擎都选择这个作为索引结构

        1. 二叉树（特指BST）

                首先是二叉树，但是实际上我们这里指的是搜索二叉树（Binary Search Tree，BST)，其主要特点是每个节点最多只能有两个子节点，每个节点的值都大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。这种结构使得搜索、插入和删除操作都能在平均情况下以较高的效率进行。

                在常规情况下，所有的数据均匀分布且并不是太多的情况下，二叉树可以大大提高数据的查询效率。

                但是这种数据结构存在很大的弊端：

                1. 如果数据分布并不均匀，流入根节点为50，之后输入的几个节点全部都比50小，那么就会导致对应的数据全部都在左边，从而形成了一条链，那么我们要查询的节点的数据的效率可能就从原本的O（ln n）变为了O（n）的时间复杂度 。

                2. 如果对应的数据量比较多的情况下，因为每一个父节点下只能最多存储两个子节点信息，那么数据一旦变多，就会导致对应的层数加深，使得查询效率降低。

                解决办法：使用一种可以自动调节高度的树以解决问题1这种情况 == 》 红黑树

        2. 红黑树

                红黑树是搜索二叉树的升级版本，其会自动调节对应节点之间的高度，使得各个节点之间的高度之差的绝对值不大于1，从而避免那种类似‘链状’的存储情况发生。

                但是同样的，红黑树也会避免不了我们在搜索二叉树所指出的问题二，也就是避免不了因为存储的数据的数据量的激增而导致对应层数加深 - > 从而导致查询效率大大下降。

                那么有没有一种数据结构能解决这种层级过深所导致的问题呢？

                解决方法：使用B-tree 树结构

        3.B-tree（多路平衡查找树）

                从名字我们就可以知道，多路指的是其字节点的个数不再只能是2，而是由我们进行人为的指定，这样就会在一定程度上减少对应数据大量存储的时候所导致的层数过深的情况的产生。

                因此在B-Tree当中，我们需要指定对应的最大度数(max-degree)，也就是对应一个节点的子节点个数。例如指定为5（5阶）的b-tree树，那么每一个节点最多可以存储4个KEY，以及5个指针信息。其一个节点下各个KEY的排列顺序也是从小到达进行排列。

                这里的5个指针分别指向的是5个范围之内的数据，以下图为例

                应当是：  小于20的数

                                大于20小于30的数

                                大于30小于40的数

                                大于40小于50的数

                                大于50的数 

                如上图当前节点已经存在了4个KEY，那么之后再进行存储就会将中间的数向上提取，之后将中间左边以及右边的数向两边搁置，我再添加一个KEY = 35

                那么加入之后当前节点的KEY当中，35是中间的数据，向上提。如图所示：

                而且还要注意的一点是，在B-Tree数当中，其所有节点既存放键(key) 也存放数据(data)

        4.B+Tree

               B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。

               相比较于B-Tree，B+Tree与其有以下几点不同:

                        1>B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。

                        2>B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。

                B+树当中所有的元素都会出现在叶子节点当中，并且叶子节点之间的关系是一种链状排列，形成单向链表。

                 节点不再存放对应的KEY的值，而是仅仅只存放一个KEY，数据均放置在叶子节点当中，这样的设置就表明对应KEY其实就是一个索引，指向对应数据所在位置。

五 hash索引

        hash索引实际上背后是依据hash表构建的，存放方式是键值对的方式，其会将对应的KEY的值  ==> 通过一些效率比较高的哈希算法得到新的hash值 ==> 映射到对应的内存槽位上，然后将对应的数据存放在这个槽位上。

        但是多个数据的哈希值是可能重复的，也就是说通过KEY计算出来的hash值一样，这就叫做哈希冲突，发生哈希冲突时，哈希表使用链表的解决方式，也就是说即使当前的槽位上已经存在数据了，那么我也可以存放，我会将这个新的数据的值存放在此链表的末尾。但是这样也存在一定问题，聪明的你能想想为什么吗？告诉我吧 ^ - ^

        如图：

        这样就可以高效的通过KEY直接获取到对应的数据信息了

        但是哈希表的这种查找，存储数据的方式注定了其无法进行多条数据的查找，只能够做到一对一精确查找。否则就会降低查找效率。

六  思考题 - 为什么InnoDB选择B+Tree作为默认的索引结构？

        通过以上对于各个索引结构的分析，我们不难分析出为什么

        1. 相比较于BTS以及红黑树，B+树既能够避免链状结构的产生，从而导致查询效率的降低；也能够通过自定义最大度数来放置因为数据过多导致树的层级过深造成的查询速度变慢。因此，两者都OUT。

        2.相比较于B-Tree树来说，使用B+树仅仅只在叶子节点存放对应的KEY的数据，而B树在所有的子节点都存放有对应的VALUE，我们还知道索引这种数据结构是在存储引擎当中实现的，那么其存储则会跟随存储引擎存放在本地磁盘，而索引的存放空间是有限的，一个节点信息会存放在 ’一页‘ 上，‘一页’存储数据的大小为16K。而B树每一个子节点都会保存数据，就会导致一页种存储的键值减少，指针跟着减少，想要同样保存大量的数据，只能够增加树的高度，从而导致性能的下降，因此OUT。

        3. 相比于HASH，HASH虽然查询效率高，但是只能够进行精准匹配，无法进行范围性的查找，获取数据，因此OUT。

之后也会更新MYSQL相关内容，关注不迷路，兄弟们  ^ - ^