446-MySQL(索引的底层实现原理,B树,B+树索引) 冷不防 2022-09-06 04:49 160阅读 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
还没有评论,来说两句吧...