MySQL 索引 B树 B+树

柔光的暖阳◎ 2022-11-04 15:27 200阅读 0赞

# 索引 #

### 文章目录 ###

*  索引
 *   *  一、索引
     *   *  1. 基本介绍
         *  2. 使用索引的优势、劣势
         *  3. 索引类型
         *  4. B树结构
         *  5. B+树结构
         *  6. MySQL中的B+树
         *  7. 索引分类
         *  8. 索引语法
         *   *  (1) 创建索引
             *  (2) 查看索引
             *  (3) 删除索引
             *  (4) 修改索引
         *  9. 索引设计原则

## 一、索引 ##

### 1. 基本介绍 ###

*  索引（index）是帮助MySQL高效获取数据的数据结构（有序）
 *  在数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引
 *  索引示意图如下
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70][]
    
     *  一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）
     *  图1没有使用索引时，查找时会按顺序遍历表中的数据，速度较慢
     *  图2使用二叉排序树结构的索引，每个节点分别包含索引键值和一个指向对应数据物理地址的指针，这样就可以运用二叉查找快速获取到相应数据

### 2. 使用索引的优势、劣势 ###

*  使用索引的优势
    
     *  提高数据检索的效率
     *  通过索引列对数据进行排序，降低数据排序的成本
 *  使用索引的劣势
    
     *  索引也是一张表，该表中保存了主键与索引字段，并指向实体类的记录，所以索引列也是要占用空间的
     *  降低更新表的速度；当表进行了更新之后，MySQL还要调整因为更新所带来的键值变化后的索引信息

### 3. 索引类型 ###

**MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持**

<table> 
 <thead> 
  <tr> 
   <th>索引</th> 
   <th>InnoDB引擎</th> 
   <th>MyISAM引擎</th> 
   <th>Memory引擎</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>BTREE索引</td> 
   <td>支持</td> 
   <td>支持</td> 
   <td>支持</td> 
  </tr> 
  <tr> 
   <td>HASH 索引</td> 
   <td>不支持</td> 
   <td>不支持</td> 
   <td>支持</td> 
  </tr> 
  <tr> 
   <td>R-tree 索引</td> 
   <td>不支持</td> 
   <td>支持</td> 
   <td>不支持</td> 
  </tr> 
  <tr> 
   <td>Full-text</td> 
   <td>5.6版本之后支持</td> 
   <td>支持</td> 
   <td>不支持</td> 
  </tr> 
 </tbody> 
</table>

*  BTREE 索引 ： 最常见的索引类型，大部分存储引擎都支持 B 树索引
 *  我们平常所说的索引，如果没有特别指明，都是指B+树结构组织的索引

### 4. B树结构 ###

*  BTree又叫多路平衡搜索树，一颗m叉的BTree特性如下：
    
     *  树中每个节点最多包含m个孩子
     *  除根节点与叶子节点外，每个节点至少有 \[ceil(m/2)\] 个孩子；ceil表示向上取整，如5 / 2 向上取整结果为3
     *  若根节点不是叶子节点，则至少有两个孩子
     *  所有的叶子节点都在同一层
     *  每个非叶子节点由n个key与n+1个指针组成，n的取值范围是\[ceil(m/2)-1\] <= n <= m-1 
     *  一个指针指向一个子节点
 *  以5叉BTree为例，讲解B树添加节点的过程
    
     *  每个非叶子节点key的数量：公式推导\[ceil(m/2)-1\] <= n <= m-1 ，所以 2 <= n <=4
     *  当n>4时，中间节点分裂到父节点，两边节点分裂
        
         *  中间节点表示新节点插入后，奇数个数取中点，偶数个数中间两个任意取
         *  重复上面动作，直到所有节点符合B树的规则
         *  最坏的情况一直分裂到根节点，生成新的根节点，高度增加1
     *  插入 C N G A H E K Q M F W L T Z D P R X Y S 数据为例，演变过程如下：
        
         *  1.  插入前4个字母 C N G A ，第一层出现的四个节点均为key，由上述得知最多只能有4个
                
                ![2021030313031217.png][]
                
                 *  每两层表示一个节点，第一层表示key，第二层表示指针
                 *  由计算得知，每个节点的key最多4个
         *  1.  插入H，H应该插在G之后，n>4，中间元素G字母向上分裂到新的节点
                
                ![20210303130321732.png][]
                
                 *  第一个指针指向比G小的节点，第二个指针指向比G大的节点
         *  1.  插入E，K，Q，不需要分裂
                
                ![20210303130330471.png][]
         *  1.  插入M，中间元素M字母向上分裂到父节点G
                
                ![20210303130337487.png][]
                
                 *  第一个指针指向小于G的节点，第二个指针指向大于G小于M的节点，第三个指针指向大于M的节点
         *  1.  插入F，W，L，T，不需要分裂
                
                ![20210303130346427.png][]
         *  1.  插入Z，中间元素T向上分裂到父节点中
                
                ![20210303130352722.png][]
         *  1.  插入D，中间元素D向上分裂到父节点中。然后插入P，R，X，Y，不需要分裂
                
                ![20210303130358989.png][]
         *  1.  最后插入S，NPQR节点n>5，中间节点Q向上分裂，但分裂后父节点DGMT的n>5，中间节点M向上分裂
                
                ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 1][]
 *  BTree树 和 二叉树 相比， 查询数据的效率更高， 因为对于相同的数据量来说，BTREE的层级结构比二叉树小，因此搜索速度快

### 5. B+树结构 ###

*  B+Tree为BTree的变种，B+Tree与BTree的区别为：
    
     *  n叉B+Tree最多含有n个key，而BTree最多含有n-1个key
     *  B+Tree的叶子节点保存所有的key信息，依key大小顺序排列。B树每个节点存储自己的key
     *  所有的非叶子节点都可以看作是key的索引部
     *  由于B+Tree只有叶子节点保存key信息，查询任何key都要从root走到叶子。所以B+Tree的查询效率更加稳定
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 2][]

### 6. MySQL中的B+树 ###

MySql索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。

如下图的叶子节点中可以从9直接横向访问到99

MySQL中的 B+Tree 索引结构示意图:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 3][]

### 7. 索引分类 ###

*  单值索引 ：即一个索引只包含单个列，一个表可以有多个单列索引
 *  唯一索引 ：索引列的数据必须都是唯一的，但允许有空值
    
     *  唯一索引的好处：
        
         *  简化了MySQL对这个索引的管理工作，这个索引也因此而变得更有效率
         *  MySQL会在有新记录插入数据表时，自动检查新记录的这个字段的值是否已经在某个记录的这个字段里出现过了；如果是，MySQL将拒绝插入那条新记录。也就是说，唯一索引可以保证数据记录的唯一性
 *  复合索引 ：即一个索引包含多个列

### 8. 索引语法 ###

准备环境

create database demo_01 default charset=utf8mb4;
    
    use demo_01;
    
    CREATE TABLE `city` (
      `city_id` int (11) NOT NULL AUTO_INCREMENT,
      `city_name` varchar(50) NOT NULL,
      `country_id` int(11) NOT NULL,
      PRIMARY KEY (`city_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    
    CREATE TABLE `country` (
      `country_id` int(11) NOT NULL AUTO_INCREMENT,
      `country_name` varchar(100) NOT NULL,
      PRIMARY KEY (`country_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    
    
    insert into `city` (`city_id`, `city_name`, `country_id`) values(1,'西安',1);
    insert into `city` (`city_id`, `city_name`, `country_id`) values(2,'NewYork',2);
    insert into `city` (`city_id`, `city_name`, `country_id`) values(3,'北京',1);
    insert into `city` (`city_id`, `city_name`, `country_id`) values(4,'上海',1);
    
    insert into `country` (`country_id`, `country_name`) values(1,'China');
    insert into `country` (`country_id`, `country_name`) values(2,'America');
    insert into `country` (`country_id`, `country_name`) values(3,'Japan');
    insert into `country` (`country_id`, `country_name`) values(4,'UK');

![20210303130444234.png][]

#### (1) 创建索引 ####

*  语法
    
        CREATE 	[UNIQUE|FULLTEXT|SPATIAL]  INDEX index_name /*指定索引的类型(可选)及名称*/
        [USING  index_type] /*指定使用的索引的数据结构，不指定默认是B+树*/
        ON tbl_name(index_col_name,...) /*为哪张表的哪个字段创建索引*/
 *  示例
    
    为city表中的city\_name字段创建索引
    
    ![20210303130456530.png][]
 *  注意：主键字段默认有主键索引，无需额外创建索引

#### (2) 查看索引 ####

*  语法
    
        show index  from  table_name;
 *  示例
    
    查看city表中的索引信息 (指令后加\\G可以直观的展示索引)
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 4][]

#### (3) 删除索引 ####

*  语法
    
        DROP  INDEX  index_name  ON  tbl_name;
 *  示例
    
    删除city表上的索引 idx\_city\_name
    
    ![2021030313052762.png][]

#### (4) 修改索引 ####

*  column\_list表示字段列表，多个用逗号隔开
 *  语法
    
        alter  table  tb_name  add  primary  key(column_list); 
        
        /*该语句添加一个主键，这意味着索引值必须是唯一的，且不能为NULL*/
        	
        alter  table  tb_name  add  unique index_name(column_list);
        	
        /*这条语句创建唯一索引，索引的值必须是唯一的（除了NULL外，NULL可能会出现多次）*/
        	
        alter  table  tb_name  add  index index_name(column_list);
        
        /*添加普通索引， 索引值可以出现多次*/
        	
        alter  table  tb_name  add  fulltext  index_name(column_list);
        	
        /*该语句指定了索引为FULLTEXT， 用于全文索引*/

### 9. 索引设计原则 ###

索引的设计可以遵循一些已有的原则，创建索引的时候请尽量考虑符合这些原则，便于提升索引的使用效率，更高效的使用索引。

*  对查询频次较高，且数据量比较大的表建立索引。
 *  索引字段的选择，最佳候选列应当从where子句的条件中提取，如果where子句中的组合比较多，那么应当挑选最常用、过滤效果最好的列的组合。
 *  使用唯一索引，区分度越高，使用索引的效率越高。
 *  索引可以有效的提升查询数据的效率，但索引数量不是多多益善，索引越多，维护索引的代价自然也就水涨船高。对于插入、更新、删除等DML操作比较频繁的表来说，索引过多，会引入相当高的维护代价，降低DML操作的效率，增加相应操作的时间消耗。另外索引过多的话，MySQL也会犯选择困难病，虽然最终仍然会找到一个可用的索引，但无疑提高了选择的代价。
 *  使用短字段索引，索引创建之后也是使用硬盘来存储的，因此提升索引访问的I/O效率，也可以提升总体的访问效率。假如构成索引的字段总长度比较短，那么在给定大小的存储块内可以存储更多的索引值，相应的可以有效的提升MySQL访问索引的I/O效率。
 *  利用最左前缀，N个列组合而成的组合索引，那么相当于是创建了N个索引，如果查询时where子句中使用了组成该索引的前几个字段，那么这条查询SQL可以利用组合索引来提升查询效率。
    
    最左查询，只要查询时包含了索引的第一个字段NAME，查询就会走索引
    
        /* 创建复合索引: */
        
        	CREATE INDEX idx_name_email_status ON tb_seller(NAME,email,STATUS);
        
        /* 就相当于 对name 创建索引 ; 对name , email 创建了索引 ; 对name , email, status 创建了索引 ; */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70]: /images/20221023/eac6fd5889f5464ebd7445f987d637d7.png
[2021030313031217.png]: /images/20221023/bb023631af004a7c8e07e522e122d52f.png
[20210303130321732.png]: /images/20221023/c603565e024e4ba190b16f9675132255.png
[20210303130330471.png]: /images/20221023/b3211c32e07f4523b9ab95ecf9a9f2a4.png
[20210303130337487.png]: /images/20221023/1baacf6bb78b476cbe7e37a8c9c3bd1e.png
[20210303130346427.png]: /images/20221023/b7555ff33a8e4c9e9a036e80cd9d2188.png
[20210303130352722.png]: /images/20221023/c7dd2d2f53ec4ce8ab81c678691b7f7e.png
[20210303130358989.png]: /images/20221023/fadec2bc395e4b4b9b505485f10cee3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 1]: /images/20221023/2f12ab4155b14dd1b607a22475996d8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 2]: /images/20221023/fdc7515973194448a229a1bda9f1bd6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 3]: /images/20221023/2c9bea19e0154fc9b9d9360627a24a10.png
[20210303130444234.png]: /images/20221023/429d54eadec247bfaa2dd3e6a9d5d264.png
[20210303130456530.png]: /images/20221023/e936a098600143e0830d65379c050e44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 4]: /images/20221023/ee97e95f8db345ff8ec4f9a00d90d84a.png
[2021030313052762.png]: /images/20221023/7580e270ab794723987ce32339730d16.png