【MySQL高级篇笔记-索引的数据结构 (中) 】

本是古典何须时尚 2023-10-11 23:20 26阅读 0赞

此笔记为[尚硅谷][Link 1]MySQL高级篇部分内容

**目录**

一、索引及其优缺点

1、索引概述

2、优点

3、缺点

二、InnoDB中索引的推演

1、设计索引

1.一个简单的索引设计方案

2.InnoDB中的索引方案

2、常见索引概念

1. 聚簇索引

2. 二级索引（辅助索引、非聚簇索引）

3. 联合索引

3、InnoDB的B+树索引的注意事项

1. 根页面位置万年不动

2. 内节点中目录项记录的唯一性

3. 一个页面最少存储2条记录

三、MyISAM中的索引方案

MyISAM 与 InnoDB对比

小结

四、索引的代价

五、MySQL数据结构选择的合理性

全表遍历

Hash结构

二叉搜索树

AVL树

B-Tree

B+Tree

思考题

R树

小结

算法的时间复杂度

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

# 一、索引及其优缺点 #

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

## 1、索引概述 ##

> MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。  
> 索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。  
> 这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法

## 2、优点 ##

> （1）类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本 ，这也是创建索引最主要的原因。
> 
> （2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
> 
> （3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
> 
> （4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。

## 3、缺点 ##

> 增加索引也有许多不利的方面，主要表现在如下几个方面：
> 
> （1）创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。 （2）索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
> 
> （3）虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。因此，选择使用索引时，需要综合考虑索引的优点和缺点。

# 二、InnoDB中索引的推演 #

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

> 在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能 从第一个页 沿着 双向链表 一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是 超级耗时 的。如果一个表有一亿条记录呢？此时 索引 应运而生。

## 1、设计索引 ##

![62a01c6138734da7be5e572756981c0f.png][]

![be52d58b02f344588be62c88fcdf25e1.png][]

![760349d236ea4868b1d3feb987c05f61.png][]

![f2cc13168f4040bea0081aa7175eff49.png][]

### 1.一个简单的索引设计方案 ###

![5354d9960ec445b2a010e8c59e7c06c7.png][]

### 2.InnoDB中的索引方案 ###

**① 迭代1次：目录项纪录的页**

![fb3b1c0fac1a4cf3bb37ef9e9b90c210.png][]

> 从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调 目录项记录和普通的 用户记录 的不同点：
> 
> ![d7cc39f70b49421c97e6bda079ec64cc.png][]
> 
> 相同点： 
> 
> ![38762973a47049b1b0a7d8f0db04ccb7.png][]

**② 迭代2次：多个目录项纪录的页**

![bdd5847103f542ee813a21dc0fdbcb90.png][]

![2762e92ecb674008b0f77a5f18f53523.png][]

**③ 迭代3次：目录项记录页的目录页**

![77adb1654f4e426f8ff9523a3f1f4830.png][]

![70d82f15330c4028a4c624df8d8da85c.png][]

**④ B+Tree**

![a164399f5bf945e8bbd2dd34570aef8a.png][]

## 2、常见索引概念 ##

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

### 1. 聚簇索引 ###

![b05c436106454dd2b6ad1568fda50947.png][]

### 2. 二级索引（辅助索引、非聚簇索引） ###

![96426a903c1e4356862057513f3e6180.png][]

![170806490acc403295af3713d7283309.png][]

###  ###

### 3. 联合索引 ###

![d25bd280dae54685b273a1458e662d94.png][]

##  ##

## 3、InnoDB的B+树索引的注意事项 ##

### 1. 根页面位置万年不动 ###

理解形成过程

![52b031ac826b403ca36c07279c2befb0.png][]

### 2. 内节点中目录项记录的唯一性 ###

### ![1e9f72b94d3c4d59b848e8760c1757c9.png][] ###

### ![8eb1b2374dfd4fc5b56a639717e6f789.png][] ###

### ![9d263e35851c4855857f3f8e12c47d25.png][]   3. 一个页面最少存储2条记录 ###

![7dda90625a95429e8efc610e459bdfb0.png][]

# 三、MyISAM中的索引方案 #

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

![4ea560cb54ee4304804267c9f5120654.png][]

MyISAM索引的原理图

![18b692d98de340d5b8125273191ea215.png][]

![1e70edeac6af4c8092ff929b996c64e5.png][]

## MyISAM 与 InnoDB对比 ##

![d03d38bbd9b942a8a520aaa80ee11265.png][]

![0eea0801e2d34a06bc94c262793e1896.png][]

### **小结** ###

![bd590ea30a51420baf78b9a88cfbb03e.png][]

# 四、索引的代价 #

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

> 索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：
> 
>  *  空间上的代价 ![88b9de7a0f214ea3b23661ef65f8b15a.png][]
> 
>  *  时间上的代价![1bf53d4c4dd64214a9b7b334e404c229.png][]

# 五、MySQL数据结构选择的合理性 #

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

### 全表遍历 ###

### Hash结构 ###

![0a0f8ff5e1b04f7aa6579657ae07d978.png][] ![89f29a603892412c9945b278a4c2c852.png][]

**Hash索引适用存储引擎如表所示：**

![33a128ffa21e43c786ea6f2d628c9748.png][]![b048e063649c4eb189aeac3e913bcaeb.png][]

![5b9b2526f6ef4da79491b868e14859c1.png][]

### 二叉搜索树 ###

如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。

![b733639ab9994938af07315cd36efde2.png][]

![0d13629cb30c4fc0b7a97e95b22f0e25.png][]

### AVL树 ###

![21c39c6106654fe8b775a03b124e9a49.png][]

### B-Tree ###

![5accc3e7e25443739eb3b0f8976eeaac.png][]

![93e8c6801ba14685b34d4f51a5a15823.png][]

![d9f0e3b1b24c48f69580249eb1d25f1b.png][]

### B+Tree ###

![2a315341a8f44718b88c7079d516f96e.png][]

> **B+ 树和 B 树的差异：**
> 
> 1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
> 
> 2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。  
> 3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非叶子节点既保存索引，也保存数据记录 。  
> 4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

![fc61e6b2c01647a180cd0bb46ed9a4ce.png][]

### 思考题 ###

**思考题：为了减少IO，索引树会一次性加载吗？**

![5d86d475562c4e35bee5c2c6c0c2ebea.png][]  
**思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO**

![18a921636c0d47ebabaf05dff507d2d7.png][]  
**思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？**

![f737f2bbcad44808981a109625547b24.png][]  
**思考题：Hash 索引与 B+ 树索引的区别**

![120bdb2178ae47a3bb1632c81312e944.png][]

![a689186df8c64798b60f5011334b690e.png][]  
**思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？**

![1235b2191fcb4986bb6ee75e4ca75e55.png][]

### R树 ###

![c50443c672674c16a2e07de303695ae3.png][]

### 小结 ###

![15145d4161e54be6acaf7d8d5531d5a9.png][]

# 算法的时间复杂度 #

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

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

![1fffb991ad404343963fb0b501243fc5.png][]

高级篇笔记PDF自取

链接：[https://pan.baidu.com/s/1pVqrTwIZFoED77i-EFmw6g?pwd=3333 ][https_pan.baidu.com_s_1pVqrTwIZFoED77i-EFmw6g_pwd_3333]  
提取码：3333

[Link 1]: https://so.csdn.net/so/search?q=%E5%B0%9A%E7%A1%85%E8%B0%B7&spm=1001.2101.3001.7020
[62a01c6138734da7be5e572756981c0f.png]: https://img-blog.csdnimg.cn/62a01c6138734da7be5e572756981c0f.png
[be52d58b02f344588be62c88fcdf25e1.png]: https://img-blog.csdnimg.cn/be52d58b02f344588be62c88fcdf25e1.png
[760349d236ea4868b1d3feb987c05f61.png]: https://img-blog.csdnimg.cn/760349d236ea4868b1d3feb987c05f61.png
[f2cc13168f4040bea0081aa7175eff49.png]: https://img-blog.csdnimg.cn/f2cc13168f4040bea0081aa7175eff49.png
[5354d9960ec445b2a010e8c59e7c06c7.png]: https://img-blog.csdnimg.cn/5354d9960ec445b2a010e8c59e7c06c7.png
[fb3b1c0fac1a4cf3bb37ef9e9b90c210.png]: https://img-blog.csdnimg.cn/fb3b1c0fac1a4cf3bb37ef9e9b90c210.png
[d7cc39f70b49421c97e6bda079ec64cc.png]: https://img-blog.csdnimg.cn/d7cc39f70b49421c97e6bda079ec64cc.png
[38762973a47049b1b0a7d8f0db04ccb7.png]: https://img-blog.csdnimg.cn/38762973a47049b1b0a7d8f0db04ccb7.png
[bdd5847103f542ee813a21dc0fdbcb90.png]: https://img-blog.csdnimg.cn/bdd5847103f542ee813a21dc0fdbcb90.png
[2762e92ecb674008b0f77a5f18f53523.png]: https://img-blog.csdnimg.cn/2762e92ecb674008b0f77a5f18f53523.png
[77adb1654f4e426f8ff9523a3f1f4830.png]: https://img-blog.csdnimg.cn/77adb1654f4e426f8ff9523a3f1f4830.png
[70d82f15330c4028a4c624df8d8da85c.png]: https://img-blog.csdnimg.cn/70d82f15330c4028a4c624df8d8da85c.png
[a164399f5bf945e8bbd2dd34570aef8a.png]: https://img-blog.csdnimg.cn/a164399f5bf945e8bbd2dd34570aef8a.png
[b05c436106454dd2b6ad1568fda50947.png]: https://img-blog.csdnimg.cn/b05c436106454dd2b6ad1568fda50947.png
[96426a903c1e4356862057513f3e6180.png]: https://img-blog.csdnimg.cn/96426a903c1e4356862057513f3e6180.png
[170806490acc403295af3713d7283309.png]: https://img-blog.csdnimg.cn/170806490acc403295af3713d7283309.png
[d25bd280dae54685b273a1458e662d94.png]: https://img-blog.csdnimg.cn/d25bd280dae54685b273a1458e662d94.png
[52b031ac826b403ca36c07279c2befb0.png]: https://img-blog.csdnimg.cn/52b031ac826b403ca36c07279c2befb0.png
[1e9f72b94d3c4d59b848e8760c1757c9.png]: https://img-blog.csdnimg.cn/1e9f72b94d3c4d59b848e8760c1757c9.png
[8eb1b2374dfd4fc5b56a639717e6f789.png]: https://img-blog.csdnimg.cn/8eb1b2374dfd4fc5b56a639717e6f789.png
[9d263e35851c4855857f3f8e12c47d25.png]: https://img-blog.csdnimg.cn/9d263e35851c4855857f3f8e12c47d25.png
[7dda90625a95429e8efc610e459bdfb0.png]: https://img-blog.csdnimg.cn/7dda90625a95429e8efc610e459bdfb0.png
[4ea560cb54ee4304804267c9f5120654.png]: https://img-blog.csdnimg.cn/4ea560cb54ee4304804267c9f5120654.png
[18b692d98de340d5b8125273191ea215.png]: https://img-blog.csdnimg.cn/18b692d98de340d5b8125273191ea215.png
[1e70edeac6af4c8092ff929b996c64e5.png]: https://img-blog.csdnimg.cn/1e70edeac6af4c8092ff929b996c64e5.png
[d03d38bbd9b942a8a520aaa80ee11265.png]: https://img-blog.csdnimg.cn/d03d38bbd9b942a8a520aaa80ee11265.png
[0eea0801e2d34a06bc94c262793e1896.png]: https://img-blog.csdnimg.cn/0eea0801e2d34a06bc94c262793e1896.png
[bd590ea30a51420baf78b9a88cfbb03e.png]: https://img-blog.csdnimg.cn/bd590ea30a51420baf78b9a88cfbb03e.png
[88b9de7a0f214ea3b23661ef65f8b15a.png]: https://img-blog.csdnimg.cn/88b9de7a0f214ea3b23661ef65f8b15a.png
[1bf53d4c4dd64214a9b7b334e404c229.png]: https://img-blog.csdnimg.cn/1bf53d4c4dd64214a9b7b334e404c229.png
[0a0f8ff5e1b04f7aa6579657ae07d978.png]: https://img-blog.csdnimg.cn/0a0f8ff5e1b04f7aa6579657ae07d978.png
[89f29a603892412c9945b278a4c2c852.png]: https://img-blog.csdnimg.cn/89f29a603892412c9945b278a4c2c852.png
[33a128ffa21e43c786ea6f2d628c9748.png]: https://img-blog.csdnimg.cn/33a128ffa21e43c786ea6f2d628c9748.png
[b048e063649c4eb189aeac3e913bcaeb.png]: https://img-blog.csdnimg.cn/b048e063649c4eb189aeac3e913bcaeb.png
[5b9b2526f6ef4da79491b868e14859c1.png]: https://img-blog.csdnimg.cn/5b9b2526f6ef4da79491b868e14859c1.png
[b733639ab9994938af07315cd36efde2.png]: https://img-blog.csdnimg.cn/b733639ab9994938af07315cd36efde2.png
[0d13629cb30c4fc0b7a97e95b22f0e25.png]: https://img-blog.csdnimg.cn/0d13629cb30c4fc0b7a97e95b22f0e25.png
[21c39c6106654fe8b775a03b124e9a49.png]: https://img-blog.csdnimg.cn/21c39c6106654fe8b775a03b124e9a49.png
[5accc3e7e25443739eb3b0f8976eeaac.png]: https://img-blog.csdnimg.cn/5accc3e7e25443739eb3b0f8976eeaac.png
[93e8c6801ba14685b34d4f51a5a15823.png]: https://img-blog.csdnimg.cn/93e8c6801ba14685b34d4f51a5a15823.png
[d9f0e3b1b24c48f69580249eb1d25f1b.png]: https://img-blog.csdnimg.cn/d9f0e3b1b24c48f69580249eb1d25f1b.png
[2a315341a8f44718b88c7079d516f96e.png]: https://img-blog.csdnimg.cn/2a315341a8f44718b88c7079d516f96e.png
[fc61e6b2c01647a180cd0bb46ed9a4ce.png]: https://img-blog.csdnimg.cn/fc61e6b2c01647a180cd0bb46ed9a4ce.png
[5d86d475562c4e35bee5c2c6c0c2ebea.png]: https://img-blog.csdnimg.cn/5d86d475562c4e35bee5c2c6c0c2ebea.png
[18a921636c0d47ebabaf05dff507d2d7.png]: https://img-blog.csdnimg.cn/18a921636c0d47ebabaf05dff507d2d7.png
[f737f2bbcad44808981a109625547b24.png]: https://img-blog.csdnimg.cn/f737f2bbcad44808981a109625547b24.png
[120bdb2178ae47a3bb1632c81312e944.png]: https://img-blog.csdnimg.cn/120bdb2178ae47a3bb1632c81312e944.png
[a689186df8c64798b60f5011334b690e.png]: https://img-blog.csdnimg.cn/a689186df8c64798b60f5011334b690e.png
[1235b2191fcb4986bb6ee75e4ca75e55.png]: https://img-blog.csdnimg.cn/1235b2191fcb4986bb6ee75e4ca75e55.png
[c50443c672674c16a2e07de303695ae3.png]: https://img-blog.csdnimg.cn/c50443c672674c16a2e07de303695ae3.png
[15145d4161e54be6acaf7d8d5531d5a9.png]: https://img-blog.csdnimg.cn/15145d4161e54be6acaf7d8d5531d5a9.png
[1fffb991ad404343963fb0b501243fc5.png]: https://img-blog.csdnimg.cn/1fffb991ad404343963fb0b501243fc5.png
[https_pan.baidu.com_s_1pVqrTwIZFoED77i-EFmw6g_pwd_3333]: https://pan.baidu.com/s/1pVqrTwIZFoED77i-EFmw6g?pwd=3333%C2%A0