认识达内从这里开始

B+树索引是程序员在学习MySQL数据库技术的时候需要重点掌握的一个编程知识点，而本文我们就通过案例分析来简单了解一下，B+树索引的概念与作用分析。

B+树就是传统意义上的索引，这是目前关系型数据库中查找为常用和为有效的索引。B+树构造的索引类似于二叉树，根据键值快速(KeyValue)快速找到数据。

有一点需要注意的是，B+树索引并不能找到给定键值具体的行。B+树索引能找到的只是被查找数据行所在的页。然后把页读入到内存中，再在内存中查找，找到查询的目标数据。

B+树是B树的变种，这里需要了解下B树。

为什么要引入B树或者B+树呢?

红黑树等其它的数据结构也可以用来实现索引，为什么要使用B树或者B+树，简单点讲就是为了减少磁盘的I/O。

一般来说，索引本身的数据量很大，全部放入到内存中是不太现实的，因此索引往往以索引文件的形式存储在磁盘中，磁盘I/O的消耗相比于内存中的读取还是大了很多的，在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址时间。

为了让一个查询尽量少地读磁盘，就需要减少树的高度，就不能使用二叉树，而是使用N叉树了，这样就能在遍历较少节点的情况下也就是较少I/O查询的情况下找到目标值。

比如一个二叉树，访问底部数据需要进行4次I/O操作。

mysql

如果使用4叉树，那么树的层架就会变矮，这时候只需要进行3次I/O操作。

mysql

数据量越来越大，N叉树的效果更明显，在有相同数据的情况下，对于二叉树，能够大大缩小树的高度。

所以B树和B+树就被慢慢演变而来了。

自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是因为它本质上是一个二叉树，每个节点只能有2个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的I/O次数，从而影响数据查询的效率。

为了解决降低树的高度的问题，后面就出来了B树，它不再限制一个节点就只能有2个子节点，而是允许M个子节点(M>2)，从而降低树的高度。

为什么MySQL用的是B+树而不是B树呢，这里来看下区别?

B-tree和B+树重要的区别是B+树只有叶子节点存储数据，其他节点用于索引，而B-tree对于每个索引节点都有Data字段。

mysql

B树简单的讲就是一种多叉平衡查找树，它类似于普通的平衡二叉树。不同的是B-tree允许每个节点有更多的子节点，这样就能大大减少树的高度。

mysql

B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+树相比与B树：

1、非叶子节点只存储索引信息;

2、所有叶子节点都有一个链指针，所以B+树可以进行范围查询;

3、数据都放在叶子节点中。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加抖音太原达内IT培训学习了解。