element tree 修改节点数据_Mysql索引之B+Tree

╰半夏微凉° 2023-01-10 11:54 113阅读 0赞

![daa503ee054710d25fe98ec0ee3b8b16.png][]

**前言**

Mysql索引是Java面试必问问题之一，各种提问层出不穷，只要我们对其从原理到使用深入理解，就再也不用担心面试被提问了。

**一、索引是什么**

索引是对数据库表中一列或者多列的值进行排序的一种数据结构，使用索引可以快速访问数据库表中的特定信息。如果把数据库中的某一张表看做成一本书，索引就好像是书中的目录，通过目录可以快速查到指定的章节，避免全书一页一页的查询，对于数据库表而言，可以通过索引快速查询出表中的数据，避免全表检索。

**二、MySQL索引分类**

1、**普通索引** index —— 加速查找

2、**唯一索引**

主键索引：primary key —— 加速查找 和 约束(不能为空且唯一)

唯一索引：unique —— 加速查找 和 约束(唯一)

3、**联合索引**

primary key(id,name) —— 联合主键索引

unique(id,name)—— 联合唯一索引

index(id,name)—— 联合普通索引

4、**全文索引** fulltext

用于搜索很长一篇文章的时候，效果最好

5、**空间索引** spatial

几乎不被使用，知道即可

**三、MySQL数据库为何要使用B+Tree作为索引的数据结构**

**1、二叉树**

对于数据检索，首先想到是二叉树，二叉树的查找时间复杂度是O(log2(n))。

![df3cb23538c6e02ba0a510ac2fa239c7.png][]

二叉树搜索相当于一个二分查找，二分查找能大大提升查询效率，但是存在一个问题，有可能出现线性结构的二叉树，相当于全表扫描，查询效率极低。如果插入的数据是1、2、3、4这类有大小排序好的数据，就会出现如下图的情况

![0acab6216cb12b44eb8b849f06ee6c8a.png][]

**2、平衡二叉树**

为了解决二叉树存在线性链表的问题，会想到用平衡二叉查找树来解决。

平衡二叉树：节点和子节点高度差不能超过1，为了保证二叉树平衡的方式为左旋，右旋等操作。

![c14a0bc1bcdc015e6b99c6ace4738a2f.png][]

貌似平衡二叉树解决了二叉树存在线性链表的问题，数据查询的效率好像也还可以，基本能达到O(log2(n))，那为什么mysql不选择平衡二叉树作为索引的存储结构呢？

**原因1：**搜索效率不足，在树结构中，数据所处的深度，决定搜索的IO次数。当数据达到几百万条以后，树的高度将会很大，如果查询树底部的数据，IO次数将大大提高。

**原因2：**查询不稳定，如果查询的数据落在根节点，只需要一次IO，如果是叶子节点或者是支节点，会需要多次IO才可以。

**原因3：**存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页大小为 4K，即每次IO，操作系统会将4K数据加载进内存。但是在平衡二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。一次IO操作，却只加载了一个关键字。在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的情况下，取一个关键字要做很多次磁盘IO。

**3、多路平衡查找树(B-Tree)**

B-Tree 是一个绝对平衡树，所有的叶子节点在同一高度；每个节点保存关键字的个数和路数的关系为：关键字个数 = 路数 - 1

![d7f2cbecff71d87c7327a5b4bec205fb.png][]

假设要从上图中查找id = X的数据，B-TREE 搜索过程如下：

1、取出根磁盘块，加载17和35两个关键字。

2、如果X等于17，则命中；如果X小于17走P1；如果17 < X < 35走P2；如果X = 35，则命中；如果X > 35走P3。

**为什么说B-Tree能够解决平衡二叉树存在的问题呢？**

B-Tree 能够很好的利用操作系统和磁盘的交互特性， MySQL为了很好的利用磁盘的预读能力，将页大小设置为16K，即将一个节点(磁盘块)的大小设置为16K，一次IO将一个节点(16K)内容加载进内存。

这里，假设关键字类型为 int，即4字节，若每个关键字对应的数据区也为4字节，不考虑子节点引用的情况下，则上图中的每个节点大约能够存储(16 \* 1000)/ 8 = 2000个关键字，共2001个路数。对于二叉树，三层高度，最多可以保存7个关键字，而对于这种有2001路的B树，三层高度能够搜索的关键字个数远远的大于二叉树。

**注意：**

在B-Tree保证树平衡的过程中，每次关键字的变化，都会导致结构发生很大的变化，这个过程是特别浪费时间，所以创建索引时，一定要创建合适的索引，而不是把所有的字段都创建索引，创建冗余索引只会在对数据进行新增，删除，修改时增加性能消耗。

**4、B+Tree**

B+Tree是在B-Tree基础上的一种优化，在B+Tree中，B树的路数和关键字的个数的关系不再成立了，数据检索规则采用的是左闭合区间，路数和关键个数关系为1比1。

![9d35847bf5b4ec21bb0c2f11a133b2ca.png][]

**B+Tree与B-Tree之间有哪些区别？**

**区别1：**B+Tree节点关键字搜索采用左闭合区间

**区别2：**B+Tree非叶子节点不保存数据相关信息，只保存关键字和子节点的引用

**区别3：**B+Tree节点关键字对应的数据只保存在叶子节点中

**区别4：**B+Tree叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系

**MySQL数据库为何最终选择用B+Tree?**

**原因1：**B+Tree是B-Tree的变种，B-Tree能解决的问题，B+Tree也能够解决，而且可以有效降低树的高度，减少磁盘IO次数，增大节点存储数据量。

**原因2：**B+Tree扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描，对B-Tree进行扫描，需要把整棵树遍历一遍，而B+Tree只需要遍历他的所有叶子节点即可(叶子节点之间有引用)。

**原因3：**B+Tree磁盘读写能力更强。他的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，保存的关键字要比B-Tree多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以，B+Tree读写一次，磁盘加载的关键字比B-Tree更多。

**原因4：**B+Tree排序能力更强。上面的图中可以看出，B+Tree天然具有排序功能。

**原因5：**B+Tree查询性能稳定。B+Tree数据只保存在叶子节点，每次查询数据，查询IO次数一定是稳定的。

![310f8852c349d254889710f21b5aef3f.png][]

[daa503ee054710d25fe98ec0ee3b8b16.png]: /images/20221119/99cb2235209a4e0d92bd3723a4cc3347.png
[df3cb23538c6e02ba0a510ac2fa239c7.png]: /images/20221119/6c105ba48d044971b62eb1b81b921315.png
[0acab6216cb12b44eb8b849f06ee6c8a.png]: https://img-blog.csdnimg.cn/img_convert/0acab6216cb12b44eb8b849f06ee6c8a.png
[c14a0bc1bcdc015e6b99c6ace4738a2f.png]: https://img-blog.csdnimg.cn/img_convert/c14a0bc1bcdc015e6b99c6ace4738a2f.png
[d7f2cbecff71d87c7327a5b4bec205fb.png]: https://img-blog.csdnimg.cn/img_convert/d7f2cbecff71d87c7327a5b4bec205fb.png
[9d35847bf5b4ec21bb0c2f11a133b2ca.png]: https://img-blog.csdnimg.cn/img_convert/9d35847bf5b4ec21bb0c2f11a133b2ca.png
[310f8852c349d254889710f21b5aef3f.png]: https://img-blog.csdnimg.cn/img_convert/310f8852c349d254889710f21b5aef3f.png