MySQL B+ 树索引原理全解

╰+哭是因爲堅強的太久メ 2023-10-18 23:41 81阅读 0赞

#### 文章目录 ####

*  1. 数据库索引
 *  2. 数据库索引的原理
 *   *   *  2.1 局部性原理与磁盘预读
         *  2.2 索引的数据结构
         *   *   *  2.2.1 m 阶 B-Tree: m 为一个节点最大子节点个数
                 *  2.2.2 B+ Tree
         *  2.3 MySQL 数据库中B+Tree 索引的应用
         *   *   *  2.3.1 MyIsAM 引擎
                 *  2.3.2 InnoDB 引擎
 *  3. 索引的使用策略与优化
 *   *   *  3.1 索引覆盖
         *  3.2 联合索引(复合索引)
         *  3.3 最左前缀原理
         *  3.4 索引优化建议
         *   *   *  3.4.1 查询优化
                 *  3.4.2 索引结构优化

## 1. 数据库索引 ##

MySQL数据库支持多种索引类型，如B+树索引，哈希索引，全文索引等等.本文只关注B+树索引，因为这是平常使用 MySQL 时接触最多的索引.全面彻底地了解索引是个很长期且艰难的工作,但我们可以从以下几个方面对数据库索引有个基本的认识.

*  `索引的目的`  
    索引就像一本字典的目录, 如果没有目录, 我们要查找某个字就需要把整本字典都翻一遍逐个字进行对比, 这无疑是非常低效的. 索引可以帮助我们快速定位到想要查找的内容的位置, 提高查询效率就是索引的目的.
 *  `索引的本质`  
    高效的查找算法往往需要特定的数据结构支持, 在数据之外,数据库系统就维护着满足特定查找算法的数据结构.这些数据结构以某种方式指向数据，这样就可以在这些数据结构上实现高级查找算法. 这种数据结构, 就是索引.
 *  `索引存放的位置`  
    索引作为一种数据结构,一般来说本身也很大,不可能全部存储在内存中, 因此索引往往以索引文件的形式存储在磁盘上.

--------------------

## 2. 数据库索引的原理 ##

#### 2.1 局部性原理与磁盘预读 ####

1.  由于存储介质的特性，磁盘本身存取比主存慢很多，再加上磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的. 为了提高磁盘与主存的交互效率, 首要的手段就是减少磁盘 I/O 次数. 为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存. 这样做的理论依据是局部性原理：当一个数据被用到时，其附近的数据通常也会马上被使用.
2.  预读的长度一般为页(page)的整倍数. 页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块, 每个存储块称为一页(页大小通常为4k)，主存和磁盘以页为单位交换数据. 当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序拿到数据继续运行.

--------------------

#### 2.2 索引的数据结构 ####

索引一般以文件形式存储在磁盘上, 为了提高性能, 每次又要把部分数据读入内存来处理,这就意味着索引检索需要磁盘I/O操作, 而我们又一般以使用磁盘I/O次数来评价索引结构的优劣. 这样, B+ 树就理所当然地被选做理想的索引数据结构了. B+ 树是 B 树的变种, 要了解B+ 树的性质还是要建立在B 树的基础之上.

--------------------

###### 2.2.1 m 阶 B-Tree: m 为一个节点最大子节点个数 ######

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

**B 树的性质:**

*  一个节点最多有m个分支
 *  一个节点有n个关键字,则有n+1个分支
 *  根节点最少有两个分支,非根非叶节点至少有ceil \[m/2\] 个分支
 *  节点的关键字递增排序
 *  节点中的关键字都大于其左边分支上的关键字,小于其右边分支上的关键字
 *  所有叶节点属于同一层,也就是具有同样的深度 h

由于B-Tree的特性, 在B-Tree中按key检索数据的算法很直观：首先从根节点进行二分查找，如果找到则返回对应key的data，找不到则对相应区间的指针指向的节点向下递归进行查找, 直到找到key成功返回数据或找到null指针失败. 以上图举例来说, 要检索 key=9 的数据, 则需要经过以下遍历过程,**可知要访问的磁盘块数量和树高直接相关,也就是I/O次数取决于树的高度h**.

磁盘块1--> 磁盘块2-->磁盘块6

数据库系统的设计者利用磁盘预读原理,将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入.为了达到这个目的，在实际实现B-Tree时有如下技巧：

1.  每次新建节点时直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加上计算机存储分配都是按页对齐的，这就实现了一个节点只需一次I/O.
2.  B-Tree中一次检索最多需要h-1次 I/O(根节点常驻内存)，渐进复杂度为O(h)=O(logd N).一般实际应用中出度d是非常大的数字，通常超过100，因此h非常小(通常不超过3).

综上所述，如果采用B-Tree存储结构，搜索时I/O次数一般不会超过3次,所以用B-Tree作为索引结构效率是非常高的.

--------------------

###### 2.2.2 B+ Tree ######

我们已经知道外存储器的信息读取最大的时间消耗在于磁盘I/O, 那么一个基本的思路就是在一个磁盘页上多存储一些索引信息, 以进一步减少I/O次数, 换句话说就是在B-tree 的基础上实现同样多的数据以更小的树高存储. 这样 B 树的变种 B+ 树就产生了.

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

**B+ 树与 B 树的差异:**

*  一个节点有n个关键字,则有n个分支
 *  B+ 树只有叶节点会存储 data, 内节点只有关键字key, 而B树任意节点中 key-data 都是成对出现
 *  所有叶节点保存了所有父节点关键字记录的指针,所有数据地址都必须到叶节点才能获取,故每次查询数据I/O次数相同(因为都需要到叶节点,而叶节点都在同一层),查询效率稳定
 *  B+ 树所有叶节点通过指针连接到一起, 范围查询效率更高
 *  B+ 树内节点不存储 data, 则同一个页的空间可以容纳更多的关键字(这就是索引字段要尽量小的目的), 一次性读入内存可供检索的关键字也更多. 这样在数据量足够大的情况下, B+ 树拥有比 B 树更小的树高,也就可以减少 I/O 次数,提高性能.

--------------------

#### 2.3 MySQL 数据库中B+Tree 索引的应用 ####

###### 2.3.1 MyIsAM 引擎 ######

MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址, 类似于使用偏旁部首查字典.使用索引搜索时, 如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录. 这种索引方式也叫 **非聚集索引**:

*  数据在索引结构中逻辑上连续，但是实际存储的物理位置并不连续.

###### 2.3.2 InnoDB 引擎 ######

InnoDB 数据文件本身就是索引文件, 类似于使用拼音查字典,正文内容本就是按照一定规则排列的目录. 在 InnoDB 索引中 B+Tree的叶节点 key 为数据表主键, data域保存完整的数据记录, 这种索引方式也可以叫 **聚集索引**:

*  数据记录存储在物理上连续的位置

--------------------

## 3. 索引的使用策略与优化 ##

#### 3.1 索引覆盖 ####

查询的数据列只从索引中就能取得，不用去读取表数据(回表)，除了表上只有一个的聚集索引外，其他索引在查询整行数据的时候必然会回表

*  可使用 `explain` 分析

#### 3.2 联合索引(复合索引) ####

一般索引只有一个字段，而联合索引即为多个字段创建一个索引.它的原理很简单，比如我们在（A,B,C）字段上创建一个联合索引，则索引记录会首先按照A字段排序，然后再按照B字段排序然后再是C字段，因此联合索引的特点就是：

*  第一个字段一定是有序的
 *  当第一个字段值相等时, 第二个字段又是有序的, 依次类推

#### 3.3 最左前缀原理 ####

在（a,b,c）字段上建立联合索引, 真正查询时是否会用到索引其实和查询语句也有关系, mysql会一直从左向右匹配直到遇到范围查询(>、<、between、like)就停止匹配.

以下的查询方式都可以用到索引

select * from table where a=1；
    select * from table where a=1 and b=2；
    select * from table where a=1 and b=2 and c=3；
    三个查询按照 （a ）, （a，b ）,（a，b，c ）顺序都可以利用到索引，这就是最左前缀匹配.

如果查询语句是：

select * from table where a=1 and c=3； 
    只会用到索引a.

如果查询语句是：

select * from table where b=2 and c=3；
     因为没有用到最左前缀a，所以这个查询用不到索引

用到了最左前缀但是顺序颠倒,比如：

select * from table where b=2 and a=1；
    select * from table where b=2 and a=1 and c=3；
    如果用到了最左前缀而只是颠倒了顺序,也可以用到索引

#### 3.4 索引优化建议 ####

###### 3.4.1 查询优化 ######

1.  最左前缀匹配原则
2.  对 where,on,group by,order by 中出现的列使用索引
3.  对于like查询，”%”不要放在前面  
    SELECT \* FROM COOK WHERE name LIKE ‘后盾%’ – 走索引  
    SELECT \* FROM COOK WHERE name LIKE ‘%后盾%’ – 不走索引
4.  查询where条件数据类型不匹配无法使用索引
5.  字符串与数字比较不使用索引
6.  正则表达式不使用索引

###### 3.4.2 索引结构优化 ######

1.  主键外键一定要建索引
2.  尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(\*)，表示字段不重复的比例. 比例越大我们扫描的记录数越少,唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0.
3.  对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键
4.  为较长的字符串使用前缀索引
5.  尽量扩展索引,不要新建索引.
6.  不要过多创建索引. 建立索引是为了提高查询效率，但建立的索引过多，会影响插入、删除数据的速度，因为我们修改表数据之后，索引也需要进行调整重建

参考文章：  
https://www.cnblogs.com/hzy1991/p/8567334.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20190921122921260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20190921122447196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center