SQL索引概念（详解B+树）

我就是我 2022-11-17 13:50 202阅读 0赞

### Sql索引（index） ###

*   *  定义
     *  分类
     *   *  复合索引特性
         *   *  复合索引最左特性（原则）
             *  原理
     *  索引及其扫描类型
     *  索引的优缺点
     *  扩展：索引工作原理
     *   *  BTree+索引
         *  怎么判断是否创建索引？
         *  为什么Mysql用B+树做索引而不用B-树或红黑树
         *   *  B树相对于红黑树的区别：
     *  为什么索引快？

## 定义 ##

索引是一种排好序的快速查找的数据结构，它帮助数据库高效的进行数据的检索。在数据之外，数据库系统还维护着满足特定查找算法的数据结构（额外的存储空间），这些数据结构以某种方式指向数据，这样就可以在这些数据结构上实现高效的查找算法。这种数据结构就叫做索引。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzYwMTM1OQ_size_16_color_FFFFFF_t_70]

一般来说索引本身也很大，不可能全部存储在内存中，因此往往以索引文件的形式存放在磁盘中。目前大多数索引都采用BTree树方式构建。

## 分类 ##

*  单值索引：一个索引只包括一个列，一个表可以有多个列
 *  唯一索引：索引列的值必须唯一，但允许有空值
 *  复合索引（联合索引）：一个索引同时包括多列

### 复合索引特性 ###

#### 复合索引最左特性（原则） ####

在Mysql建立复合索引时有最左前缀的原则。当建立一个复合索引(col1,col2,col3)时，实际上建立了三个索引，即(col1)、(col1,col2)、(col1,col2,col3)。

#### 原理 ####

复合索引的结构是B+树，比如(name,age,sex)的时候，b+树是按照从左到右的顺序来建立搜索树的，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex。当age或者sex字段缺失时，b+树就不知道第一步该查哪个节点，所以只能把名字name的数据都找到，即索引的最左匹配特性。

## 索引及其扫描类型 ##

**`type：`**

*  ALL 全表扫描，没有优化，最慢的方式
 *  index 索引全扫描
 *  range 索引范围扫描，常用语<，<=，>=，between等操作
 *  ref 使用非唯一索引扫描或唯一索引前缀扫描，返回单条记录，常出现在关联查询中
 *  eq\_ref 类似ref，区别在于使用的是唯一索引，使用主键的关联查询
 *  const 当查询是对主键或者唯一键进行精确查询，系统会把匹配行中的其他列作为常数处理
 *  null MySQL不访问任何表或索引，直接返回结果
 *  System 表只有一条记录(实际中基本不存在这个情况)

> **性能排行：**  
> System > const > eq\_ref > ref > range > index > ALL

**`possible_keys：`**

*  显示可能应用在这张表中的索引

**`key：`**

*  真正使用的索引方式

## 索引的优缺点 ##

**优点:**

*  索引是数据库优化
 *  表的主键会默认自动创建索引
 *  大量降低数据库的IO磁盘读写成本，极大提高了检索速度
 *  索引事先对数据进行了排序，降低查询是数据排序的成本，降低CPU的消耗

**缺点:**

*  索引本身也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也要占用空间
 *  索引表中的内容，在业务表中都有，数据是重复的，空间是“浪费的”
 *  虽然索引大大提高了查询的速度，但反向影响了增、删、改操作的效率。如表中数据变化之后，会造成索引内容不正确，需要更新索引表信息，如果数据量非常巨大，重新创建索引的时间就大大增加
 *  随着业务的不断变化，之前建立的索引可能不能满足查询需求，需要消耗我们的时间去更新索引

## 扩展：索引工作原理 ##

### BTree+索引 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzYwMTM1OQ_size_16_color_FFFFFF_t_70 1]

*  浅蓝色: 磁盘块
 *  深蓝色: 数据项
 *  黄色: 数据的指针

真实的数据仅在叶子节点中: 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90,99  
查找过程: 假如要找29

*  从树根开始，即先把磁盘块1中内容读到内存中，发生一次IO
 *  确定29在(17,35)之间，锁定磁盘块1中的P2指针
 *  根据P2指针，找到磁盘块3，读取到内存中，发生二次IO
 *  29在(26,30)之间，锁定磁盘块3的P2指针
 *  通过磁盘3的P2指针，将磁盘块8的内容读取到内存中，发生第三次IO
 *  最终找到数据29，查询结束，总共发生三次IO

### 怎么判断是否创建索引？ ###

**创建索引：**

*  主键约束默认建立唯一索引
 *  频繁出现在where查询条件的字段
 *  多表查询中与其它表进行on关联的字段，外键关系
 *  单列索引/复合索引的选择? 高并发下倾向于创建复合索引
 *  查询中经常用来排序的字段
 *  查询中经常用来统计或者分组字段

**不创建索引：**

*  频繁更新的字段: 每次更新都会影响索引树
 *  where条件查询中用不到的字段
 *  表记录太少
 *  经常增删改的表: 更新了表，索引也得更新才行
 *  注意: 如果一张表中重复的记录非常多，为它建立索引就没有太大意义

### 为什么Mysql用B+树做索引而不用B-树或红黑树 ###

*  B+树只有叶节点存放数据，其余节点用来索引
 *  B-树是每个索引节点都会有Data域

从Mysql（InnoDB）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。

那么Mysql如何衡量查询效率呢？磁盘IO次数。B-树/B+树的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。

另一个优点是：B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

#### B树相对于红黑树的区别： ####

平衡二叉树AVL 和红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候，**红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况**。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根**据磁盘查找存取的次数往往由树的高度所决定**，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

同时，数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

## 为什么索引快？ ##

*  排序
 *  树形结构，类似二分查找

3层的BTree可以表示上百万的数据，如果上百万条数据，查找只需要三次IO，性能提高将是巨大的，如果没有索引每次查找都要发生一次IO，那么总共就需要百万次的IO,显然成本是非常高的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzYwMTM1OQ_size_16_color_FFFFFF_t_70]: /images/20221022/710d59128eca43aca423389adb25fdd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzYwMTM1OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/26f88d5fe73c4d669e8a7727084647db.png