446-MySQL(索引的底层实现原理,B树,B+树索引)

冷不防 2022-09-06 04:49 225阅读 0赞

## 索引的底层实现原理 ##

**数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘块（对应索引树的节点），索引树越低，越“矮胖”，磁盘IO次数就少**

**MySQL支持两种索引，一种的B-树索引，一种是哈希索引**  
大家知道，B-树和哈希表在数据查询时的效率是非常高的。  
**这里我们主要讨论一下MySQL InnoDB存储引擎，基于B-树（但实际上MySQL采用的是B+树结构）的索引结构。**  
B-树是一种m阶平衡树，叶子节点都在同一层，由于每一个节点存储的数据量比较大，索引整个B-树的层数是非常低的，基本上不超过三层。

**由于磁盘的读取也是按block块操作的**（内存是按page页面操作的，一般是16k，是内存页面的整数倍，读1块，刚好放到4个内存页面上），因此B-树的节点大小一般设置为和磁盘块大小一致，这样一个B-树节点，就可以通过一次磁盘I/O把一个磁盘块的数据全部存储下来，所以当使用B-树存储索引的时候，磁盘I/O的操作次数是最少的（MySQL的读写效率，主要集中在磁盘I/O上）  
**数据和索引都是放在磁盘上的**，MySQL server不可能直接从磁盘上读取数据，得通过操作系统把磁盘上的数据加载到内存中，也就是说，运行起来的进程要访问索引，需要花费磁盘I/O，先把数据，索引读到内存当中，这个磁盘I/O当然是少的好，磁盘I/O影响效率。  
**在我们的C/C++语言中**，如果我们new/malloc向内存申请4个字节，实际上不可能只拿4个字节，内存管理是按页面4K为大小单位的，操作系统相当于批发站，它批发内存是以页面为单位的，我们申请4个字节，实际上我们向内核kernel申请，内核是按页面给我们分配的。按页面分配以后，但是我们的应用程序只需要4个字节，还剩下的字节就被lib.so或者 libc++.so库的ptmalloc（缓存），tcmalloc来管理，相当于2个函数，管理剩下的空闲的字节，等你下次还malloc申请字节的时候，就不用向内核空间申请，直接在用户空间，从c库分配出来就可以了。等用光了，才向内核申请。

**假设有2千万的数据，要进行读取，如果是平衡的二叉树，一个节点1个数据，2个指针，二叉平衡树构建2千万的数据，树有多少层？log2000w，**  
![在这里插入图片描述][43e61ca86ad94ff4834746291c121339.png]  
**25层。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

**在最坏的情况下，读取一个索引，要花费25次磁盘I/O**

## B-树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**涉及到磁盘到内存的一些读取，我们一般都采用B-树结构。**  
首先，B-树是平衡树，所有叶子节点都在一层，AVL树是平衡二叉树（左右子树高度差不会超过1），搜索的时间复杂度是O(logn)，二分搜索也是。

**我们称B-树是m阶平衡树，一般取值300-500。**  
**如果我们用B-树构建数据结构来存储2千万的索引，假如m取500，**

![在这里插入图片描述][bc7113ad5e3f4ad7890fd482f0c71e3b.png]  
**最多3层，最多3次磁盘I/O就可以了**  
**最好的情况是一次磁盘I/O读取的磁盘块的内容，刚好存储在B树的1个节点中。**

**我们以下面这张表格为例**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

我们把uid设置成了主键，主键会自动创建索引，  
当我们进行一些查询操作的时候，  
![在这里插入图片描述][94ae9fd8862449349bcebc10123be3fb.png]  
一看uid有索引，请求存储引擎，请求kernel，花费磁盘I/O从磁盘上读索引文件到内存上，用索引的数据构建B-树加速搜索。  
**key是建索引的列**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**17,35,8，12等紫色的这些数字是key值，左孩子比父节点的值小，父节点比右孩子的值小，这是平衡树的概念**，**黄色的data**表示key索引所在的这一行的数据，**data存储的是数据本身内容，还是在磁盘上的地址**？这得看我们使用哪种存储引擎。**如果我们用的是MyISAM存储引擎**，索引和数据是在不同的文件存储，上图这构建的是索引树，存储的自然是在磁盘的地址了，通过索引值在磁盘上找到包含这个索引值的记录，然后通过地址在磁盘上读取数据文件中相应的数据。  
**如果我们用的是InnoDB存储引擎**，数据和索引是在一块放着的，索引树上放的就是数据。即使没有加主键，会自动创建主键，和索引。

这样一来，在搜索的时候，比如我们要搜索28，但是一个B树节点里面的数据很多，不止在图中画的17和35两个节点，m取值是300-500。如果是m取500的B树，相当于一个节点有500个指针域，指向500个孩子，有499个数据域。平衡树中，**在一个节点里，里面的数据也是从小到大排序的**。在一个节点里，有很多数据域，**当我们想要去找28时，在一个节点里面怎么搜？肯定是二分搜索。** 时间复杂度：O(logn)  
**选择B树结构的好处是：非常少的磁盘I/O**  
![在这里插入图片描述][94ae9fd8862449349bcebc10123be3fb.png]  
**如果uid没有索引的话，搜索的时候，是整张表一行一行的搜索，不在索引树上搜索。**

**再举个例子**  
![在这里插入图片描述][f167a11549454408b5e08e5e23791105.png]  
如果name没有索引的话，如果在MyISAM中，就是把整张表过1遍，效率非常低。如果我们给name建1个索引的话，当我们再去执行这个select语句的时候，MySQL server的分析器就知道name有索引，直接加载name的索引，花费磁盘I/O，把磁盘上的数据加载到内存中来，构建成B-树。name就是相当于上图中的紫色数据。

**从上图可以看到B-树存在的缺点：**  
每个节点中有key，也有data，但是每一个节点的存储空间是有限的，如果data数据较大时会导致每个节点能存储的key的数据很小  
当存储的数据量很大时同样会导致B-树的高度较大，磁盘IO次数花费增大，效率降低

## B+树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
1、每一个非节点只存放key，不存放data，这样的好处是一个节点存放的key值更多，这样B+树在理论上来说，层数更低一些，搜索的效率更好一些。  
2、数据都存储在叶子节点上。我们发现，叶子节点上存储了所有的索引值和其对应的data。直接的好处就是搜索每一个索引对应的值data都需要跑到叶子节点上，这样，每一行记录搜索的时间是非常均匀的。  
3、叶子节点被串在一个链表当中，形成了一个有序的链表。如果要进行索引树的搜索或者是整表搜索，直接遍历叶子节点的有序链表即可。或者做范围查询的时候，直接遍历叶子节点的有序链表即可。

## MySQL最终为什么要采用B+树存储索引结构呢？ ##

**那么看看B-树和B+树在存储结构上有什么不同？**

1.  B-树的每一个节点，存了关键字和对应的数据地址，而B+树的非叶子节点只存关键字，不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的，B+树的叶子节点存放关键字和数据，因此，从树的高度上来说，B+树的高度要小于B-树，使用的磁盘I/O次数少，因此查询会更快一些。
2.  B-树由于每个节点都存储关键字和数据，因此离根节点进的数据，查询的就快，离根节点远的数据，查询的就慢，花费的磁盘I/O次数不均匀，每一行数据搜索花费的时间也不均匀；B+树所有的数据都存在叶子节点上，因此在B+树上搜索关键字，找到对应数据的时间是比较平均的，没有快慢之分。
3.  在B-树上如果做区间查找，遍历的节点是非常多的，非常麻烦，遍历左右子树；B+树所有叶子节点被连接成了有序链表结构，因此做整表遍历和区间查找是非常容易的。

**从一张表进行搜索的话，如果我加了过滤条件，**  
![在这里插入图片描述][93472b810f80405ab104115c7bdd1374.png]  
**MySQL先检查有没有索引，如果没有索引的话，就做整表搜索，效率是非常低的，如果有索引的话，操作系统会给我们从磁盘上的索引文件加载到内存上，用B+树来构建，一个节点刚好对应1个磁盘I/O，非叶子节点存的都是key，所有的key和data都是存储在叶子节点上，花费最少的磁盘I/O次数，以logn的时间复杂度，来找见索引对应的数据。**

[43e61ca86ad94ff4834746291c121339.png]: /images/20220829/2cc22b033a0c4faf819531d6e0a368e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/2f331538f0ff4d108e96acfb75a43aac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/22df7f2bc6a34c4bbd22ebc4440d63ef.png
[bc7113ad5e3f4ad7890fd482f0c71e3b.png]: /images/20220829/99b179fbf8e149dfb1c66640d8c88f72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/2d1b39523a164ee186d4517e5c148963.png
[94ae9fd8862449349bcebc10123be3fb.png]: /images/20220829/de1bee704481471b82547e6cde8f90b3.png
[f167a11549454408b5e08e5e23791105.png]: /images/20220829/155e984a66a44be6b52bb7399e1ef3ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/93ba2ecf1d794a97802c9487a34e61d6.png
[93472b810f80405ab104115c7bdd1374.png]: /images/20220829/e062872e7ee446b79a5e67dbe11953e5.png