Mysql数据库索引数据结构学习篇

傷城~ 2023-02-26 12:30 76阅读 0赞

文章部分摘于[https://www.cnblogs.com/yufeng218/p/12465694.html][https_www.cnblogs.com_yufeng218_p_12465694.html]

**1、先了解一下mysql数据库**：

[MySQL][]是一种[开放源代码][Link 1]的关系型[数据库管理][Link 2]系统（RDBMS），使用最常用的数据库管理语言--[结构化查询语言][Link 3]（SQL）进行数据库管理。MySQL是开放源代码的。MySQL因为其速度、可靠性和适应性而备受关注。大多数人都认为在不需要[事务][Link 4]化处理的情况下，MySQL是管理内容最好的选择。

**  [MySQL][]结构图**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70][]  
  
**2、影响数据库性能的因素：**

1.服务器硬件  
 2.服务系统  
 3.数据库存储引擎的选择(重点)  
 4.数据库参数配置  
 5.数据库表结构设计和sql语句(重点)

**3、索引：**

索引是帮助[MySQL][]高效获取数据的排好序的数据结构。

**索引的数据结构：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 1][]

有一张表，表名为 t ，表中有7条数据；使用 **select \* from t where t.clo2 = 89** 进行查询

![format_png][]

**如果没有创建索引**

若表中没有创建索引，则会全表扫描，一条一条的遍历查询，需要遍历 6 次，查询一行数据至少和磁盘做一次I/O操作（I/O是很耗性能的），至少要做 6 次 I/O 操作；

**大家可以在这个网站上学习各种数据结构：[https://www.cs.usfca.edu/~galles/visualization/BST.html][https_www.cs.usfca.edu_galles_visualization_BST.html]**

**如果创建了索引，索引的底层是二叉树，这样查询 4 次就找到数据了**  
**二叉树特点：**左边的子元素小于父元素，右边的子元素大于父元素。每个结点最多有两颗子树，结点的度最大为2，也就是只有两个分叉的树。度的意思是当前结点有几个分叉就是几度。左子树和右子树是有顺序的，次序不能颠倒。即使某结点只有一个子树，也要区分左右子树。

![format_png 1][]

**有大小顺序的二叉树就变成了单项链表的数据结构。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 2][]

**如果创建了索引，索引的底层是红黑****树，这样查询 2 次就找到数据了**  
**红黑树特点：**是一种自**[平衡二叉查找树][Link 5]**，每个节点是黑色，或者是红色。根节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的。**当数据越大树的高度越大，查询越慢 ，高度不可控（数据多io重、性能差****）。**

**当单边的节点大于3时候，就会自动调整，这样可以解决二叉树的弊端。**

![format_png 2][]

**如果创建了索引，索引的底层是B-Tree，这样查询 2 次就找到数据了  
B-Tree特点：**叶节点据有相同的深度，叶节点的指针为空，所有的索引元素不能重复，节点中的数据索引从左到右递增排序。

若 Max. Degree = 4，则如下图所示：

![format_png 3][]

当然 B-Tree 也是有弊端的；以下是 B-Tree 的存储，数字为key，data为对应的数据；

**若一个节点我们申请的空间为16KB，若data中的数据过大，则一个节点能放的数据量越小，这样就会造成树的高度比较大了（比红黑树高度小点）；空白大小为6个字节  存放的是下一个节点内存中的地址。**

![20200715210312678.png][]  
  
**如果创建了索引，索引的底层是B+Tree，这样查询 2 次就找到数据了**

**B+Tree特点**：非叶子节点不存储data，只存储索引（冗余），可以放更多索引；叶子节点包含所有索引字段，即所有的data元素存储在叶子节点上；叶子节点使用指针连接，提高区间访问的性能；树节点从左到右依次递增，叶子节点从左到右依次递增，双向指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 3][]

**B+Tree 查询某一数据具体过程：**

以上图中查找 **49** 的数据：

1.先将根节点的数据(15, 56, 77) 做一次磁盘 I/O 操作取出加载到内存中，然后再在内存中做比对，找到对应的指针，查找到其对应的节点；

2. 将指针指向节点的数据(15, 20, 49) 做一次磁盘 I/O 操作取出加载到内存中，然后再在内存中做比对，找到对应的指针，接着去叶子节点获取数据；

**B+Tree 相对于 B-Tree的优化点**：

**优化点1：** B-Tree的所有节点都存储了 data 元素， B+Tree的非叶子节点不存储 data元素，则 B+Tree 的一个非叶子节点可以存储更多的索引；

**优化点2：** B+Tree在叶子节点之间增加了指针连接；对 select \* from t where col2 > 20 的范围查找有很好的支持；MySQL 对 B+Tree 做了优化，叶子节点使用的是双向指针；

**MySQL页默认能够存储多少数据：**

<1> 查看MySQL文件页大小（一个节点的大小）：

SHOW GLOBAL STATUS like 'Innodb_page_size'；

<2> MySQL页文件默认为16KB，树的高度为3，能够存储多少数据？

我们先看非叶子节点，假设主键ID为 bigint 类型，那么长度为8B，指针大小在Innodb源码中6B，一共14B，那么一页（即一个节点）可以存储  16KB/14B=1170 个索引元素和 1170个指针；根节点有1170个索引和1170个指针，树高度为2的节点就有1170个，那么叶子节点的数量为 1170x1170；每个叶子节点可以存储16KB，若每条数据比较大为1KB，那么每个叶子节点可以存储16条数据；那么，高度为3的 B+Tree 的叶子节点可以存储的数据量为 1170x1170x16=2000W；

**如果创建了索引，索引的底层是Hash表**

**先介绍一下Hash算法**

Hash本身是一种函数，又被称为散列函数。将key放在数组里，用一个hash算法把不同的key转换成一个确定的value，然后放在这个数组的指定位置，相同的输入永远可以得到相同的输出。具体的算法有MD5、SHA1、SHA2、SHA3。

**Hash冲突：不同的key得到了相同的value，当出现Hash冲突，可以在冲突发生的位置跟一个链表。**

若索引使用的** Hash** 存储的，存储的时候先做一次hash运算，根据 hash 的值就可以快速的定位数据的磁盘指针，这样就不管表里面有多少数据，我们的查询效率都非常的快；

在实际中为什么使用 B-Tree 或 B+Tree 来存储索引的方式更多，而不太使用 hash 呢？

原因1：若使用 select \* from t where clo2 > 6，这种查找范围的SQL，那Hash就不能搞定了，就不会走索引了；而且对排序hash也没有办法；

原因2：hash会产生 hash 碰撞，MySQL的底层对hash做了处理，很少会发生hash碰撞的；

[https_www.cnblogs.com_yufeng218_p_12465694.html]: https://www.cnblogs.com/yufeng218/p/12465694.html
[MySQL]: https://baike.baidu.com/item/MySQL/471251
[Link 1]: https://baike.baidu.com/item/%E5%BC%80%E6%94%BE%E6%BA%90%E4%BB%A3%E7%A0%81/114160
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%BA%93%E7%AE%A1%E7%90%86
[Link 3]: https://baike.baidu.com/item/%E7%BB%93%E6%9E%84%E5%8C%96%E6%9F%A5%E8%AF%A2%E8%AF%AD%E8%A8%80/10450182
[Link 4]: https://baike.baidu.com/item/%E4%BA%8B%E5%8A%A1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70]: /images/20230209/b72bc70e95cc44f38cff1aa3e410eb5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 1]: /images/20230209/5c9fc2582a974a10a407703d5b6b086a.png
[format_png]: /images/20230209/c4cc66a42ee646de9ab5d0e4074ddb9a.png
[https_www.cs.usfca.edu_galles_visualization_BST.html]: https://www.cs.usfca.edu/~galles/visualization/BST.html
[format_png 1]: /images/20230209/e50f541ce6e140efa0357ec19397061d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 2]: /images/20230209/c2662375119e4cdfa93b53fd6c46abfe.png
[Link 5]: https://www.cnblogs.com/ybf-yyj/p/9513706.html
[format_png 2]: /images/20230209/275d0d7cb8bb4b4ebec4aa311317ae15.png
[format_png 3]: /images/20230209/d330a21004e64a6b85d6f9517dc38ac8.png
[20200715210312678.png]: /images/20230209/03d3afd37d9d42a79bffc3c22e24afbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwNzE4NQ_size_16_color_FFFFFF_t_70 3]: /images/20230209/52c94dc7a330465bbe33f7baf2c3eef2.png