Mysql索引数据结构及原理

浅浅的花香味﹌ 2023-06-11 04:27 17阅读 0赞

## 什么是索引？ ##

**索引**（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：==索引是一种数据结构。这些数据结构以某种方式引用（指向）数据，==这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

**索引特点**：加速查询，但更新和增加慢

**索引的几种分类：**  
1、UNIQUE,唯一索引，可以为null,但不能重复  
2、INDEX 普通索引  
3、Promary key 主键索引  
4、fulltext index 全文索引，效率慢

**创建索引的方式**

ALTER table 表名 ADD 索引类型 索引名（字段名）
    CREATE index 索引名 on 表名（字段名）
    #当有多个字段时，用逗号隔开

**删除索引**

Drop Index 索引名 on 表名

组合索引具备最左原则  
即多个字段的组合索引，只有当包含最左侧索引字段时，索引才会生效。原理和二叉树查找相似，只有找到第一个节点才能往下查找

## 索引的数据结构 ##

索引的数据结构有很多种，Mysql使用的索引是B+树结构，下面一一讨论

### 二叉树 ###

左子树的键值小于根的键值，右子树的键值大于根的键值   
![该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次][1_1_2_2_n_n_ _1_2_2_3_3_3_ _ 6 _ 2.3]  
该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次

**缺点**：当数据都大于根节点的数据时，整个结构就会向右倾斜，变成一个链表，导致查询深度加大。

## 平衡二叉树 ##

为了解决二叉树极端情况下出现的问题，引入平衡二叉树，java8中新引入的红黑树就是它的一个实现，它有如下特点:  
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树  
**它的查找次数与数量无关，只与其高度有关**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70]  
上图左边45的左子树高度为2，右子树是空的，差距为2，非平衡二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 1]  
图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。  
右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。

平衡二叉树失去平衡后可以通过旋转的方式得到平衡二叉树  
有二叉左旋和二叉右旋两种方式，这里暂不讨论

# 平衡多路查找树（B-Tree） #

B-Tree是为了解决磁盘IO问题涉及的一种平衡树，  
**需要了解：**  
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。  
InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位，但一页的大小往往比一个block大很多  
因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB  
InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

**B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块**

## B+Tree ##

InnoDB存储引擎用的就是B+TREE做索引  
**b+tree和b-tree的区别在于：**  
1.B+Tree的所有根节点都不带有任何数据信息，只有索引信息，所有数据信息全部存储在叶子节点里(B+Tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。)  
2、又由B树的性质可以得到，所有叶子节点都会在同一层，B+Tree会以一个双向链表的形式将所有叶子节点的信息全部串联起来，这样，想遍历所有数据信息只需要顺序遍历叶子节点就可以了，方便又高效  
3、B+Tree的查询效率是非常稳定的，因为所有信息都存储在了叶子节点里面，从根节点到所有叶子节点的路径是相同的。

innodb索引分类：（按数据的存储方式）  
聚簇索引(clustered index)  
1) 有主键时，根据主键创建聚簇索引  
2) 没有主键时，会用一个唯一且不为空的索引列做为主键，成为此表的聚簇索引  
3) 如果以上两个都不满足那innodb自己创建一个虚拟的聚集索引  
辅助索引(secondary index)  
非聚簇索引都是辅助索引，像复合索引、前缀索引、唯一索引

## 哈希索引 ##

除了B+树之外，还有一种常见的是哈希索引。

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。  
**缺点：**  
1、哈希索引也没办法利用索引完成排序；

2、不支持最左匹配原则；

3、在有大量重复键值情况下，哈希索引的效率也是极低的---->哈希碰撞问题；

4、不支持范围查询；

[1_1_2_2_n_n_ _1_2_2_3_3_3_ _ 6 _ 2.3]: /images/20230531/6f97d767f86f41c6853b7074ec2ca810.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70]: /images/20230531/fa1f6e99cee04d6c850c83857f6874ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzAwMDMw_size_16_color_FFFFFF_t_70 1]: /images/20230531/52cffe9718e34a35bb86b587583bcf55.png