数据库索引概念、索引测试和优化、及其底层结构

你的名字 2021-12-15 01:53 327阅读 0赞

### 文章目录 ###

*   *  一、索引概念
     *   *  1.1 索引分类
         *  1.2 索引的使用
     *  二、索引测试
     *  三、索引原则
     *  四、索引结构
     *   *  4.1 基础概念
         *  4.2 MySQL 索引实现
         *  4.3 索引使用策略及优化

## 一、索引概念 ##

> MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构，索引的本质：索引是数据结构。

### 1.1 索引分类 ###

*  主键索引 (PRIMARY KEY)
    
     *  唯一不可重复，只有一列可以作为主键
 *  唯一索引 (UNIQUE KEY)
    
     *  避免重复的列出现，多个列可以标识为唯一索引
 *  常规索引 (KEY/INDEX)
    
     *  默认的，使用 index 或者 key 设置
 *  全文索引 (FullText)
    
     *  在特定的引擎下才有，比如 MYSIAM
     *  快速定位数据

### 1.2 索引的使用 ###

1、 在创建表的时候给字段增加索引  
2、 创建完毕后，增加索引

普通索引的创建

create table user8(id int primary key,
    	name varchar(20),
    	email varchar(30),
    	index(name) --在表的定义最后，指定某列为索引
    );
    -- 创建完之后增加索引
    alter table user9 add index(name);

全文索引创建

-- 当对文章字段或有大量文字的字段进行检索时，会使用到全文索引
    CREATE TABLE articles (
    	id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
    	title VARCHAR(200),
    	body TEXT,
    	FULLTEXT (title,body)
    )engine=MyISAM; -- 指定引擎为 MySIAM
    
    -- 使用全文索引查数据
    SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('database');`
    
    -- 可以用explain工具看一下，是否使用到索引
    explain select * from articles where body like '%database%'\G;
    
    -- 显示索引
    -- 如果 key 对应的为 null ，说明没有索引
    show keys from 表名
    show index from 表名;
    desc 表名;
    
    -- 删除主键索引
    alter table 表名 drop primary key;`
    
    -- 其他索引的删除
    alter table 表名 drop index 索引名;`
    alter table user10 drop index idx_name;	`
    
    -- 还有一种方法：drop index 索引名 on 表名
    `drop index name on user8;`

## 二、索引测试 ##

mysql 是可以编程的  
下面是建立十万行数据

-- 插入100万条数据 49.245 sec
    DELIMITER $$ -- 写函数之前必须要有标志
    CREATE FUNCTION mock_data()
    RETURNS INT
    BEGIN
        DECLARE num INT DEFAULT 1000000;
        DECLARE i INT DEFAULT 0;
        WHILE i<num DO
    	-- 插入语句
    	INSERT INTO app_user(`name`,`email`,`phone`,`gender`,`password`,`age`)
    	VALUES(CONCAT('用户',i),'1309334291@qq.com',CONCAT('18',FLOOR(RAND()*((999999999-1000000000)+1000000000))),FLOOR(RAND()*2),UUID(),FLOOR(RAND()*100));  
    	SET i = i+1;
        END WHILE;
        RETURN i;
    END;
    
    SELECT mock_data();

查询测试

SELECT * FROM app_user WHERE `name`='用户9999';

耗时 4.982 s![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center]

通过 explain 查看到共找了 2912447 行数据  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 1]

下面通过索引测试

索引创建需要时间，底层本质是一颗树

-- create index 索引名 on 表（字段）
    CREATE INDEX id_app_user_name ON app_user(`name`);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 2]

创建完之后，我们再测试查询语句的时间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 3]  
可以看到速度明显提高

注意：索引在小数据用处不大，在大数据量的时候区别十分明显

## 三、索引原则 ##

*  索引不是越多越好
 *  不要对经常变动的数据加索引
 *  小数据量表不加索引
 *  索引一般加在频繁查询的字段上

## 四、索引结构 ##

> 前言：MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型

索引类型

*  哈希索引
 *  **B Tree 树索引**
 *  全文索引

哈希底层是哈希表，将哈希码存储在索引中，同时在哈希表中保存指向每个数据行指针，检索可以一次定位，查询效率很高

缺点

*  无法使用范围查询，无法过滤，只能等值比较查询
 *  无法对数据进行排序操作
 *  每次需要全表扫描查询

**下面主要内容分为三个部分来讨论 B/B+ 树索引**

第一部分：主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

第二部分：结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分：根据上面的理论基础，讨论MySQL中高性能使用索引的策略。

### 4.1 基础概念 ###

**B 树特性**

*  是一颗平衡多叉树，所有的叶子节点都在同一层
 *  每个节点存储M/2 ~ M个关键字(M 代表的是多叉树)
 *  所有的关键字在树中只出现一次
 *  每个节点都存储 key 和 value，可通过 key 找到数据记录地址
 *  非叶子节点和叶子节点都有可能被命中

**插入步骤**

1.  如果树为空，直接插入该节点
2.  如果树非空，利用插入法找到插入的位置
3.  插入进去检查是否满足B数特性，即元素小于M
4.  如果等于M需要进行分裂
    
    4.1 申请新节点  
    4.2 找到需要分裂节点的中间位置  
    4.3 将节点中间右侧的元素及其孩子节点搬移到新节点  
    4.4 最后将中间数据和新生成的节点插入到双亲节点

**查找步骤：**

首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针

\[B 树示意图\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 4]

> 当然以上这些都不是很重要，主要掌握 B 树和 B+树的区别

B+树结构，在 B 树的基础上进行改进

*  B+ 树给叶子节点增加了链指针,指向相邻叶子节点的指针，可以范围查询，提高区间访问性能
 *  B+ 树所有的关键字都在叶子节点中，非叶子节点相当于叶子节点的索引
 *  B+ 树非叶子节点没有数据，总是在叶子节点命中，所以性能稳定  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 5]
 *  B+ 树由于非叶子节点没有数据值，所以可以存储更多的元素， IO 次数比B树少

**索引性能**

根据 B 树分析，检索一次需要最多访问 h 个节点，数据库系统设计者巧妙利用了 **磁盘预读原理**，将一个节点的大小设为一个页，这样每个节点只需要一次IO就可以完全载入，另外还需要保证每次新建一个节点的时候都是直接申请一个页的空间，这样一个节点在物理上也存储在一个页里，就可以实现一个节点一次IO，所以说如果一个节点可以存储更多的元素，效率就会比较高

> 磁盘预读原理：由于磁盘IO速度比较慢，为了尽可能减少IO磁盘次数，所以在每次读取的时候都会预读，比如只需要一个字节，磁盘也会从这个位置顺序向后读取一定长度的数据放入内存，这是依据了**局部性原理**(当一个数据被用到时，其附近的数据也通常马上被用到)

**为什么不用红黑树作为索引？**

**由于红黑树高度比较深，逻辑上很近的父子节点，可能物理上会相差很远，无法利用局部性原理，所以红黑树效率明显比 B 树差很多**

仅供了解：我们知道磁盘读取的速度要远远低于主存的读取，因为读取磁盘需要带有机械运动，寻找对应的扇区数据需要寻道时间和旋转时间.所以尽可能减少IO磁盘次数，是提高性能的最直接的方式

> 当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间

### 4.2 MySQL 索引实现 ###

**MyISAM 索引实现**

在 MySQL 中，索引属于存储引擎级别的概念，不同的存储引擎对索引的实现方式自然也是不一样的

MyISAM 引擎使用 B+ 树作为索引结构，叶子节点的 data 域存放的是数据记录的地址，MyISAM的索引方式也叫做 **非聚集索引**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 6]  
在 MyISAM 中，主索引和辅助索引在结构中没有任何区别，只是主索引要求 key 是唯一的，辅助索引key是可以重复的

MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录

**InnoDB 索引实现**

和 MyISAM 的实现方式截然不同

InnoDB 的数据文件本身就是索引文件，对于 MyISAM 索引文件和数据文件是分离的，索引文件仅仅保存数据记录的地址，而在 InnoDB 中，表数据文件本身就是按 B+ 树组织的一个索引结构，这颗树的叶子节点 data 域保存了完整的数据记录，这个索引的 key 是数据表的主键.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 7]

这种索引也叫 **聚集索引**，由于 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键，如果没有则系统自动选定或者生成一个唯一标识的数据记录列作为主键

第二个与 MyISAM 不同的是 InnoDB 的辅助索引 data 域存储相应记录主键的值，而不是地址，换句话说，InnoDB 的所有辅助索引都引用主键作为data 域

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 8]

这样的实现方式使得按主键搜索的效率十分高效，但是对于辅助索引需要检索两遍索引，首先检索辅助索引获得主键，然后用主键到主索引中检索获得数据记录地址

这也就是为什么不建议过长的字段作为主键，因为所有的辅助索引都引用主索引，过长的主索引会令辅助索引变得过大，再比如用非单调的字段作为主键在 InnoDB 也不是一个好建议，因为数据本身是一颗 B+树，这导致了在插入记录的时候，为了维持B+树特性，而频繁的分裂调整变得低效，所以一般使用自增字段作为主键的

### 4.3 索引使用策略及优化 ###

MySQL 的优化主要分为结构优化和查询优化

下面主要讨论结构化优化

情况1：当 where 后面有多个查询字段时， MySQL 查询优化器会自动调整顺序来使用合适的索引，如果我们写的时候不一致，会发现最后的查询结果是一致的

情况2：最左前缀匹配，这个其实说到是我们进行查询的时候，查询SQL语句可能没有用到索引，比如在一张表建立联合索引，它可能只会匹配最左边的索引，如果没有对最左边进行匹配查询，可能无法使用到索引

情况3：对于范围列的查询想要用到索引，必须是最左前缀，另外范围后面的数据无法用到索引，同时索引最多用于一个范围列，如果查询中有多个范围列，则无法使用索引

情况4：对于查询条件中如果含有函数表达式，也无法对这列数据使用索引

> 注意：索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引  
> \-1 如果表记录比较少，不建议使用索引  
> \-2 索引的选择性比较低，比如只有0或1，男或女

如果使用 InnoDB 引擎，一般把与业务无关的自增字段作为主键

> 注意：很多网上博客说使用学号或者身份证这样的唯一字段作为主键，这其实是一种误导

之前说 InnoDB 采用聚集索引，数据记录本身被存于主索引的叶子节点上，这就要求同一个叶子节点内的各条数据记录按主键顺序存放，因此每当有一条新记录插入时，MySQL 会根据其主键将其插入到合适的节点位置，如果使用自增主键，每次插入数据，记录就会添加到当前索引节点后序位置，当一页写满开启新的一页，这样形成一个紧凑的索引结构，如果使用非自增主键比如学号，身份证，每次插入主键的值几乎都是随机值，每次新记录都要被插入到现有索引的某个中间位置，此时MySQL就不得不要移动数据了，甚至目标页面可能会被写回到磁盘里面，然后又需要再一次访问磁盘，明显带来了开销

**因此尽量在InnoDB上采用自增字段做主键**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20211214/5ec0e5e4423f4e2ba289b33cc53f35ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20211214/17771eab3d114cc98209bcbd27d71c2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20211214/84c45820b8674eacae354458442c9043.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20211214/6c0e956b2f13437aa2a66711d7f17b47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20211214/7d397f72f48740c19ed51a9ad09ce219.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20211214/272e30d923e14fec9422e11df6a17d44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20211214/2e00c3a26039437788e59fd036809251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20211214/e9554348c39b4168bef17331a1232ca8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20211214/9c349ef1202f4906bf9419167759d0c6.png